A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret

Haipeng LuoarXiv 2020 · arXiv

TL;DR

This paper introduces Exploration Enhanced Q-learning (EE-QL), a novel model-free reinforcement learning algorithm that achieves near-optimal regret bounds for infinite-horizon average-reward Markov Decision Processes (MDPs). This is a significant advancement as it matches theoretical lower bounds without requiring strong ergodicity assumptions, a limitation of previous model-free methods.

What Problem Does This Paper Address?

Reinforcement learning (RL) aims to train agents to make optimal decisions in an environment to maximize cumulative rewards. A key challenge in RL is the exploration-exploitation trade-off: balancing the need to explore the environment to gather information with the desire to exploit existing knowledge for immediate rewards. This trade-off is quantified by "regret," which measures the difference between the agent's cumulative reward and the optimal possible reward.

While model-based RL algorithms (which learn a model of the environment) have achieved good regret bounds, model-free algorithms (which learn directly from experience) are often simpler and more scalable. However, achieving near-optimal regret bounds for model-free algorithms in infinite-horizon average-reward MDPs has been particularly challenging. This is due to the difficulty of estimating Q-values (expected future rewards for state-action pairs) without the problem becoming unstable or requiring strong assumptions about the environment's dynamics (like ergodicity). Previous model-free approaches either achieved suboptimal regret or relied on these strong assumptions.

Methods

The paper proposes Exploration Enhanced Q-learning (EE-QL), a model-free algorithm designed for infinite-horizon average-reward MDPs. The core of EE-QL lies in its novel approach to estimating the Q-value function and managing optimism.

Key aspects of EE-QL include:

  • Stochastic Approximation with a Modified Learning Rate: EE-QL uses a learning rate of $\alpha_\tau \propto 1/\sqrt{\tau}$ (where $\tau$ is the number of visits to a state-action pair), which is different from the standard $1/\tau$ used in Q-learning. This specific learning rate is crucial for balancing new and old observations and has desirable properties for theoretical analysis.
  • Concentrating Estimate of the Optimal Gain ($J^*$): The algorithm assumes access to a "concentrating estimate" of the optimal average reward, denoted as $J_t$. This estimate is assumed to satisfy $|J_t - J^*| \leq c/\sqrt{t}$. In cases where $J^*$ is unknown, $J_t$ is updated stochastically.
  • Economical Use of Optimism: Unlike some prior model-free methods that applied optimism (e.g., using UCB) to individual Q-value estimates, EE-QL applies optimism to a single scalar: the estimated optimal average reward $J_t$. This "optimism around a single scalar" is a key innovation that leads to improved performance and theoretical guarantees.

Datasets

Not discussed in the paper. The experiments are conducted on synthetic environments: RandomMDP and RiverSwim.

Key Insights and Ideas

  • Breaking the Ergodicity Barrier for Model-Free RL: The most significant insight is demonstrating that near-optimal $\mathcal{O}(\sqrt{T})$ regret is achievable for model-free algorithms in average-reward MDPs without requiring the strong ergodicity assumption. This opens up the applicability of model-free methods to a broader class of problems.
  • Optimism on a Scalar vs. Vector: The paper highlights that applying optimism to a single value (the average reward $J^*$) is more efficient and leads to better empirical performance than applying it to every Q-value estimate. This is because the latter can lead to "wasted optimism" that doesn't necessarily translate to better learning.
  • The Importance of the Learning Rate: The choice of the learning rate $\alpha_\tau \propto 1/\sqrt{\tau}$ is critical. It's shown to be essential for balancing the influence of past and present data and for enabling the theoretical analysis that leads to the $\mathcal{O}(\sqrt{T})$ regret bound.

Key Results

  • Theoretical Guarantee: EE-QL achieves a regret bound of $\mathcal{O}((\text{sp}(q^*) + cSA \ln T)\sqrt{SAT} + \text{sp}(v^*)\sqrt{T \ln 1/\delta})$, which matches the lower bound of $\Omega(\sqrt{DSAT})$ up to logarithmic factors. This is the first model-free algorithm to achieve this bound for weakly communicating MDPs.
  • Empirical Performance: Experiments on RiverSwim and RandomMDP environments show that EE-QL significantly outperforms existing model-free algorithms like Optimistic QL. It also performs comparably to the best model-based algorithms, demonstrating its practical effectiveness. In the RiverSwim environment, other model-free algorithms that require ergodicity did not achieve sub-linear regret.

Limitations and Future Work

  • Assumption on $J_t$: The theoretical analysis relies on the assumption that a concentrating estimate of $J^*$ is available ($|J_t - J^*| \leq c/\sqrt{t}$). While the paper shows this assumption holds numerically for an optimistic empirical average reward estimator, its theoretical verification for general cases is left for future work.
  • Generalization to Function Approximation: The current theoretical guarantees are for tabular MDPs. Extending these guarantees to settings with function approximation (which is crucial for large-scale problems) is a natural next step.
  • Exploration of $J^*$ Estimation: Further research could explore more robust and theoretically grounded methods for estimating $J_t$ when $J^*$ is unknown.

Summary updated

Abstract

Recently, model-free reinforcement learning has attracted research attention due to its simplicity, memory and computation efficiency, and the flexibility to combine with function approximation. In this paper, we propose Exploration Enhanced Q-learning (EE-QL), a model-free algorithm for infinite-horizon average-reward Markov Decision Processes (MDPs) that achieves regret bound of $O(\sqrt{T})$ for the general class of weakly communicating MDPs, where $T$ is the number of interactions. EE-QL assumes that an online concentrating approximation of the optimal average reward is available. This is the first model-free learning algorithm that achieves $O(\sqrt T)$ regret without the ergodic assumption, and matches the lower bound in terms of $T$ except for logarithmic factors. Experiments show that the proposed algorithm performs as well as the best known model-based algorithms.
BibTeX
@misc{luo2020model,
  author = {Haipeng Luo},
  title = {{A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret}},
  year = {2020},
  eprint = {2006.04354},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.04354},
}
Figure