Scalable Online Exploration via Coverability
<|reference_start|>Scalable Online Exploration via Coverability: Exploration is a major challenge in reinforcement learning, especially for high-dimensional domains that require function approximation. We propose exploration objectives -- policy optimization objectives that enable downstream maximization of any reward function -- as a conceptual framework to systematize the study of exploration. Within this framework, we introduce a new objective, $L_1$-Coverage, which generalizes previous exploration schemes and supports three fundamental desiderata:   1. Intrinsic complexity control. $L_1$-Coverage is associated with a structural parameter, $L_1$-Coverability, which reflects the intrinsic statistical difficulty of the underlying MDP, subsuming Block and Low-Rank MDPs.   2. Efficient planning. For a known MDP, optimizing $L_1$-Coverage efficiently reduces to standard policy optimization, allowing flexible integration with off-the-shelf methods such as policy gradient and Q-learning approaches.   3. Efficient exploration. $L_1$-Coverage enables the first computationally efficient model-based and model-free algorithms for online (reward-free or reward-driven) reinforcement learning in MDPs with low coverability.   Empirically, we find that $L_1$-Coverage effectively drives off-the-shelf policy optimization algorithms to explore the state space.<|reference_end|>
@article{amortila2024scalable,
    title={Scalable Online Exploration via Coverability},
    author={Philip Amortila, Dylan J. Foster, Akshay Krishnamurthy},
    journal={arXiv preprint arXiv:2403.06571},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.06571},
    primaryClass={cs.LG math.OC stat.ML}
}