Optimism in reinforcement learning and Kullback-Leibler divergence

Sarah Filippi, Olivier Cappé, Aurélien Garivier

TL;DR

This paper introduces KL-UCRL, a novel model-based reinforcement learning algorithm that uses Kullback-Leibler (KL) divergence to implement "optimism." While achieving theoretical regret bounds comparable to existing methods like UCRL2, KL-UCRL demonstrates significantly improved practical performance, especially in environments with sparse connectivity, by avoiding pitfalls of previous L¹-based approaches.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents learn by interacting with an environment to maximize cumulative rewards. A key challenge is balancing exploration (gathering information about the environment) and exploitation (using current knowledge to maximize rewards). Model-based RL algorithms tackle this by learning a model of the environment (transition probabilities and rewards) and then acting optimally based on this learned model.

A popular strategy for balancing exploration and exploitation is "optimism in the face of uncertainty." This involves acting as if the environment were slightly better than estimated, encouraging exploration. Algorithms like UCRL2 implement this by finding an "optimistic" model that is consistent with the learned model but potentially yields higher rewards. However, UCRL2 uses the L¹ (total variation) norm to define this consistency. The authors identify several issues with L¹-based optimism: it can be discontinuous with respect to model estimates, potentially assign zero probability to observed transitions, and can lead to persistent exploration bonuses even when evidence suggests otherwise, particularly in environments with sparse connections. This paper aims to address these limitations by proposing an alternative approach using KL divergence.

Methods

The core contribution is the KL-UCRL algorithm, which replaces the L¹-norm constraint in UCRL2 with a Kullback-Leibler (KL) divergence constraint. This change is applied within the "extended value iteration" step, where the algorithm seeks an optimistic model.

The key steps involve:

  • Model Estimation: The agent maintains estimates of the environment's transition probabilities ($P_t$) and reward functions ($\hat{r}_t$) based on observed data.
  • Optimistic Model Search: Instead of finding an optimistic model $M'$ within an L¹-ball around the estimated model $M_t$, KL-UCRL searches within a KL-ball. This means finding a model $M'$ such that $KL(P_t(.;x,a), P'(.;x,a)) \le \epsilon_p(x,a,t)$ and $|\hat{r}_t(x,a) - r'(x,a)| \le \epsilon_r(x,a,t)$, where $\epsilon_p$ and $\epsilon_r$ are confidence bounds that decrease with the number of observations.
  • KL-Optimistic Extended Value Iteration: The algorithm solves a maximization problem under this KL constraint. The paper details an efficient procedure for this, involving a one-dimensional line search to find the optimal value function and policy for the optimistic model.
  • Regret Analysis: The authors prove that KL-UCRL achieves theoretical regret bounds comparable to UCRL2, guaranteeing near-optimal performance. This relies on novel concentration inequalities for KL divergence.

Datasets

Not discussed in the paper. The paper uses simulated environments for evaluation.

Key Insights and Ideas

  • KL Divergence for Optimism: The paper argues that KL divergence is a more suitable measure than L¹ norm for defining "optimistic" models in RL. This is because KL divergence leads to smoother, more continuous optimistic models, which are less prone to assigning zero probability to observed transitions and better handle sparse connectivity.
  • Geometric Interpretation: The difference between L¹ and KL balls is illustrated geometrically. KL balls are "smoother" and more "round" around the estimated probability distribution, leading to more stable and consistent optimistic models. L¹ balls can be more "angular" and lead to abrupt changes.
  • Handling Sparse Connectivity: A major advantage highlighted is KL-UCRL's superior performance in environments with reduced connectivity. Unlike L¹ optimism, KL optimism can "renounce" unobserved transitions even if they lead to states with potentially high values, leading to more efficient exploration.
  • Theoretical Guarantees: Despite the algorithmic change, KL-UCRL retains the strong theoretical regret bounds of UCRL2, demonstrating that the practical improvements do not come at the cost of theoretical guarantees.

Key Results

  • Improved Performance: Numerical experiments on benchmark environments (RiverSwim, SixArms) and randomly generated sparse environments show that KL-UCRL consistently achieves a smaller average regret than UCRL2. This improvement is particularly pronounced in sparse environments.
  • Comparable Theoretical Bounds: The paper proves that KL-UCRL achieves logarithmic regret bounds, similar to UCRL2, ensuring its theoretical soundness.
  • Efficient Algorithm: The KL-optimistic extended value iteration is solved efficiently using a one-dimensional line search, making the algorithm's computational complexity comparable to UCRL2.

Limitations and Future Work

  • Limitations: The paper focuses on finite state and action space Markov Decision Processes (MDPs). The theoretical guarantees and experimental results are for this specific setting. The practical implications for continuous state/action spaces or more complex environments are not directly addressed.
  • Future Work: The authors suggest that the geometric considerations and the advantages of KL divergence could be further explored. They also imply that the KL-UCRL algorithm's robustness and efficiency in sparse environments warrant further investigation and potential applications in more complex RL settings.

Summary updated

Abstract

We consider model-based reinforcement learning in finite Markov Decision Processes (MDPs), focussing on so-called optimistic strategies. In MDPs, optimism can be implemented by carrying out extended value iterations under a constraint of consistency with the estimated model transition probabilities. The UCRL2 algorithm by Auer, Jaksch and Ortner (2009), which follows this strategy, has recently been shown to guarantee near-optimal regret bounds. In this paper, we strongly argue in favor of using the Kullback-Leibler (KL) divergence for this purpose. By studying the linear maximization problem under KL constraints, we provide an efficient algorithm, termed KL-UCRL, for solving KL-optimistic extended value iteration. Using recent deviation bounds on the KL divergence, we prove that KL-UCRL provides the same guarantees as UCRL2 in terms of regret. However, numerical experiments on classical benchmarks show a significantly improved behavior, particularly when the MDP has reduced connectivity. To support this observation, we provide elements of comparison between the two algorithms based on geometric considerations.
BibTeX
@inproceedings{filippi2010optimism,
  author = {Sarah Filippi and Olivier Cappé and Aurélien Garivier},
  title = {{Optimism in reinforcement learning and Kullback-Leibler divergence}},
  booktitle = {Allerton},
  year = {2010},
  url = {https://openreview.net/forum?id=5jrbd0nqsf},
}
Figure