Exploration-Enhanced POLITEX

Abstract

We study algorithms for average-cost reinforcement learning problems with value function approximation. Our starting point is the recently proposed POLITEX algorithm, a version of policy iteration where the policy produced in each iteration is near-optimal in hindsight for the sum of all past value function estimates. POLITEX has sublinear regret guarantees in uniformly-mixing MDPs when the value estimation error can be controlled, which can be satisfied if all policies sufficiently explore the environment. Unfortunately, this assumption is often unrealistic. Motivated by the rapid growth of interest in developing policies that learn to explore their environment in the lack of rewards (also known as no-reward learning), we replace the previous assumption that all policies explore the environment with that a single, sufficiently exploring policy is available beforehand. The main contribution of the paper is the modification of POLITEX to incorporate such an exploration policy in a way that allows us to obtain a regret guarantee similar to the previous one but without requiring that all policies explore environment. In addition to the novel theoretical guarantees, we demonstrate the benefits of our scheme on environments which are difficult to explore using simple schemes like dithering. While the solution we obtain may not achieve the best possible regret, it is the first result that shows how to control the regret in the presence of function approximation errors on problems where exploration is nontrivial. Our approach can also be seen as a way of reducing the problem of minimizing the regret to learning a good exploration policy. We believe that modular approaches like ours can be highly beneficial in tackling harder control problems.

References in corpus (8)

• Prioritized Experience Replay
• Dueling Network Architectures for Deep Reinforcement Learning
• DeepMind Control Suite
• Distributed Prioritized Experience Replay
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Provably Efficient Maximum Entropy Exploration
• Model-Free Linear Quadratic Control via Reduction to Expert Prediction
• Regularized Off-Policy TD-Learning

Cited by in corpus (17)

• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Provably Efficient Exploration in Policy Optimization
• Learning and Planning in Average-Reward Markov Decision Processes
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Online learning in MDPs with linear function approximation and bandit feedback
• Online Learning for Unknown Partially Observable MDPs
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Towards General Function Approximation in Zero-Sum Markov Games
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Online Sparse Reinforcement Learning
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation