Instance-Dependent Auto-Exploration for Tabular Online Discounted Reinforcement Learning

In online discounted reinforcement learning from a single trajectory, a central cost is exploration: the time spent reaching states whose optimal action is still unknown. Existing auto-exploration guarantees for stochastic policy mirror descent charge every iteration the cost of reaching the hardest state, even once its optimal action is known, through a constant exponential in the mixing time of the optimal policy. We prove that the exploration cost is controlled instead by a certified hitting cost $H_{\theta }(s)$, which is equivalent up to constants to the worst-case expected time to reach $s$ under policies that keep mass at least $\theta$ on optimal actions. For the algorithm's $\theta$, every iterate is such a policy with high probability. Each rollout stops once it covers the states where the policy keeps mass at least $\theta$ on two or more actions. Resolved states leave this set, so every iteration is charged only the largest $H_{\theta }(s)$ over unresolved states. For accuracy $ϵ$ and advantage gaps $\Delta (s)$, the sample complexity is then at most an ${ϵ}^{-2}$ baseline plus the exploration cost ${\max }_s{H}_{\theta }(s)/\max \{(1-\gamma )ϵ,\Delta (s){\}}^2$, up to logarithmic and instance-independent factors. The only structural assumption is that some deterministic optimal policy induces an irreducible chain; the mixing regime and action-independent transitions are special cases with explicit bounds on $H_{\theta }$. On an action-dependent family of $3n-2$ states whose small gaps arise from transitions, the upper bound $\tilde{O}(n^2+n{ϵ}^{-2})$ matches a lower bound with deterministic costs up to logarithmic factors, for a fixed discount factor. Charging the hardest state at every iteration gives $\Omega (n^2{ϵ}^{-2})$.