Layered State Discovery for Incremental Autonomous Exploration
This addresses the problem of efficiently discovering policies in reinforcement learning for researchers, with incremental improvements over prior work.
The paper tackles the autonomous exploration problem by introducing a layered decomposition and the LAE algorithm, achieving a sample complexity of ω(LS→L(1+ε)ΓL(1+ε)A ln^12(S→L(1+ε))/ε^2) and, under an assumption, a minimax-optimal complexity matching a lower bound up to logarithmic factors.
We study the autonomous exploration (AX) problem proposed by Lim & Auer (2012). In this setting, the objective is to discover a set of $ε$-optimal policies reaching a set $\mathcal{S}_L^{\rightarrow}$ of incrementally $L$-controllable states. We introduce a novel layered decomposition of the set of incrementally $L$-controllable states that is based on the iterative application of a state-expansion operator. We leverage these results to design Layered Autonomous Exploration (LAE), a novel algorithm for AX that attains a sample complexity of $\tilde{\mathcal{O}}(LS^{\rightarrow}_{L(1+ε)}Γ_{L(1+ε)} A \ln^{12}(S^{\rightarrow}_{L(1+ε)})/ε^2)$, where $S^{\rightarrow}_{L(1+ε)}$ is the number of states that are incrementally $L(1+ε)$-controllable, $A$ is the number of actions, and $Γ_{L(1+ε)}$ is the branching factor of the transitions over such states. LAE improves over the algorithm of Tarbouriech et al. (2020a) by a factor of $L^2$ and it is the first algorithm for AX that works in a countably-infinite state space. Moreover, we show that, under a certain identifiability assumption, LAE achieves minimax-optimal sample complexity of $\tilde{\mathcal{O}}(LS^{\rightarrow}_{L}A\ln^{12}(S^{\rightarrow}_{L})/ε^2)$, outperforming existing algorithms and matching for the first time the lower bound proved by Cai et al. (2022) up to logarithmic factors.