Optimism in reinforcement learning and Kullback-Leibler divergence

By Sarah Filippi, Olivier Capp'e, Aurélien Garivier. 2010

111 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Kullback–Leibler upper confidence bounds for optimal sequential allocation (2012, methodology): “…KL-UCB index requires solving a convex program (maximizing a linear function on the probability simplex under Kullback–Leibler constraints) for which we provide in the supplemental article [Capp´e et al. (2013), Appendix C.1] a simple algorithm inspired by Filippi, Capp´e and Garivier (2010).”
Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs (2018, methodology): “, 2010) or (Filippi et al., 2010), the right way to control it is however to sum this contribution over all episodes and make appear a martingale difference sequence of T deterministic terms, bounded by the deterministic quantity D, since S(b̃k) 6 D.”