Layered State Discovery for Incremental Autonomous Exploration
share
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 𝒮_L^→ 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 𝒪̃(LS^→_L(1+ϵ)Γ_L(1+ϵ) A ln^12(S^→_L(1+ϵ))/ϵ^2), where S^→_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 𝒪̃(LS^→_LAln^12(S^→_L)/ϵ^2), outperforming existing algorithms and matching for the first time the lower bound proved by Cai et al. (2022) up to logarithmic factors.
READ FULL TEXT