Variational Bayesian Reinforcement Learning with Regret Bounds

Brendan O'Donoghue

Introduction

This paper introduces K-learning, a reinforcement learning algorithm that utilizes a novel "Knowledge-value" (K-value) to seamlessly combine expected rewards with epistemic uncertainty. By endowing an agent with a risk-seeking utility function, the authors derive a soft-max Bellman operator. This provides the first formal proof that maximum-entropy and soft-max policies can achieve near-optimal Bayesian regret bounds, bridging the gap between practical deep RL heuristics and rigorous theoretical guarantees.

The Exploration-Exploitation Dilemma

In Reinforcement Learning (RL), agents constantly face the exploration-exploitation dilemma: should they stick to known, rewarding actions (exploitation) or try something new to potentially discover better rewards (exploration)?

While Bayesian methods like Thompson Sampling are theoretically powerful for managing this trade-off, they are often computationally expensive because they require sampling entire environments from a posterior distribution. Conversely, "soft-max" or "maximum-entropy" RL methods are highly popular in deep learning for their practical performance and smooth exploration. However, they have historically lacked rigorous theoretical guarantees regarding regret—the cumulative loss compared to an optimal policy.

This paper seeks to provide a principled Bayesian foundation for these popular soft-max heuristics, proving they are mathematically sound strategies for managing uncertainty rather than just convenient tricks.

Methods: Deriving K-Learning

The core innovation of the paper is the derivation of K-values (Knowledge-values) through a new Optimistic Bellman Operator.

  1. Risk-Seeking Utility: The agent is given an exponential, risk-seeking utility function. In this context, "risk" refers to epistemic uncertainty (what the agent doesn't know about the environment). A risk-seeking agent naturally gravitates toward uncertain states.
  2. The K-Value: The K-value acts as the "certainty equivalent" of future rewards under this utility. It elegantly compresses both the expected reward and the uncertainty into a single scalar value.
  3. Optimistic Bellman Operator: The authors derive a modified Bellman equation where the standard "hard-max" is replaced by a soft-max, and an exploration "bonus" term is added based on the inverse visitation count of a state-action pair.
  4. Boltzmann Policy: The agent acts according to a Boltzmann distribution over these K-values. The "temperature" ($\tau$) controls the balance between exploration and exploitation. The paper provides two methods for setting this temperature: a fixed schedule or a more sophisticated convex optimization approach.

Experimental Environment: The DeepSea MDP

The algorithm was evaluated on the DeepSea Markov Decision Process (MDP), a classic "needle in a haystack" environment.

The DeepSea MDP environment, requiring a specific sequence of actions to find the reward.

DeepSea is a grid-like environment of depth $L$. To obtain any reward, the agent must execute a highly specific sequence of $L$ "right" actions. A single "left" action results in zero reward and immediately ends the episode. This environment is specifically designed to defeat simple "dithering" exploration strategies (like $\epsilon$-greedy), which would take an exponential amount of time ($2^L$) to stumble upon the reward.

Key Insights

  • Soft-max as a First Principle: The soft-max operator, often used as an ad-hoc heuristic to smooth out learning, emerges naturally from the mathematics when assuming an agent wants to maximize a risk-seeking exponential utility.
  • Uncertainty as a Bonus: The K-learning update rule explicitly adds an exploration bonus that scales with the inverse of the visitation count ($1/n$). This establishes a clear bridge to "Optimism in the Face of Uncertainty" (OFU) methods.
  • Stationary Randomized Strategies: Unlike Thompson Sampling, which changes its deterministic policy every episode based on a new sample, K-learning maintains a single, slowly-evolving stochastic policy based on the current posterior.

Key Results

Performance of K-learning compared to baseline algorithms on the DeepSea environment as size increases.
  • Theoretical Bound: The paper proves a Bayes regret bound of $\tilde{O}(L^{3/2}\sqrt{SAT})$, where $L$ is the horizon, $S$ is the number of states, $A$ is the number of actions, and $T$ is total time. This matches the best-known bounds for Thompson Sampling.
  • Empirical Performance: In the DeepSea experiments, K-learning scaled gracefully with the depth of the environment. It matched the efficiency of Thompson Sampling and vastly outperformed standard Q-learning and soft-Q learning, which failed as the environment grew larger.
  • Optimization vs. Schedule: The "optimized" temperature variant performed slightly better than the fixed schedule, demonstrating the value of tuning the exploration rate dynamically to the specific state of the agent's knowledge.

Limitations and Future Work

Currently, K-learning is model-based, meaning it requires estimating the full transition function of the MDP, which can be memory-intensive for very large state spaces. Additionally, the proofs and experiments focus on tabular MDPs. While the authors suggest that K-values could be represented by deep neural networks, a "Deep K-learning" version remains untested. Future work will likely explore an online, model-free version of K-learning, which would be more practical for high-dimensional, real-world problems.

Summary updated

Abstract

We consider the exploration-exploitation trade-off in reinforcement learning and show that an agent endowed with an exponential epistemic-risk-seeking utility function explores efficiently, as measured by regret. The state-action values induced by the exponential utility satisfy a Bellman recursion, so we can use dynamic programming to compute them. We call the resulting algorithm K-learning (for knowledge) and the risk-seeking utility ensures that the associated state-action values (K-values) are optimistic for the expected optimal Q-values under the posterior. The exponential utility function induces a Boltzmann exploration policy for which the 'temperature' parameter is equal to the risk-seeking parameter and is carefully controlled to yield a Bayes regret bound of $\tilde O(L^{3/2} \sqrt{S A T})$, 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 timesteps. We conclude with a numerical example demonstrating that K-learning is competitive with other state-of-the-art algorithms in practice.
BibTeX
@inproceedings{odonoghue2021variational,
  author = {Brendan O'Donoghue},
  title = {{Variational Bayesian Reinforcement Learning with Regret Bounds}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=EaLBPnRtggY},
}
Figure