Source-linked AI summary
Planning to Be Surprised: Optimal Bayesian Exploration in Dynamic Environments
Yi Sun, Faustino Gomez, Juergen Schmidhuber
TL;DR
The paper asks whether an agent can choose actions optimally while exploring an initially unknown environment. It formulates exploration as Bayesian inference with Shannon information gain and derives a curiosity-value policy that maximizes expected cumulative information gain. For finite MDPs, it establishes optimality of a dynamic-programming approximation, while noting that exact planning becomes infeasible for long horizons.
Problem
The paper asks how an agent should choose actions to accumulate knowledge about an unknown environment as quickly as possible.
Method
The paper models learning through Bayesian inference and Shannon information gain, then selects actions using curiosity Q-values and backward dynamic programming.
Results
The paper shows that an optimal policy maximizes cumulative expected information gain, and establishes the optimality of dynamic-programming approximation in finite MDPs.
Takeaways & Limitations
Optimal Bayesian exploration provides a theoretically grounded basis for exploration strategies in dynamic environments and finite MDPs.
Takeaways & Limitations
Exact curiosity planning has complexity O((n_o n_a)^τ), making large look-ahead horizons infeasible and requiring approximation heuristics in practice.
Abstract
from arXiv · showhide
To maximize its success, an AGI typically needs to explore its initially unknown world. Is there an optimal way of doing so? Here we derive an affirmative answer for a broad class of environments.
1 Introduction
The paper asks how an agent should choose actions to accumulate knowledge about an unknown environment efficiently. It develops an optimal Bayesian exploration framework and applies it to finite MDPs.
- An agent explores an unknown environment by observing outcomes, taking actions, and incrementally building an environmental model.
- The central question is how to choose actions so that knowledge about the environment accumulates as quickly as possible.
- The paper measures learning progress with Shannon information gain and derives action choices that maximize cumulative expected information gain.
- For finite MDPs, the paper shows theoretically and experimentally that optimal Bayesian exploration can be approximated by solving sequential dynamic programming problems.
2 Preliminaries
The framework represents environmental uncertainty probabilistically, updates beliefs from sequential observations, and measures learning through information gain. Expected information gain is decomposed across action-observation steps, supporting a curiosity-based planning formulation.
- The agent interacts in discrete cycles by taking an action and receiving a sensory observation, with histories recording these action-observation sequences.
- Environmental models are represented by a latent parameter with a prior, while a conditional predictor specifies observations given histories and that parameter.
- Bayesian updating represents the agent’s knowledge after each action-observation pair through the posterior distribution over the environmental parameter.
- Information gained between histories is measured by KL divergence between their posterior distributions, and an additional action-observation pair has its own information gain.
- Information gain is additive in expectation across successive histories, enabling cumulative learning progress to be analyzed over trajectories.
- Expected information gain from an action equals the mutual information between the environmental parameter and the resulting observation, conditioned on the current history and action.
3 Optimal Bayesian Exploration
The paper defines curiosity values recursively and shows that backward planning yields an optimal finite-horizon Bayesian exploration policy. The result depends on expected additivity of KL-based information gain, differs from ordinary reward maximization, and becomes computationally expensive for long horizons.
- Optimal Bayesian Exploration: For a finite remaining horizon, the curiosity Q-value combines immediate expected information gain with the expected future curiosity value after the resulting observation.The policy must balance immediate information gain against the value of the histories reached by each action.
- Optimal Bayesian Exploration: Backward induction selects the action maximizing the curiosity Q-value at each history, producing a policy that maximizes cumulative expected information gain.The construction proceeds backward in the number of remaining actions.
- Finite Time Horizon: For an agent with fixed life span T, following the resulting policy at each time maximizes expected cumulative information gain with respect to the prior.At time t, the policy uses the remaining T−t steps.
- Non-triviality of the Result: The decomposition supporting dynamic planning follows from KL divergence and does not generally hold for other information-gain measures.Thus the optimality argument is tied to the paper’s KL-based formulation.
- Non-triviality of the Result: Information gains are additive only in expectation, so they can serve as reward signals when planning ahead but are not ordinary pathwise additive rewards.The cumulative gain relative to the prior may fluctuate even though each immediate KL-based gain is non-negative.
- The Algorithm: The exact curiosity-value algorithms have complexity O((n_o n_a)^τ), making long-horizon planning infeasible and motivating approximation heuristics.Here n_o and n_a denote the numbers of possible observations and actions.
4 Exploration in Finite Markovian Environment with Dirichlet Priors
The paper models finite Markovian exploration with Dirichlet transition priors and defines curiosity Q-values from expected information gain. It establishes infinite-horizon convergence and shows that a dynamic-programming approximation becomes accurate when the prior counts are large.
- Bayesian model: Finite Markovian environments use Dirichlet priors over transition probabilities, updated through probabilistic inference after observed transitions.The posterior remains Dirichlet because the prior is conjugate to the multinomial transition model.
- Infinite horizon: The infinite-horizon curiosity Q-value exists for every prior, state-action pair, and discount factor γ ∈ [0, 1), with uniform convergence.The finite-horizon sequence is Cauchy, and the convergence error is bounded by gα γ^τ/(1−γ).
- Information gain: The expected information gain of a transition is upper bounded by the gain from observing that transition for the first time.This bound supports convergence because later observations contribute no more information than the initial observation.
- Curiosity Q-value: Curiosity Q-values combine immediate expected information gain with the expected future curiosity value induced by the chosen action.The resulting action choice balances short-term information with information available in subsequent states.
- Approximation: The optimal curiosity Q-value is defined by an infinite recursion that cannot be solved directly, motivating finite-horizon Bellman approximations.The Bellman equation can be solved by dynamic programming in time polynomial in the numbers of states and actions.
- Approximation: When α is large, the dynamic-programming approximation ˜qα is a very good approximation of the optimal qα.The paper states that the approximation error decreases at rate c^-2 under the stated proposition conditions.
5 Experiment
The experiment evaluates four exploration strategies in a two-clique MDP connected by a long corridor. Greedy exploration and the dynamic-programming approximation traverse both cliques, while the DP approximation achieves the strongest cumulative information gain, especially early.
- Setup: The experiment compares random exploration, Q-learning, greedy exploration, and a dynamic-programming approximation of optimal Bayesian exploration.The environment contains two densely connected cliques linked by a long corridor, with randomly generated within-clique transitions.
- Behavior: Greedy exploration and the dynamic-programming approximation move back and forth between the two cliques.Random exploration struggles in the corridor, while Q-learning becomes stuck in the initial clique.
- Results: The dynamic-programming approximation clearly outperforms the other algorithms in cumulative information gain, particularly during early exploration.The comparison is based on the bottom plot of cumulative information gain over time.
- Results: Q-learning gets stuck because the corridor’s deterministic transitions make its information gain fall to virtually zero after several attempts.Its Q-value for entering the corridor consequently becomes lower than the Q-value for moving inside the clique.
6 Related Work
The paper distinguishes its approach from prior exploration work by treating environments whose states change through actions and by deriving exploration from Bayesian principles. It also connects curiosity Q-values to artificial curiosity and intrinsically motivated reinforcement learning.
- Novelty: Unlike much active learning and Bayesian experiment design, the paper studies dynamic environments in which actions change the environmental state.Most of the contrasted work focuses on queries that do not affect the environment.
- Novelty: The paper derives its exploration strategy from first principles rather than applying reinforcement learning heuristically to expected information gain.It formulates curiosity Q-values and emphasizes balancing immediate with long-term expected information gain.
- Connections: The curiosity Q-value connects pure exploration with artificial curiosity and intrinsically motivated reinforcement learning without an external reward signal.The connection follows from the definition of the curiosity Q-value.
7 Conclusion
The paper presents optimal Bayesian exploration for dynamic environments through curiosity Q-values and establishes the optimality of a dynamic-programming approximation in finite MDPs.
- Conclusion: The paper establishes a theoretically sound foundation for exploration strategies based on curiosity Q-values in dynamic environments.The conclusion centers on the principle of optimal Bayesian exploration.
- Conclusion: In the finite MDP case, the dynamic-programming approximation is optimal for the optimal Bayesian exploration strategy.This is the paper’s stated finite-MDP conclusion.