Is the physical state necessarily hidden?

No. The physical state can be observed while the environment's dynamics remain uncertain.

Is it the same as Thompson sampling?

No. Sampling a possible model and acting according to it is a different decision procedure from fully planning over future belief changes.

Why include beliefs in the state?

They summarize information relevant to predicting outcomes and choosing future actions.

AI Glossary / Probabilistic machine learning / Advanced

Bayes-adaptive Markov decision process

Definition

A Bayes-adaptive Markov decision process is a decision-making model that includes an agent's beliefs about an uncertain environment in its state representation. It plans actions by considering both their rewards and how their outcomes may change beliefs used in future decisions.

What it means

Ordinary planning with a known model asks what to do given the current situation. Bayes-adaptive planning also asks what the agent currently knows about how the environment works. Two agents in the same physical situation may choose differently because they have different evidence about likely outcomes.
This creates a principled way to value learning through action. An action with a lower immediate expected reward may be worthwhile when its observations improve later choices. Whether exploration is worthwhile depends on the prior, possible observations, rewards and time remaining.

How it works

Specify a prior over uncertain model parameters and update it with Bayes' rule as observations arrive. Form an augmented state, often called a hyperstate, containing the physical state and the current posterior belief, or a sufficient representation of the relevant history.
Predictive transitions average over the possible models and also update the belief component. Planning maximizes expected cumulative reward in this augmented process. Exact solutions can be computationally demanding because possible beliefs form a large state space. Bayes-adaptive Monte-Carlo planning is one approach to approximating this planning problem; it is not the definition of the process itself.

Three practical examples

A robot in a simulated warehouse could plan routes while learning uncertain passage reliability. A short exploratory route might help future trips, provided its expected benefit justifies the immediate cost.
An operations researcher could model repeated choices between a familiar process and an unfamiliar alternative. Observed outcomes would update beliefs about the alternative before subsequent choices.
A simulation team could compare policies that use posterior means with policies that anticipate future learning. The comparison would isolate the value of information under explicitly stated assumptions before any operational trial.

Think of it this way

Imagine choosing between a familiar route and a shortcut whose reliability you do not yet know. Trying the shortcut today may teach you something useful for many later journeys. If this is your final journey, that learning has no later travel benefit. The value of the experiment depends on both what it reveals and how many opportunities remain to use the information.

Worked example

Consider an original two-decision, undiscounted toy problem. At each decision, a safe action returns a known reward of 0.55. An uncertain action returns either one or zero. Its fixed success probability is either 0.90 or 0.10, with equal prior probability. Outcomes are independent conditional on that fixed probability. There are no additional costs.
The uncertain action's immediate expected reward is 0.50, so a policy considering only immediate reward chooses the safe action. However, trying the uncertain action first provides evidence. A success gives posterior probability 0.90 to the high-success model, making the next success probability 0.90×0.90+0.10×0.10=0.82. After a failure, that posterior probability is 0.10 and the next success probability is 0.18.
With one decision remaining, choose the uncertain action after success and the safe action after failure. The total expected reward from this learning-aware plan is 0.50 + 0.50×0.82 + 0.50×0.55 = 1.185.
Choosing safe first reveals nothing about the uncertain action. The best final choice remains safe, yielding 0.55+0.55=1.10. Thus exploration is preferable over this two-decision horizon under the stipulated assumptions, even though its immediate expected reward is lower. With only one decision, safe is preferable. This small bandit-style special case illustrates belief-dependent planning; it does not establish which actions are appropriate in any real business environment.

Illustrative case study

Fictional warehouse operator Rowan Dispatch is evaluating routing policies in a simulator. Some passage times are uncertain but assumed stable during each simulated run. The team specifies alternative models and priors, then lets simulated observations update the planner's beliefs.
It compares short and long planning horizons to see when exploratory trips are worthwhile. It also tests what happens when the assumed model family omits a type of delay observed in historical data. Its report distinguishes performance under the stipulated simulator from evidence about deployment. This fictional case illustrates a model-testing process, not a claim of achieved time savings or a recommendation to experiment on live operations.

Common misconceptions and mistakes

“Bayes-adaptive means the environment must change over time.” A fixed but unknown environment is sufficient; the agent's beliefs change as it learns.
“Planning with the average model is equivalent.” A fixed average-model calculation can omit how observations change future beliefs and actions.
“Bayes-optimal means best under every possible reality.” Optimality is relative to the specified prior, model, reward objective and horizon or discounting assumptions.
“A correct belief update solves the planning problem.” The agent must still evaluate future decisions in a potentially enormous augmented state space.
“Exploration is always valuable.” Its information may arrive too late, cost too much or fail to affect useful later choices.

Business use

Use this concept to assess proposals for systems that learn while making repeated decisions. Require clarity about which parameters are uncertain, what observations update them and how the reward reflects the organization's purpose. Test prior sensitivity and model misspecification in simulations. Compare the benefit of planning for learning against its computational cost and against simpler policies. Keep claims about theoretical optimality separate from evidence about a particular implementation.

Check your understanding

What changes after the toy example's first success?

Answer: belief in the high-success model rises to 0.90, and the next predicted success probability becomes 0.82.

Why does safe-first yield 1.10?

Answer: it provides no information, so safe remains the best final action.

Would exploration still be preferred with one decision remaining?

Answer: no; its expected immediate reward is 0.50 versus 0.55 for safe.

Related terms

Markov decision process
Bayesian reinforcement learning
Belief state
Posterior predictive distribution
exploration-exploitation trade-off
value of information
Bayes-adaptive Monte-Carlo planning

Learn next

Work through a Bayesian update for an uncertain success rate. Then compare a policy using only current expected rewards with a finite-horizon policy that anticipates learning from its actions.

Finite horizon

Sources

Guez, A., Silver, D., and Dayan, P. Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search, 2012, especially Section 2: https://acguez.github.io/files/guez_nips2012.pdf The two-decision example and fictional warehouse case are original illustrations.

Previous: Bayer pattern Next: Bayes classifier