Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning

By Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, Ronald Ortner. 2018

129 citations recorded by the source corpus.

We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound $c$ on the span of the optimal bias function is known. For an MDP with $S$ states, $A$ actions and $\Gamma \leq S$ possible next states, we prove a regret bound of $\widetilde{O}(c\sqrt{\Gamma SAT})$, which significantly improves over existing algorithms (e.g., UCRL and PSRL), whose regret scales linearly with the MDP diameter $D$. In fact, the optimal bias span is finite and often much smaller than $D$ (e.g., $D=\infty$ in non-communicating MDPs). A similar result was originally derived by Bartlett and Tewari (2009) for REGAL.C, for which no tractable algorithm is available. In this paper, we relax the optimization problem at the core of REGAL.C, we carefully analyze its properties, and we provide the first computationally efficient algorithm to solve it. Finally, we report numerical simulations supporting our theoretical findings and showing how SCAL significantly outperforms UCRL in MDPs with large diameter and small span.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “(See (Jaksch et al., 2010; Bartlett & Tewari, 2009; Fruit et al., 2018; Lakshmanan et al., 2015; Pirotta et al., 2015; 2013) and references therein for the OFU principle in ﬁnite-state MDPs.) The main novelty here is to optimize the lower bound directly, without explicitly building any conﬁdence…”
Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function (2019, background): “The agent executes the optimal policy of the best MDP in the conﬁdence set [Bartlett and Tewari, 2009, Jaksch et al., 2010, Maillard et al., 2011, Fruit et al., 2018a].”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, background): “RL in stationary (discounted and un-discounted reward) MDPs has been widely studied in (Burnetas & Katehakis, 1997; Bartlett & Tewari, 2009; Jaksch et al., 2010; Agrawal & Jia, 2017; Fruit et al., 2018a;b; Sidford et al., 2018b;a; Wang, 2019; Zhang & Ji, 2019; Fruit et al., 2019; Wei et al., 2019).”
Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, methodology): “For a discussion of various transition parameters used in the literature we refer to Jaksch et al. (2010) and Bartlett and Tewari (2009).”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, unknown): “Few remarks are in order: • the problem independent bound (D or H) is replaced by a problem dependent quantity as in (Bartlett & Tewari, 2009; Fruit et al., 2018)”