# Exploration-Enhanced POLITEX

arXiv: https://arxiv.org/abs/1908.10479 · HTML: https://mlsanity.com/paper/1908.10479/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Aug 2019.

## Built on by (most cited first, 8 of 8)

- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Going Beyond Linear RL: Sample Efficient Neural Function Approximation](https://mlsanity.com/paper/2107.06466/) (2021)

## Abstract (arXiv)

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.