Adaptive Approximate Policy Iteration

Abstract

Model-free reinforcement learning algorithms combined with value function approximation have recently achieved impressive performance in a variety of application domains. However, the theoretical understanding of such algorithms is limited, and existing results are largely focused on episodic or discounted Markov decision processes (MDPs). In this work, we present adaptive approximate policy iteration (AAPI), a learning scheme which enjoys a \(\tilde\{O\}(T^\{2/3\})\) regret bound for undiscounted, continuing learning in uniformly ergodic MDPs. This is an improvement over the best existing bound of \(\tilde\{O\}(T^\{3/4\})\) for the average-reward case with function approximation. Our algorithm and analysis rely on online learning techniques, where value functions are treated as losses. The main technical novelty is the use of a data-dependent adaptive learning rate coupled with a so-called optimistic prediction of upcoming losses. In addition to theoretical guarantees, we demonstrate

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhao2020adaptive

Related papers

• Dual Policy Iteration (2018)0.00
• The Role Of Lookahead And Approximate Policy Evaluation In Reinforcement Learning With Linear Value Function Approximation (2021)0.00
• Reinforcement Learning With Unbiased Policy Evaluation And Linear Function Approximation (2022)0.00
• Unifying Value Iteration, Advantage Learning, And Dynamic Policy Programming (2017)0.00
• \(\sqrt{n}\)-regret For Learning In Markov Decision Processes With Function Approximation And Low Bellman Rank (2019)0.00
• Solving Common-payoff Games With Approximate Policy Iteration (2021)3.58
• Improved Regret Bound And Experience Replay In Regularized Policy Iteration (2021)0.00
• Cautiously Optimistic Policy Optimization And Exploration With Linear Function Approximation (2021)0.00