Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs
<|reference_start|>Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs: We resolve the open problem of designing a computationally efficient algorithm for infinite-horizon average-reward linear Markov Decision Processes (MDPs) with $\widetilde{O}(\sqrt{T})$ regret. Previous approaches with $\widetilde{O}(\sqrt{T})$ regret either suffer from computational inefficiency or require strong assumptions on dynamics, such as ergodicity. In this paper, we approximate the average-reward setting by the discounted setting and show that running an optimistic value iteration-based algorithm for learning the discounted setting achieves $\widetilde{O}(\sqrt{T})$ regret when the discounting factor $\gamma$ is tuned appropriately. The challenge in the approximation approach is to get a regret bound with a sharp dependency on the effective horizon $1 / (1 - \gamma)$. We use a computationally efficient clipping operator that constrains the span of the optimistic state value function estimate to achieve a sharp regret bound in terms of the effective horizon, which leads to $\widetilde{O}(\sqrt{T})$ regret.<|reference_end|>
@article{hong2024reinforcement,
    title={Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs
  via Approximation by Discounted-Reward MDPs},
    author={Kihyuk Hong, Woojin Chae, Yufan Zhang, Dabeen Lee, Ambuj Tewari},
    journal={arXiv preprint arXiv:2405.15050},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15050},
    primaryClass={stat.ML cs.LG}
}