Optimism in Reinforcement Learning Based on Kullback-Leibler Divergence

Sarah Filippi, Olivier Cappé, Aurélien Garivier

Abstract

We consider model-based reinforcement learning in finite Markov Decision Processes (MDPs), focusing on 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, 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.

Introduction

In model-based reinforcement learning (RL), an agent interacts with an unknown environment to learn transition probabilities and rewards. A standard approach to balancing exploration and exploitation is the Optimism in the Face of Uncertainty (OFU) principle. This strategy directs the agent to act according to the most favorable version of the environment that remains statistically plausible given the observed data.

The current state-of-the-art algorithm, UCRL2, implements this by using the $L_1$ norm (total variation distance) to define the set of plausible models. While theoretically sound, the $L_1$ approach suffers from several practical limitations, including policy instability due to discontinuities and a tendency to "hope" for impossible transitions in sparse environments. This paper introduces KL-UCRL, which replaces the $L_1$ norm with the Kullback-Leibler (KL) divergence, leveraging its superior geometric properties to enhance learning efficiency.

The Pitfalls of $L_1$ Optimism

The authors identify three primary issues with using $L_1$ distance to define confidence sets:

  1. Discontinuity: Small updates to empirical estimates can cause the optimistic model to jump abruptly, leading to unstable policies.
  2. Observation Incompatibility: The $L_1$ ball can occasionally include models that assign zero probability to transitions that have actually been observed.
  3. The "Ghost" Transition Problem: In MDPs with low connectivity (sparse graphs), $L_1$ optimism often maintains a high "exploration bonus" for transitions to high-value states long after evidence suggests those transitions are impossible. This leads to excessive regret in environments with restricted movement.

The KL-UCRL Algorithm

KL-UCRL addresses these issues by utilizing the KL divergence to constrain the optimistic model. The core of the algorithm involves a modified Extended Value Iteration. At each step, the agent solves the following optimization problem to find a transition probability vector $q$ that maximizes the expected future value $V$, subject to a KL-divergence constraint around the empirical estimate $p$:

$$\max_q V'q \quad \text{s.t.} \quad KL(p, q) \leq \epsilon$$

Efficient Optimization via Duality

While maximizing a linear function over a KL-ball appears to be a complex non-linear optimization, the authors demonstrate that it can be reduced to a simple one-dimensional root-finding problem. By applying Lagrangian duality, the optimal $q$ can be found by solving a convex function using Newton’s method. This ensures that KL-UCRL is computationally efficient, with a runtime comparable to the sorting-based methods used in $L_1$ algorithms.

Geometric and Theoretical Insights

The advantage of KL-UCRL lies in the geometry of the probability simplex. Unlike the $L_1$ ball, which is a polytope with sharp corners, the KL ball is smooth. This smoothness ensures that the optimistic model evolves continuously as data is collected. Furthermore, KL divergence is deeply rooted in large deviation theory; it naturally accounts for the fact that the probability of unobserved events should decay exponentially as more data is gathered. This allows KL-UCRL to "prune" impossible transitions much faster than $L_1$-based methods.

From a theoretical standpoint, the authors derive new concentration inequalities for the KL divergence. They prove that KL-UCRL achieves a regret bound of $O(D|X|\sqrt{|A|T \log(\dots)})$, where $D$ is the MDP diameter, $|X|$ is the state space, and $|A|$ is the action space. This matches the near-optimal theoretical guarantees of UCRL2 while providing superior empirical performance.

Experimental Results

The algorithm was evaluated on several benchmarks designed to test exploration efficiency:

  • RiverSwim: A classic environment requiring systematic exploration against a current. KL-UCRL demonstrated significantly lower regret than UCRL2.
  • SixArms: A multi-armed bandit-style MDP where the agent must identify the best action among several competitors.
  • Random Sparse MDPs: In environments where states have limited connectivity, KL-UCRL outperformed UCRL2 by a wide margin. It effectively avoided the "ghost transition" problem, stopping exploration of impossible paths much earlier than its $L_1$ counterpart.

Conclusion

KL-UCRL represents a significant refinement of optimistic reinforcement learning. By replacing the $L_1$ norm with the more geometrically appropriate KL divergence, the algorithm achieves greater stability and faster convergence, particularly in sparse environments. While currently limited to finite state spaces, the success of KL-based optimism suggests promising future applications in continuous control and more complex RL architectures.

Summary updated

Abstract

We consider model-based reinforcement learning in finite Markov De- cision Processes (MDPs), focussing on so-called optimistic strategies. In MDPs, optimism can be implemented by carrying out extended value it- erations under a constraint of consistency with the estimated model tran- sition 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 ef- ficient 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 com- parison 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 Based on Kullback-Leibler Divergence}},
  booktitle = {Allerton},
  year = {2010},
  url = {https://openreview.net/forum?id=5jrbd0nqsf},
}
Figure