Variance-Based Rewards for Approximate Bayesian Reinforcement Learning

By Jonathan Sorg, Satinder Singh, Richard L. Lewis. 2010

72 citations recorded by the source corpus.

The explore{exploit dilemma is one of the central challenges in Reinforcement Learning (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over environments; however, full Bayesian planning is intractable. Planning with the mean MDP is a common myopic approximation of Bayesian planning. We derive a novel reward bonus that is a function of the posterior distribution over environments, which, when added to the reward in planning with the mean MDP, results in an agent which explores efficiently and effectively. Although our method is similar to existing methods when given an uninformative or unstructured prior, unlike existing methods, our method can exploit structured priors. We prove that our method results in a polynomial sample complexity and empirically demonstrate its advantages in a structured exploration task.

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

Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “Bayesian algorithms have the advantage of being able to incorporate prior information about the problem and, as we show in the numerical experiments, they tend to perform better than nonBayesian approaches in practice [17, 51, 49].”
Neural Predictive Belief Representations (2018, background): “…can also be useful for learning policies that efﬁciently explore partially observable environments by acting to reduce uncertainty on the agent’s belief (as in Bayes-optimal exploration; Wilson et al., 2007; Kolter & Ng, 2009; Sorg et al., 2010; Asmuth & Littman, 2012; Ghavamzadeh et al., 2015).”
UCB EXPLORATION VIA Q-ENSEMBLES (2018, background): “[20] models the environment and constructs exploration bonus from variance of model parameters.”
Reward Design via Online Gradient Ascent (2010, methodology): “For example, work on reward shaping [11] has shown how to modify rewards to accelerate learning without altering the optimal policy, and PAC-MDP methods [5, 20] including approximate Bayesian methods [7, 19] add bonuses to the objective reward to achieve optimism under uncertainty.”
Near-Optimal BRL using Optimistic Local Transitions (2012, methodology): “Some of them solve the MDP generated by the expected model (at some stage) with an added exploration reward which favors transitions with lesser known models, as in r-max (Brafman & Tennenholtz, 2003), beb (Kolter & Ng, 2009), or with variance based rewards (Sorg et al., 2010).”
Cooperative Multi-agent Control Using Deep Reinforcement Learning (2017, background): “The concept of reward shaping [26] involves modifying rewards to accelerate learning without changing the optimal policy and approximate Bayesian methods that add bonus reward to the objective reward to achieve optimism under uncertainty [17, 35].”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “A number of prior methods also examine various techniques for using models and prediction to incentivize exploration [12, 13, 14, 15].”
Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search (2012, unknown): “…Dearden’s Maze BAMCP 387.6 ± 1.5 72.9 ± 3 32.7 ± 3 965.2 ± 73 BFS3 [2] 382.2 ± 1.5 66 ± 5 10.4 ± 2 240.9 ± 46 SBOSS [5] 371.5 ± 3 59.3 ± 4 21.8 ± 2 671.3 ± 126 BEB [18] 386 ± 0 67.5 ± 3 10 ± 1 184.6 ± 35 Bayesian DP* [23] 377 ± 1 - - - Bayes VPI+MIX* [8] 326 ± 31 - - 817.6 ± 29 IEQL+* [20] 264”
Reward Estimation for Variance Reduction in Deep Reinforcement Learning (2018, background): “Other works in the RL setting augment rewards via shaping mechanisms [22, 23]; for example, to make robot learning easier with sparse rewards.”
Approximate real-time optimal control based on sparse Gaussian process models (2014, unknown): “in [27] and [28].”
Reinforcement learning with limited reinforcement: using Bayes risk for active learning in POMDPs (2008, unknown): “More recent work in Bayesian MDPs have provided a formal char acte ization of the sample complexity required to achieve near-optimal r eward [38, 39, 40], including for cases where the learner has access to a teacher (similar to an oracle to achieve efficient uses the notion of teacher (similar to a”
An Optimistic Posterior Sampling Strategy for Bayesian Reinforcement Learning (2013, methodology): “These two conditions are easily satisfied in the context of finite state and action space MDPs. Inspired from the principle of the Bayes-UCB algorithm proposed in the context of multi-armed bandit problems [10], our strategy works as follows: at each time-step, a pool of MDPs is drawn from the…”
Bounded Optimal Exploration in MDP (2016, methodology): “MBIE and VBE work reasonably if we discard the theoretical guarantee.”
Reinforcement Learning with Limited Reinforcement : Using Bayes Risk for Active Learning in POMDPs Finale (2012, background): “More recent work in Bayesian MDPs have provided a formal char acte ization of the sample complexity required to achieve near-optimal r eward [38, 39, 40], including for cases where the learner has access to a teacher (similar to an oracle to achieve efficient uses the notion of teacher (similar to a”
Convex Optimization: Algorithms and Complexity (2015, unknown): “Sorg et al, [Sorg et al., 2010] deals with the issue by expressing the bonus over the variance of the unknown parameters (including the unknown rewards), as in Eq.”