Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes

2023/06/28 by Zhang, Zihan, Xie, Qiaomin · 3 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2306.16394

Abstract

We develop several provably efficient model-free reinforcement learning (RL) algorithms for infinite-horizon average-reward Markov Decision Processes (MDPs). We consider both online setting and the setting with access to a simulator. In the online setting, we propose model-free RL algorithms based on reference-advantage decomposition. Our algorithm achieves \widetildeO(S⁵A²sp(h^*)√(T)) regret after T steps, where S× A is the size of state-action space, and sp(h^*) the span of the optimal bias function. Our results are the first to achieve optimal dependence in T for weakly communicating MDPs. In the simulator setting, we propose a model-free RL algorithm that finds an ε-optimal policy using \widetildeO ((SAsp²(h^*))/(ε²)+\fracS²Asp(h^*)ε ) samples, whereas the minimax lower bound is Ω((SAsp(h^*))/(ε²)). Our results are based on two new techniques that are unique in the average-reward setting: 1) better discounted approximation by value-difference estimation; 2) efficient construction of confidence region for the optimal bias function with space complexity O(SA).

Cited by

• A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
• Finite-Time Bounds for Average-Reward Fitted Q-Iteration
• Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain

Related

• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation