Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning

2024/05/29 by Kar, Avik, Singh, Rahul
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2405.18793

Abstract

We study the infinite-horizon average-reward reinforcement learning (RL) for continuous space Lipschitz MDPs in which an agent can play policies from a given set Φ. The proposed algorithms efficiently explore the policy space by ''zooming'' into the ''promising regions'' of Φ, thereby achieving adaptivity gains in the performance. We upper bound their regret as O(T^1 - d_eff.^-1), where d_eff. = d^Φ_z+2 for model-free algoritahm PZRL-MF and d_eff. = 2d_S + d^Φ_z + 3 for model-based algorithm PZRL-MB. Here, d_S is the dimension of the state space, and d^Φ_z is the zooming dimension given a set of policies Φ. d^Φ_z is an alternative measure of the complexity of the problem, and it depends on the underlying MDP as well as on Φ. Hence, the proposed algorithms exhibit low regret in case the problem instance is benign and/or the agent competes against a low-complexity Φ (that has a small d^Φ_z). When specialized to the case of finite-dimensional policy space, we obtain that d_eff. scales as the dimension of this space under mild technical conditions; and also obtain d_eff. = 2, or equivalently O(√(T)) regret for PZRL-MF, under a curvature condition on the average reward function that is commonly used in the multi-armed bandit (MAB) literature.

Related

• Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs