Variance Reduction Methods for Sublinear Reinforcement Learning

By Sham M. Kakade, Mengdi Wang, Lin F. Yang. 2018

36 citations recorded by the source corpus.

This work considers the problem of provably optimal reinforcement learning for (episodic) finite horizon MDPs, i.e. how an agent learns to maximize his/her (long term) reward in an uncertain environment. The main contribution is in providing a novel algorithm --- Variance-reduced Upper Confidence Q-learning (vUCQ) --- which enjoys a regret bound of $\widetilde{O}(\sqrt{HSAT} + H^5SA)$, where the $T$ is the number of time steps the agent acts in the MDP, $S$ is the number of states, $A$ is the number of actions, and $H$ is the (episodic) horizon time. This is the first regret bound that is both sub-linear in the model size and asymptotically optimal. The algorithm is sub-linear in that the time to achieve $\epsilon$-average regret (for any constant $\epsilon$) is $O(SA)$, which is a number of samples that is far less than that required to learn any (non-trivial) estimate of the transition model (the transition model is specified by $O(S^2A)$ parameters). The importance of sub-linear algorithms is largely the motivation for algorithms such as $Q$-learning and other "model free" approaches. vUCQ algorithm also enjoys minimax optimal regret in the long run, matching the $\Omega(\sqrt{HSAT})$ lower bound. Variance-reduced Upper Confidence Q-learning (vUCQ) is a successive refinement method in which the algorithm reduces the variance in $Q$-value estimates and couples this estimation scheme with an upper confidence based algorithm. Technically, the coupling of both of these techniques is what leads to the algorithm enjoying both the sub-linear regret property and the (asymptotically) optimal regret.

Subfields: Artificial Intelligence, Control and Systems Engineering

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 Control and Systems Engineering

Citations in the corpus

Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “Another line of work of model-based reinforcement learning is to learn a dynamic model in a hidden representation space, which is especially necessary for pixel state spaces (Kakade et al., 2018; Dann et al., 2017; Szita & Szepesvári, 2010; Kearns & Singh, 2002; Jaksch et al., 2010).”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, background): “There is a substantial body of work on tabular reinforcement learning [2, 16, 19, 5, 21, 10].”
Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function (2019, background): “Recently, Kakade et al. [2018] and Zanette and Brunskill [2019] achieved the same regret bound of ˜ O ( √ SAHT ) by learning a precise value function to predict the best future reward of current state.”
Mo' States Mo' Problems: Emergency Stop Mechanisms from Observation (2019, background): “[15] for an overview of state-of-the-art regret bounds in episodic MDPs.”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “For tabular H-horizon MDP with S states and A actions, there have been results on model-based methods (e.g., Jaksch et al. 2010; Osband et al. 2014; Azar et al. 2017; Dann et al. 2017; Agrawal & Jia 2017; Dann et al. 2018; Kakade et al. 2018), and on modelfree methods (e.”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, background): “Compared to the existing literature, our work • Maintains state of the art worst-case guarantees (Azar et al., 2017; Kakade et al., 2018), • Improves on the regret bounds of (Bartlett & Tewari, 2009; Fruit et al., 2018) when restricted to the episodic setting and without the need of domain…”
Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition (2020, methodology): “H to the regret analysis in [Azar et al., 2017] and [Kakade et al., 2018].”