Variational Bayesian Reinforcement Learning with Regret Bounds

By Brendan O'Donoghue. 2018

49 citations recorded by the source corpus.

We consider the exploration-exploitation trade-off in reinforcement learning and we show that an agent imbued with an epistemic-risk-seeking utility function is able to explore efficiently, as measured by regret. The parameter that controls how risk-seeking the agent is can be optimized to minimize regret, or annealed according to a schedule. We call the resulting algorithm K-learning and we show that the K-values that the agent maintains are optimistic for the expected optimal Q-values at each state-action pair. The utility function approach induces a natural Boltzmann exploration policy for which the 'temperature' parameter is equal to the risk-seeking parameter. This policy achieves a Bayesian regret bound of $\tilde O(L^{3/2} \sqrt{SAT})$, where L is the time horizon, S is the number of states, A is the number of actions, and T is the total number of elapsed time-steps. K-learning can be interpreted as mirror descent in the policy space, and it is similar to other well-known methods in the literature, including Q-learning, soft-Q-learning, and maximum entropy policy gradient. K-learning is simple to implement, as it only requires adding a bonus to the reward at each state-action and then solving a Bellman equation. We conclude with a numerical example demonstrating that K-learning is competitive with other state-of-the-art algorithms in practice.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Probabilistic & Bayesian Methods

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

In Reinforcement Learning

In Probabilistic & Bayesian Methods

Citations in the corpus

Conservative Q-Learning for Offline Reinforcement Learning (2020, methodology): “Following [47, 26, 45], we use concentration properties of B̂π to control this error.”
Stochastic matrix games with bandit feedback (2020, methodology): “3 Optimistic posterior estimates via K-learning K-learning is a Bayesian exploration algorithm originally developed for Markov Decisions processes in which the agent computes the value of states and actions using a risk-seeking utility function [28].”
Making Sense of Reinforcement Learning and Probabilistic Inference (2020, methodology): “• k learn: K-learning via ensemble with prior networks (O’Donoghue, 2018; Osband et al., 2018).”
If MaxEnt RL is the Answer, What is the Question? (2019, background): “Equation 1 can also be directly obtained by considering an agent with a risk-seeking utility function [36].”