Decision making under uncertainty: belief states, POMDPs, and value of information

Why this subject matters now

For a long time the theory of acting under partial observability was a beautiful cul-de-sac: the partially observable Markov decision process (POMDP) was known to be the right model and known to be computationally intractable in the worst case, so practitioners hand-designed state estimators and controllers and hoped the seams did not show. Three developments moved the frontier. Point-based value iteration, starting with Pineau, Gordon and Thrun in 2003 and maturing into SARSOP by 2008, showed that anchoring the value function to the belief points a good policy actually reaches turns an intractable problem into an approximable one for many real domains. Online tree search, POMCP in 2010 and DESPOT in 2013, showed that a planner can act well without ever representing the whole value function, by searching forward from the current belief with sampled particles. And the same search machinery, Monte Carlo tree search built on the UCB1 bandit algorithm, became the engine behind the strongest game-playing systems, which turned a niche planning technique into something every applied researcher is expected to understand.

In parallel, the question "what should I measure, and is it worth the cost" acquired a precise answer through the value of information, and the question "where should I sample an expensive black-box function next" acquired one through Bayesian optimization. Bayesian optimization is now the default way to tune the hyperparameters of a machine-learning system, to design experiments in the physical sciences, and to optimize simulators that cost hours per evaluation, and its acquisition functions, Expected Improvement chief among them, are direct descendants of the value-of-information calculus. A practitioner today is expected to know that state estimation and control are one problem when the state is hidden, to reach for the value of information before commissioning an expensive sensor, and to know why Expected Improvement balances exploitation against exploration without any tuning knob. This page derives all of it. It assumes the Markov decision process and dynamic programming, which are developed in the companion page on reinforcement learning fundamentals, and it assumes basic state-space search and Bayes-net inference, developed in AI principles and probabilistic graphical models; it owns the partially observed case, the depth of tree search, the value of information, and Gaussian-process decision making.

Utility theory: why a rational agent maximizes expected utility

Before we can say what a good decision is, we need a scalar to maximize. That the scalar exists at all, and that it should be maximized in expectation rather than through some other functional of the outcome distribution, is not an assumption; it is a theorem about preferences. The setup is a set of deterministic outcomes and a set of lotteries, which are probability distributions over outcomes. A rational agent has a preference relation \( \succeq \) over lotteries, read "is at least as good as." The von Neumann-Morgenstern theorem states that if this relation satisfies four axioms, there is a real-valued utility \( u \) on outcomes such that one lottery is preferred to another exactly when it has the higher expected utility.

The four axioms

The axioms are constraints on \( \succeq \). Completeness: for any two lotteries \( p, q \), either \( p \succeq q \) or \( q \succeq p \) (the agent can always compare). Transitivity: if \( p \succeq q \) and \( q \succeq r \) then \( p \succeq r \). Continuity: if \( p \succeq q \succeq r \), there is a probability \( \alpha \in [0,1] \) such that the agent is indifferent between \( q \) and the mixed lottery that yields \( p \) with probability \( \alpha \) and \( r \) with probability \( 1-\alpha \), written \( q \sim \alpha p + (1-\alpha) r \). Independence: for any lottery \( s \) and any \( \alpha \in (0,1] \), \( p \succeq q \) if and only if \( \alpha p + (1-\alpha) s \succeq \alpha q + (1-\alpha) s \); mixing both sides with the same third lottery does not reverse the preference. Independence is the axiom that does the real work and the one most often questioned empirically, because human preferences violate it (the Allais paradox); the theorem is a statement about what consistency requires, not a description of people.

The representation theorem, constructively

The proof is a construction, and the construction is the reason the theorem feels forced once you accept the axioms. Assume a best outcome \( B \) and a worst outcome \( W \) with \( B \succ W \) (finite outcome set; the general case is a limiting argument). For any outcome \( x \) with \( B \succeq x \succeq W \), continuity gives a number \( u(x) \in [0,1] \) such that

Define this \( u(x) \) to be the utility of \( x \); it is the probability of the best outcome in a standard reference lottery the agent finds exactly as good as \( x \). Now take any lottery \( p \) that yields outcome \( x_i \) with probability \( p_i \). Independence lets us substitute, inside \( p \), each outcome \( x_i \) by its equivalent reference lottery \( u(x_i) B + (1-u(x_i)) W \) without changing the agent's valuation, one outcome at a time. After all substitutions, \( p \) has been reduced to a lottery over only \( B \) and \( W \), and by the rules of compound probability the total weight on \( B \) is

So every lottery is equivalent to a single reference lottery whose probability of \( B \) equals its expected utility. Finally, a reference lottery with more weight on \( B \) is preferred (this is monotonicity, which independence and the axioms imply). Therefore \( p \succeq q \iff \E_p[u] \ge \E_q[u] \), which is the claim. The utility is unique up to a positive affine transformation \( u \mapsto a u + b \) with \( a > 0 \), because the choice of \( B \) and \( W \) fixes only a scale and an origin. Two consequences matter downstream: the object an agent maximizes is an expectation of a utility, not the utility of an expectation, and the utility function itself, not the reward in units of money or time, is what a POMDP or a decision diagram should carry.

Risk aversion is concavity

The shape of \( u \) encodes attitude to risk. Consider a lottery \( p \) over monetary outcomes and compare its expected utility \( \E_p[u(X)] \) to the utility of its expected value \( u(\E_p[X]) \). Jensen's inequality says that if \( u \) is concave then \( \E_p[u(X)] \le u(\E_p[X]) \): the agent values the gamble at no more than its expected cash value, which is the definition of risk aversion. Concave utility is risk-averse, convex is risk-seeking, linear is risk-neutral. The certainty equivalent \( \mathrm{CE}(p) \) is the sure amount the agent finds exactly as good as the gamble,

and the risk premium is \( \E_p[X] - \mathrm{CE}(p) \ge 0 \) for a concave \( u \), the amount of expected value the agent will forgo to remove the risk. The local strength of risk aversion is captured by the Arrow-Pratt coefficient of absolute risk aversion \( A(x) = -u''(x)/u'(x) \), which is invariant to the affine rescaling that leaves preferences unchanged. Constant absolute risk aversion (CARA) corresponds to the exponential utility \( u(x) = -e^{-A x} \), whose \( A(x) = A \) is flat; the square-root utility \( u(x) = \sqrt{x} \) has \( A(x) = 1/(2x) \), decreasing in wealth, which matches the intuition that a fixed gamble frightens a poor agent more than a rich one.

Influence diagrams and how to evaluate them

A decision problem with structure is drawn as an influence diagram, which extends a Bayesian network with two new node types: rectangular decision nodes, whose values the agent chooses, and a diamond utility node, whose value the agent wants to maximize in expectation. Chance nodes are as in a Bayes net. Arcs into a chance or utility node mean probabilistic or functional dependence; arcs into a decision node are informational, meaning the parent's value is observed before the decision is made. The graphical-models page treats the modeling side; here we care about evaluation.

   Disease (chance) ─────────────> [ Utility ]
        │                              ^
        v                              │
   Test result ·······> ┌──────────┐  │
     (informational)    │  Treat?   │──┘
                        └──────────┘  (decision)

The normative solution is a policy: a mapping from each decision node's observed parents to an action that maximizes expected utility, called the maximum-expected-utility (MEU) policy. Evaluating a single-decision diagram is the same sum-product machinery used for Bayes-net inference, with one \( \max \) interleaved into the variable-elimination ordering. Concretely, eliminate every chance variable that is not observed at decision time by summing it out against the utility factor; this leaves an expected-utility table indexed by the decision and its observed parents; then take the \( \arg\max \) over the decision for each configuration of the observed parents. The ordering constraint is the subtle part: a chance variable observed before the decision must be eliminated after the \( \max \), because the policy is allowed to depend on it, whereas a variable never observed is summed out before the \( \max \). With several decisions the eliminations and maxima interleave in the order the information becomes available, which is exactly dynamic programming on the decision sequence. The payoff of the diagram view is that value of information, developed below, falls out of it for free: to price an observation, add the informational arc and recompute the MEU.

The POMDP model

A POMDP is a Markov decision process in which the agent does not see the state. Formally it is the tuple \( (\mathcal{S}, \mathcal{A}, \mathcal{O}, T, Z, R, \gamma) \): a state space \( \mathcal{S} \), an action space \( \mathcal{A} \), an observation space \( \mathcal{O} \), a transition model \( T(s' \mid s, a) = P(s_{t+1}=s' \mid s_t=s, a_t=a) \), an observation model \( Z(o \mid s', a) = P(o_{t+1}=o \mid s_{t+1}=s', a_t=a) \), a reward \( R(s,a) \), and a discount \( \gamma \in [0,1) \). The dynamics are Markov in the true state, exactly as in a fully observed MDP, but the agent never observes \( s_t \). It acts, the world transitions, and it receives an observation \( o_{t+1} \) that is a noisy, partial function of the new state. Everything hard about POMDPs comes from this one change: a policy cannot be a function of the state, because the state is unknown; it must be a function of the entire history of actions and observations.

The belief state and the belief-state MDP

The history grows without bound, so a policy over histories is not directly usable. The key reduction, due to Astrom in 1965, is that the history can be summarized without loss by a sufficient statistic: the posterior distribution over the current state given everything seen so far, called the belief. Write \( b_t(s) = P(s_t = s \mid a_0, o_1, \ldots, a_{t-1}, o_t) \), a point on the probability simplex \( \Delta(\mathcal{S}) \). The belief is a sufficient statistic for the history: the optimal action depends on the history only through \( b_t \), because the future dynamics and rewards depend on the past only through the current state distribution, which is what \( b_t \) is. This turns the POMDP into a fully observed MDP whose state is the belief, called the belief-state MDP. Its state space is the continuous simplex \( \Delta(\mathcal{S}) \), its actions are the original actions, its reward is the belief-expected reward \( \rho(b, a) = \sum_s b(s) R(s,a) \), and its transition is deterministic given the observation: taking \( a \) in belief \( b \) and receiving \( o \) sends \( b \) to a new belief \( b' \) computed by the filter below. The reformulation is exact; the difficulty has been relocated from "state is hidden" to "state space is a continuous simplex."

Deriving the belief update (the Bayesian filter)

The belief update is Bayes' rule applied to one step of the dynamics. Start from belief \( b \), take action \( a \), and receive observation \( o \). We want \( b'(s') = P(s' \mid b, a, o) \). Condition on the previous state as a nuisance variable and apply Bayes' rule with \( o \) as the evidence:

The first factor is the observation model \( Z(o \mid s', a) \). The second is the one-step predicted state distribution, obtained by pushing the belief through the transition model,

which is the standard marginalization over the unknown previous state, valid because \( s_{t+1} \perp \text{history} \mid (s_t, a_t) \) by the Markov property. The denominator is the probability of seeing \( o \) at all, a normalizing constant that makes \( b' \) sum to one:

Putting the pieces together, the filter is a predict step (transition) followed by a correct step (observation) followed by renormalization:

This is the discrete-state analogue of the Kalman filter and the same object as the forward pass of a hidden Markov model; the temporal-models machinery in the graphical-models page and the particle filter in AI principles are the approximate versions used when \( \mathcal{S} \) is too large to enumerate. The denominator, the observation likelihood, is exactly the weight a particle filter would assign, which is why importance-weighted particles approximate this update.

The value function over belief space is piecewise linear and convex

The belief-state MDP has a continuous state space, so its value function is a function on the simplex and value iteration over it looks hopeless. The rescue is a structural theorem, due to Smallwood and Sondik in 1973: for a finite-horizon POMDP the optimal value function is piecewise linear and convex (PWLC) in the belief, and therefore representable exactly by a finite set of vectors. This is the single most important fact in the subject, so we derive it.

The alpha-vector representation

A PWLC function on the simplex is an upper envelope of linear functions. Each linear function is an inner product of the belief with a vector \( \alpha \in \R^{|\mathcal{S}|} \), and the value is the best such inner product:

where \( \Gamma \) is a finite set of alpha vectors. Each alpha vector is the value, as a function of the true (unknown) state, of committing to one particular conditional plan; the belief weighs those state-contingent values by how likely each state is, and the agent, at belief \( b \), is best off following the plan whose vector wins the maximum there. The maximum of linear functions is convex, which is why the value function is convex over beliefs: a decision maker is better off, in expectation, knowing where it is than being uncertain, because certainty lets it tailor the plan.

Proof by induction on the horizon

The base case is the zero-step value \( V_0(b) = \max_a \sum_s b(s) R(s,a) \), a maximum over actions of the linear functions \( b \mapsto b \cdot r_a \) with \( r_a(s) = R(s,a) \). That is PWLC with \( \Gamma_0 = \{ r_a : a \in \mathcal{A}\} \). For the inductive step, assume \( V_{t-1}(b) = \max_{\alpha' \in \Gamma_{t-1}} \alpha' \cdot b \) is PWLC. The Bellman backup for the belief-state MDP is

where \( b'_{a,o} \) is the filtered belief. Substitute the inductive form of \( V_{t-1} \) and the filter. The pleasant cancellation is that \( V_{t-1}(b'_{a,o}) = \max_{\alpha'} \alpha' \cdot b'_{a,o} \), and \( b'_{a,o}(s') = Z(o\mid s',a)\big[\sum_s T(s'\mid s,a) b(s)\big] / P(o\mid b,a) \), so the normalizer \( P(o \mid b, a) \) in the denominator of the belief is cancelled exactly by the \( P(o \mid b, a) \) multiplying the term. What remains is linear in \( b \). Define, for an action \( a \), an observation \( o \), and a successor alpha vector \( \alpha' \in \Gamma_{t-1} \), the backprojected vector

which pulls a successor value back through one step of observation and transition into a function of the current state \( s \). Then the backup becomes

For a fixed \( b \) the inner maximization picks one successor vector per observation, and the whole bracket is then a single inner product \( b \cdot \alpha \) with

one choice \( \alpha'_o \) of successor vector for each observation. Ranging over all actions and all assignments of a successor vector to each observation generates a finite set \( \Gamma_t \), and \( V_t(b) = \max_{\alpha \in \Gamma_t} \alpha \cdot b \). That is PWLC, closing the induction. The construction also exposes the cost: the number of candidate vectors is \( |\mathcal{A}|\,|\Gamma_{t-1}|^{|\mathcal{O}|} \), because each of the \( |\mathcal{O}| \) observations independently selects among \( |\Gamma_{t-1}| \) successors. The set doubly exponential growth is what exact solvers must fight; most vectors are dominated (never the maximum anywhere on the simplex) and can be pruned by linear programming, but the worst case remains brutal, and this is the whole motivation for point-based methods.

One exact backup, worked by hand

Take the tiger problem with three actions: listen, open-left, open-right. Rewards over the true state \( (\text{TL}, \text{TR}) \): listening costs one in each state, \( r_{\text{listen}} = (-1, -1) \); opening a door faces the tiger for a big penalty and the other door for a small prize, \( r_{\text{oL}} = (-100, 10) \) and \( r_{\text{oR}} = (10, -100) \) (open-left is bad when the tiger is left). The listen observation model is \( Z(\text{HL} \mid \text{TL}) = Z(\text{HR}\mid\text{TR}) = 0.85 \) as before, and the transition for listening is the identity. Use \( \gamma = 0.95 \) and let \( b = P(\text{TL}) \) parameterize the simplex.

The one-step value function \( V_1 \) is the upper envelope of the three reward lines \( -1 \), \( -100 b + 10(1-b) = 10 - 110 b \), and \( 10 b - 100(1-b) = 110 b - 100 \). Setting listen equal to open-left gives \( 10 - 110 b = -1 \Rightarrow b = 0.1 \), and listen equal to open-right gives \( 110 b - 100 = -1 \Rightarrow b = 0.9 \). So \( V_1 \) opens left for \( b < 0.1 \), listens for \( 0.1 \le b \le 0.9 \), and opens right for \( b > 0.9 \): near certainty about the tiger's location, open the safe door; when unsure, listening's flat \( -1 \) beats the risk of a \( -100 \).

Now back up the listen action to horizon two. For each observation the agent may choose any successor vector from \( \Gamma_1 = \{ r_{\text{listen}}, r_{\text{oL}}, r_{\text{oR}} \} \). Because the listen transition is the identity, \( g_{\text{listen}, o, \alpha'}(s) = Z(o \mid s)\, \alpha'(s) \). Take the conditional plan "if you hear left, listen again; if you hear right, open the safe left door," i.e. \( \alpha'_{\text{HL}} = r_{\text{listen}} \) and \( \alpha'_{\text{HR}} = r_{\text{oL}} \). Its backed-up vector, component by component:

Enumerating all actions and all successor assignments, then pruning vectors that are dominated everywhere on \( [0,1] \), leaves the exact horizon-two value function with five pieces (verified in NumPy). Ordered by increasing \( b = P(\text{TL}) \):

Two lessons are visible in the table. First, the value function has grown from three pieces at horizon one to five at horizon two: exact backups add pieces, and the count can grow rapidly, which is the intractability. Second, the new middle pieces are genuinely informative plans, "listen, and then act on what you hear," whose alpha vectors are not parallel to any horizon-one vector; the slope of an alpha vector is the information the plan extracts. At the uniform belief \( b = 0.5 \) the optimal value is \( -1.95 \), the flat "listen then listen" vector, confirming that with 85 percent sensors a single listen is not decisive enough to justify opening at even odds.

Point-based and online POMDP solving

Point-based value iteration: PBVI and SARSOP

Exact value iteration maintains a value at every belief, but a good policy only ever visits a thin, low-dimensional slice of the simplex, the beliefs reachable from the initial belief under sensible actions. Point-based value iteration (PBVI), introduced by Pineau, Gordon and Thrun in 2003, exploits this: instead of representing \( V \) everywhere, it keeps one alpha vector per belief in a finite set \( B = \{ b_1, \ldots, b_m \} \) of sampled beliefs, and backs up only at those points. The backup at a single belief \( b \) is cheap because the inner \( \max_{\alpha'} \) is evaluated at that one belief rather than symbolically over the whole simplex, so it selects one successor vector per observation directly:

producing exactly one vector per sampled belief and per iteration, so the value-function size is capped at \( |B| \) rather than growing doubly exponentially. Because each \( \alpha_b \) is a valid lower bound (it is the exact value of a real conditional plan) and the max over these vectors is used at every belief, PBVI produces a lower bound on \( V^\ast \) whose tightness depends on how densely \( B \) covers the reachable beliefs. Anytime variants expand \( B \) by simulating the current policy forward and adding the beliefs it reaches, concentrating effort where it matters.

SARSOP, from Kurniawati, Hsu and Lee in 2008, sharpens this idea by targeting the beliefs reachable under an optimal policy rather than under any policy, which is a smaller set. It maintains both a lower bound (alpha vectors) and an upper bound on \( V^\ast \), and it expands the belief tree by descending along actions and observations chosen to reduce the gap between the bounds at the initial belief, pruning subtrees that the bounds prove cannot be optimal. The name stands for successive approximations of the reachable space under optimal policies. SARSOP remains one of the strongest offline POMDP solvers and is the reference implementation people reach for when a problem is small enough to solve offline once and deploy the resulting alpha vectors.

Online solving: POMCP and DESPOT

When the state space is too large even to enumerate for a filter, or the model is available only as a simulator, the alternative is to plan online from the current belief and never build a global value function. POMCP (Partially Observable Monte Carlo Planning), from Silver and Veness in 2010, runs Monte Carlo tree search over histories, represents the belief as an unweighted particle set, and uses a black-box simulator to sample transitions and observations. Its two ideas are that a particle filter can approximate the belief without an explicit model, and that the same particles used to plan can be reused to update the belief after acting, so the belief representation and the planner share state. POMCP scales to very large POMDPs because its cost per decision depends on the number of simulations, not on the size of the state space, though it can suffer particle depletion when observations are rare.

DESPOT (Determinized Sparse Partially Observable Tree), from Somani, Ye, Hsu and Lee in 2013, addresses a weakness of POMCP: the search tree branches on every possible observation, so it is wide and shallow. DESPOT fixes a small number of sampled "scenarios" (determinized random-number streams) and searches only the tree consistent with them, which bounds the branching factor and yields a regret bound relating the number of scenarios to the value gap. It also admits a regularized objective that penalizes overfitting to the sampled scenarios. In practice DESPOT and its successors drive real robotic systems that must plan under uncertainty in real time, such as autonomous driving among pedestrians whose intentions are hidden.

Monte Carlo tree search in depth

The planners above all rest on Monte Carlo tree search (MCTS), and MCTS rests on a bandit algorithm. This section builds it bottom-up: the bandit problem, the derivation of UCB1 from a concentration inequality, the recursive application UCT, and the extension to continuous actions.

The bandit view and the exploration-exploitation tension

A multi-armed bandit has \( K \) arms; pulling arm \( i \) returns a reward drawn i.i.d. from an unknown distribution on \( [0,1] \) with mean \( \mu_i \). The player pulls arms one at a time and wants to maximize cumulative reward, equivalently to minimize regret against always pulling the best arm \( \mu^\ast = \max_i \mu_i \):

where \( N_i(n) \) is the number of pulls of arm \( i \) after \( n \) rounds and the second equality just groups the regret by arm. To keep regret small an algorithm must pull each suboptimal arm only \( O(\log n) \) times, which is the best possible by the Lai-Robbins lower bound. The difficulty is that the means are unknown and estimated from noisy samples, so the algorithm must balance pulling arms that look good (exploitation) against pulling arms it is unsure about (exploration).

Deriving UCB1 from Hoeffding's inequality

The optimism-in-the-face-of-uncertainty principle says: act as if each arm's mean is as high as the data plausibly allow, then the arm you pull is either genuinely good, in which case you gain, or over-estimated, in which case you learn. To make "plausibly allow" precise, use Hoeffding's inequality: for \( n \) i.i.d. samples in \( [0,1] \) with empirical mean \( \hat{\mu} \) and true mean \( \mu \),

We want an upper confidence bound \( \hat{\mu}_i + u_i \) that overshoots the true mean with only a small, controlled probability. Set the tail probability at round \( t \) to \( t^{-4} \), a deliberately fast-shrinking budget so that the probabilities are summable over time. Solving \( e^{-2 n_i u_i^2} = t^{-4} \) for the width \( u_i \) with \( n_i \) the current pull count of arm \( i \):

This gives the UCB1 rule of Auer, Cesa-Bianchi and Fischer (2002): at round \( t \) pull the arm maximizing

the empirical mean (exploitation) plus a confidence bonus that grows with the log of total time and shrinks with the arm's own pull count (exploration). The regret analysis then shows that a suboptimal arm \( i \) is pulled at most about \( 8 \ln n / \Delta_i^2 \) times: once the bonus for arm \( i \) has shrunk below \( \Delta_i \), which happens after \( O(\ln n / \Delta_i^2) \) pulls, the bound for the optimal arm exceeds arm \( i \)'s bound with high probability and arm \( i \) is no longer chosen; the summable \( t^{-4} \) tail budget controls the rare rounds where concentration fails. The total regret is \( O\!\big( \sum_{i:\Delta_i>0} \ln n / \Delta_i \big) \), matching the Lai-Robbins lower bound up to constants. The bonus constant is often written \( c \sqrt{\ln t / n_i} \) with \( c \) a tunable exploration weight; \( c = \sqrt{2} \) is the theoretical value for rewards in \( [0,1] \), and tuned values are common in practice.

UCT: UCB1 recursively down a tree

Kocsis and Szepesvari (2006) turned UCB1 into a planner by treating action selection at each node of a search tree as its own bandit problem, where an arm is a child action and its reward is the return backed up from simulations that passed through it. The resulting algorithm, UCT (Upper Confidence bounds applied to Trees), runs many simulations, each of four phases. Selection: from the root, descend by repeatedly choosing the child maximizing \( \hat{Q}(s,a) + c \sqrt{\ln N(s) / N(s,a)} \), where \( \hat{Q} \) is the mean return through that child, \( N(s) \) is the visit count of the node and \( N(s,a) \) of the child, until a node with an unexpanded action is reached. Expansion: add one new child. Simulation: play out a default (often random) policy from the new node to a terminal or a depth cap, obtaining a return. Backpropagation: add that return to \( \hat{Q} \) and increment the counts of every node on the path. After the simulation budget is spent, the root action with the highest visit count (or highest mean) is played. The value that makes UCT work is that the internal estimates are non-stationary, because a child's return distribution changes as its own subtree is refined, yet UCB1 still guides the search toward the promising subtrees and, in the limit, the value estimate at the root converges to the minimax or expectimax value. In a POMDP the "state" of the tree is a history and the simulator supplies transitions and observations, which is exactly POMCP.

Progressive widening for continuous actions

UCB1 assumes a finite arm set; with continuous or very large action spaces every simulation would try a fresh action and no action would ever be visited twice, so the tree never deepens. Progressive widening caps the number of children a node is allowed as a slowly growing function of its visit count: node \( s \) may have at most \( \lceil k\, N(s)^{\alpha} \rceil \) children, with \( k > 0 \) and \( \alpha \in (0,1) \). When the cap is not yet reached a new action is sampled and added; otherwise selection proceeds among the existing children by UCB. Because \( N(s)^{\alpha} \) grows sublinearly, each existing action accrues visits and its value estimate stabilizes, while the action set still densifies over time. The same trick applied to the observation or state branching is double progressive widening, which is what lets tree search handle continuous observations, as in continuous-state POMDPs. The technique, developed by Couetoux and colleagues in 2011, is the standard way to bring MCTS to robotics and control, where actions are real-valued. When a learned value or policy network replaces the random rollout, this same machinery becomes the search used in the strongest game and planning agents, which the deep reinforcement learning page takes up.

Value of information

Information is only worth acquiring if it might change a decision, and then only up to the improvement it produces. The value-of-information calculus makes this exact and turns "should we run the test" into an arithmetic comparison. Let \( \theta \) be an uncertain state of the world with prior \( p(\theta) \), let \( a \in \mathcal{A} \) be the decision, and let \( U(a, \theta) \) be the utility. The best the agent can do knowing only the prior is the prior-optimal expected utility,

Expected value of perfect information

Suppose an oracle could reveal \( \theta \) exactly before the decision. Then for each revealed value the agent picks the best action for that \( \theta \), and averaging over what the oracle might say gives the prior-expected value with perfect information,

The expected value of perfect information is the difference,

Nonnegativity is Jensen's inequality applied to the convex function \( \max_a \): the maximum of a set of linear functionals is convex, and moving the expectation inside a convex function cannot increase it, so \( \E[\max_a U] \ge \max_a \E[U] \). Information never hurts a rational agent, because the no-information policy is always still available; EVPI is exactly the gap Jensen leaves. It is an upper bound on what any test, however good, can be worth, which is its practical use: if a perfect test is not worth its price, no imperfect one is either.

Expected value of sample information

Real tests are noisy. A test is an experiment that returns a signal \( z \) correlated with \( \theta \) through a likelihood \( p(z \mid \theta) \). After seeing \( z \) the agent updates to the posterior \( p(\theta \mid z) \) and picks the posterior-best action; averaging over the prior predictive distribution of the signal \( p(z) = \sum_\theta p(z\mid\theta) p(\theta) \) gives the value of acting with the test,

and the expected value of sample information is

nonnegative by the same Jensen argument, now applied to the posterior. EVSI is what a specific test is worth; it lies between zero and EVPI, and a perfectly revealing experiment recovers EVPI as a special case. The decision rule is immediate: buy the test if and only if its EVSI exceeds its cost.

Gaussian processes for decisions

The final decision problem is choosing where to evaluate an expensive black-box function \( f : \mathcal{X} \to \R \), knowing only noisy evaluations at previously chosen points. This is Bayesian optimization, and its engine is a Gaussian-process (GP) posterior over \( f \) together with an acquisition function that turns the posterior into a decision about where to sample next. The acquisition function is a value-of-information object: it prices each candidate point by how much improvement it is expected to yield.

The Gaussian process posterior, derived

A GP places a Gaussian prior over functions: any finite set of function values is jointly Gaussian, with mean given by a mean function (take it zero) and covariance given by a kernel \( k(x, x') \). Given training inputs \( X = (x_1, \ldots, x_n) \) with noisy targets \( y_i = f(x_i) + \varepsilon_i \), \( \varepsilon_i \sim \mathcal{N}(0, \sigma_n^2) \), and a test point \( x_\ast \), the values \( \mathbf{y} \) and \( f_\ast = f(x_\ast) \) are jointly Gaussian:

where \( K_{ij} = k(x_i, x_j) \) is the training covariance and \( (\mathbf{k}_\ast)_i = k(x_i, x_\ast) \). The posterior over \( f_\ast \) is obtained by the Gaussian conditioning identity: if \( (\mathbf{a}, \mathbf{b}) \) are jointly Gaussian with covariance blocks \( \Sigma_{aa}, \Sigma_{ab}, \Sigma_{bb} \), then \( \mathbf{b} \mid \mathbf{a} \) is Gaussian with mean \( \Sigma_{ba}\Sigma_{aa}^{-1}\mathbf{a} \) and covariance \( \Sigma_{bb} - \Sigma_{ba}\Sigma_{aa}^{-1}\Sigma_{ab} \). This identity is itself a consequence of completing the square in the joint Gaussian density, or equivalently of the Schur complement of the covariance; the graphical-models page derives it from the information form. Applying it with \( \mathbf{a} = \mathbf{y} \) and \( \mathbf{b} = f_\ast \):

The posterior mean is a linear smoother of the observations, and the posterior variance shrinks near the data and reverts to the prior variance far from it. Both are needed for decisions: the mean says where \( f \) is believed to be low (for minimization), and the variance says where the belief is weak and a surprise might lie. The cost is the \( O(n^3) \) factorization of \( K + \sigma_n^2 I \), which caps exact GPs at a few thousand points and motivates the sparse and inducing-point methods used at scale.

Acquisition functions and Expected Improvement in closed form

Given the posterior, an acquisition function scores candidate points; the next evaluation goes to the maximizer of the acquisition. Three are standard. GP-UCB (Srinivas et al., 2010) is the optimism rule transported to continuous domains: for maximization, \( a_{\text{UCB}}(x) = \mu(x) + \beta_t^{1/2} \sigma(x) \), with a schedule for \( \beta_t \) that yields a sublinear cumulative-regret bound in terms of the kernel's information gain. Thompson sampling draws a sample function from the GP posterior and evaluates at its optimum, exploring in proportion to the posterior probability that a point is best. Expected Improvement (EI), from Mockus (1978) and popularized by Jones, Schonlau and Welch's EGO (1998), prices a point by the expected amount by which it beats the best value seen so far, and it has a closed form worth deriving.

Work in the minimization convention with \( f_{\min} \) the best (lowest) observed value. At a candidate \( x \) the posterior predicts \( Y \sim \mathcal{N}(\mu, \sigma^2) \) with \( \mu = \mu(x) \), \( \sigma = \sigma(x) \). The improvement is \( I = \max(f_{\min} - Y, 0) \), and Expected Improvement is its mean:

Substitute \( t = (y - \mu)/\sigma \), so \( y = \mu + \sigma t \), \( dy = \sigma\, dt \), and the upper limit \( y = f_{\min} \) becomes \( t = z \) with \( z = (f_{\min} - \mu)/\sigma \). The integrand's factor becomes \( f_{\min} - \mu - \sigma t \), and \( \mathcal{N}(y;\mu,\sigma^2) dy = \varphi(t)\, dt \) with \( \varphi \) the standard normal density:

The first integral is \( \Phi(z) \), the standard normal CDF. For the second, use \( \varphi'(t) = -t\,\varphi(t) \), so \( \int_{-\infty}^{z} t\,\varphi(t)\, dt = -\int_{-\infty}^{z} \varphi'(t)\, dt = -\varphi(z) \). Therefore

which can be written \( \sigma\,[\, z\,\Phi(z) + \varphi(z) \,] \) since \( f_{\min} - \mu = \sigma z \). The two terms are exactly exploitation and exploration: the first rewards a low posterior mean (\( \mu \) well below \( f_{\min} \) makes \( z \) large and \( \Phi(z) \to 1 \)), the second rewards high posterior uncertainty (large \( \sigma \) with the \( \varphi(z) \) bump), and EI balances them with no tuning parameter, which is why it is the default acquisition. As \( \sigma \to 0 \) at an observed point, \( \mathrm{EI} \to 0 \), so EI never re-samples where it is already certain.

Validation of safety-critical policies

A POMDP policy that will drive a car or fly an aircraft must be validated against failures that are, by design, extremely rare, which makes naive Monte Carlo hopeless: to observe a failure of probability \( 10^{-9} \) with any confidence would take on the order of \( 10^{10} \) simulations. Two ideas make validation feasible. Importance sampling replaces the nominal disturbance distribution \( p \) with a proposal \( q \) that makes failures common, then corrects the estimate with the likelihood ratio: the failure probability is \( \E_{p}[\mathbb{1}_{\text{fail}}] = \E_{q}\big[\mathbb{1}_{\text{fail}} \, p(x)/q(x)\big] \), an unbiased estimator whose variance is small when \( q \) concentrates on the failure region while keeping the ratio controlled. Finding a good \( q \) is the hard part, and the cross-entropy method iteratively fits \( q \) to the failures it has already found.

Adaptive stress testing (Lee, Koren, Kochenderfer and colleagues) frames the search for the most likely failure as a sequential decision problem: a reinforcement-learning or tree-search agent controls the environment's disturbances and is rewarded for driving the system to a failure while keeping the disturbance sequence probable under the nominal model, so the failures it surfaces are the ones most worth fixing. Because the falsifier is itself an MDP or POMDP solver, the whole toolkit of this page, MCTS with progressive widening for continuous disturbances, applies to validating the very policies the toolkit produces. This closes a loop that a deployed autonomous system needs: plan under uncertainty, then adversarially search for the rare beliefs and disturbances under which the plan fails.

Implementation

The code below is written to be run and checked, not merely read. The belief filter and the UCT planner are exact reference implementations; the GP posterior and EI are checked against the numbers worked by hand above. Python with NumPy and SciPy is primary because these algorithms are small linear algebra and control flow, not dense tensor programs; a JAX version is given where vectorizing or differentiating actually buys something, namely the GP posterior (batched over candidates and differentiable through the kernel hyperparameters) and the belief filter (vectorized over a particle set).

The POMDP belief filter

The first block is the exact Bayesian filter for a discrete POMDP, applied to the tiger problem to reproduce the beliefs from Problem 2. The JAX version vectorizes the same update over a batch of beliefs, which is the shape a particle-based or ensemble filter needs.

import numpy as np

def belief_update(b, a, o, T, Z):
    """Exact discrete Bayesian filter.
    b : (S,)      current belief over states
    T : (A,S,S)   T[a,s,s'] = P(s' | s, a)
    Z : (A,S,O)   Z[a,s',o] = P(o | s', a)
    returns b' : (S,) posterior after action a, observation o
    """
    pred = b @ T[a]                     # (S,) predict step: sum_s T[a,s,s'] b[s]
    unnorm = Z[a, :, o] * pred          # (S,) correct step: Z[a,s',o] * pred[s']
    return unnorm / unnorm.sum()        # renormalize; sum is P(o | b, a)

# tiger problem: states (TL, TR), actions (listen, open-left, open-right),
# observations (hear-left, hear-right). listening does not move the tiger.
S, A, O = 2, 3, 2
T = np.stack([np.eye(2),                # listen: identity
              np.full((2, 2), 0.5),     # open-left: tiger resets to uniform
              np.full((2, 2), 0.5)])    # open-right: tiger resets to uniform
Z = np.zeros((A, S, O))
Z[0] = [[0.85, 0.15],                   # listen: P(o | s'); 85% accurate
        [0.15, 0.85]]
Z[1] = Z[2] = 0.5                       # opening reveals nothing about next tiger

b0 = np.array([0.5, 0.5])
b1 = belief_update(b0, a=0, o=0, T=T, Z=Z)          # listen, hear-left
b2 = belief_update(b1, a=0, o=0, T=T, Z=Z)          # listen, hear-left again
b3 = belief_update(b1, a=0, o=1, T=T, Z=Z)          # listen, hear-right
print(b1)   # [0.85 0.15]
print(b2)   # [0.9698 0.0302]
print(b3)   # [0.5 0.5]

import jax, jax.numpy as jnp

def belief_update(b, a, o, T, Z):
    pred = b @ T[a]                     # (S,)
    unnorm = Z[a, :, o] * pred          # (S,)
    return unnorm / unnorm.sum()

# vmap the filter over a batch of beliefs (an ensemble / particle cloud):
batched = jax.vmap(belief_update, in_axes=(0, None, None, None, None))

T = jnp.stack([jnp.eye(2), jnp.full((2, 2), 0.5), jnp.full((2, 2), 0.5)])
Z = jnp.zeros((3, 2, 2)).at[0].set(jnp.array([[0.85, 0.15], [0.15, 0.85]]))
Z = Z.at[1].set(0.5).at[2].set(0.5)

B = jnp.array([[0.5, 0.5], [0.7, 0.3], [0.9, 0.1]])   # (N, S) batch of beliefs
B1 = batched(B, 0, 0, T, Z)             # each row updated by (listen, hear-left)
print(B1[0])   # [0.85 0.15]  matches the NumPy filter for the uniform prior

Gaussian-process posterior and Expected Improvement

The next block builds the GP posterior of Problem 4 and evaluates EI, reproducing \( \mu(3) = 1.2819 \), \( \sigma(3) = 0.8553 \), \( \mathrm{EI}(3) = 0.1263 \). The JAX version batches the posterior over a grid of candidates and is differentiable through the kernel lengthscale, which is what a marginal-likelihood optimizer needs.

import numpy as np
from scipy.stats import norm

def rbf(a, b, ell=0.7):
    return np.exp(-(a[:, None] - b[None, :]) ** 2 / (2 * ell ** 2))

X = np.array([0., 1., 2., 4.])          # training inputs
y = np.array([1.8, 0.7, 1.5, 2.0])      # noisy observations (minimization)
noise = 1e-2

K = rbf(X, X) + noise * np.eye(len(X))  # (n,n)
Kinv = np.linalg.inv(K)

def gp_posterior(xs):
    ks = rbf(xs, X)                     # (m,n)
    mu = ks @ Kinv @ y                  # (m,) posterior mean
    var = 1.0 - np.einsum('mi,ij,mj->m', ks, Kinv, ks)   # (m,) posterior var
    return mu, np.sqrt(var)

def expected_improvement(xs, fmin):
    mu, sd = gp_posterior(xs)
    z = (fmin - mu) / sd
    return (fmin - mu) * norm.cdf(z) + sd * norm.pdf(z)

mu, sd = gp_posterior(np.array([3.0]))
print(mu[0], sd[0])                     # 1.2819 0.8553
print(expected_improvement(np.array([3.0]), fmin=y.min())[0])   # 0.1263

import jax, jax.numpy as jnp
from jax.scipy.stats import norm

def rbf(a, b, ell):
    return jnp.exp(-(a[:, None] - b[None, :]) ** 2 / (2 * ell ** 2))

X = jnp.array([0., 1., 2., 4.])
y = jnp.array([1.8, 0.7, 1.5, 2.0])
noise = 1e-2

def ei(xs, ell, fmin):
    K = rbf(X, X, ell) + noise * jnp.eye(X.shape[0])
    ks = rbf(xs, X, ell)                            # (m,n)
    sol = jnp.linalg.solve(K, y)                    # (n,)  K^{-1} y
    mu = ks @ sol                                   # (m,)
    v = jnp.linalg.solve(K, ks.T)                   # (n,m) K^{-1} k*
    var = 1.0 - jnp.sum(ks * v.T, axis=1)           # (m,)
    sd = jnp.sqrt(var)
    z = (fmin - mu) / sd
    return (fmin - mu) * norm.cdf(z) + sd * norm.pdf(z)

xs = jnp.array([3.0])
print(ei(xs, 0.7, jnp.min(y)))                      # [0.1263]
# differentiable in the lengthscale: gradient of EI w.r.t. ell in one line
g = jax.grad(lambda ell: ei(xs, ell, jnp.min(y))[0])(0.7)
print(g)                                            # d EI(3) / d ell

UCT: Monte Carlo tree search on a bandit reward

The last block is a compact but faithful UCT planner run on a small stochastic decision problem: a root with several actions, each of which leads to a noisy terminal reward. It shows the four phases, the UCB1 selection rule with the \( \sqrt{2\ln N / n} \) bonus, and the visit-count-based final choice. On a bandit-shaped problem UCT concentrates its visits on the best arm, which is the property the regret analysis promises.

import numpy as np
rng = np.random.default_rng(0)

# a 4-armed stochastic problem: arm i returns a noisy reward with mean means[i].
means = np.array([0.20, 0.55, 0.50, 0.80])   # arm 3 is best
def sample_reward(a):
    return float(np.clip(means[a] + rng.normal(0, 0.1), 0, 1))

class Node:
    def __init__(self, n_actions):
        self.N = 0                            # visits to this node
        self.n = np.zeros(n_actions)          # visits to each child action
        self.q = np.zeros(n_actions)          # mean return through each action

def uct_action(node, c=np.sqrt(2)):
    # selection: pull any unvisited arm first, else UCB1
    unvisited = np.where(node.n == 0)[0]
    if len(unvisited):
        return int(unvisited[0])
    ucb = node.q + c * np.sqrt(np.log(node.N) / node.n)
    return int(np.argmax(ucb))

def uct(iterations=2000):
    root = Node(len(means))
    for _ in range(iterations):
        a = uct_action(root)                  # select
        r = sample_reward(a)                  # simulate (1-step rollout here)
        root.N += 1                           # backpropagate
        root.n[a] += 1
        root.q[a] += (r - root.q[a]) / root.n[a]   # running mean
    return root

root = uct(2000)
print("visits per arm:", root.n.astype(int))   # concentrated on arm 3
print("value estimates:", np.round(root.q, 3))
print("chosen arm:", int(np.argmax(root.n)))    # 3, the true best

Running the planner puts the large majority of its visits on arm 3, the true best, and only logarithmically many on each worse arm, exactly the \( O(\ln n / \Delta_i) \) allocation the UCB1 analysis predicts; the recovered value estimates match the arm means to within the sampling noise. Deepening the rollout and letting nodes have children turns this into full tree search, and swapping the reward sampler for a POMDP simulator that returns observations turns it into POMCP.

How it is done in practice: the engineering gap

The gap between these derivations and a deployed system is mostly about which approximation is acceptable where. Offline, when a POMDP is small and static, SARSOP computes alpha vectors once and the runtime policy is a dot product against each vector followed by an argmax, which is microseconds; the engineering is in the modeling, getting the observation and transition probabilities right, and in verifying the discretization of a continuous problem did not throw away the structure that made it solvable. Online, when the state space is large or the model is a simulator, POMCP and DESPOT plan within a fixed time budget per decision, and the practical levers are the number of simulations, the rollout policy (a hand-coded or learned heuristic dramatically outperforms random rollouts), and particle management to avoid depletion when observations are informative. Real autonomous-driving stacks run DESPOT-style planners at control rates by capping tree depth and reusing the previous step's tree.

Bayesian optimization in production rarely uses a bare EI on a bare GP. The GP is usually fit with a Matern rather than a squared-exponential kernel, because sample paths of the squared-exponential are infinitely smooth and over-confident; the hyperparameters are marginalized or re-fit by maximum marginal likelihood at each step; the acquisition is optimized over a continuous domain with multi-start gradient ascent, using the differentiability the JAX code above exposes; and batch (parallel) evaluation uses q-EI or entropy-based acquisitions rather than one-point EI. BoTorch, built on GPyTorch, is the reference stack for exactly this, providing GPU-accelerated GPs, Monte Carlo acquisition estimators, and their gradients. The \( O(n^3) \) GP cost caps exact methods around a few thousand evaluations, which is usually enough for hyperparameter tuning and experimental design; beyond that, sparse GPs with inducing points or trust-region methods take over.

The current research frontier

Three threads are active. The first is scaling POMDP solvers to continuous and high-dimensional state and observation spaces, where particle-based online methods with double progressive widening (POMCPOW and PFT-DPW from the group at Stanford around Kochenderfer) and learned belief representations meet, and where the question is how to plan when the belief cannot be written down exactly. The second is the marriage of tree search with learned value and policy functions: replacing random rollouts with a neural evaluator, as in the AlphaZero line at DeepMind and its open reimplementations, and, more recently, using tree search at inference time to improve the outputs of large sequence models, which has revived interest in the exploration constants and progressive-widening schedules derived here. The third is Bayesian optimization beyond Expected Improvement: information-theoretic acquisitions (entropy search and predictive entropy search from Cambridge and Harvard groups, max-value entropy search), multi-fidelity and multi-task optimization that borrow cheap approximations, and neural surrogates that replace the GP when thousands of evaluations are available. Underlying all three is a steady flow of work, from Auer's original bandit analysis through the modern regret bounds of Srinivas and successors, on exactly how much to explore, which is the quantity every method on this page is ultimately trading off.

Open source to read

• JuliaPOMDP/POMDPs.jl is the most complete open POMDP ecosystem: a common interface plus solvers (SARSOP, QMDP, POMCP, DESPOT, POMCPOW). Start with the interface definition and the tiger example, then read the SARSOP.jl and BasicPOMCP.jl solver packages to see the alpha-vector and tree-search code side by side.
• AdaCompNUS/despot is the reference C++ implementation of DESPOT from the group that invented it. Read src/core/ for the scenario tree and the lower/upper bound machinery, which is the clearest exposition of determinized sparse search.
• google-deepmind/mctx is MCTS in JAX, batched and differentiable, implementing MuZero-style and Gumbel search. Open mctx/_src/search.py to see selection, expansion, and backup written as pure array operations, the vectorized counterpart to the UCT loop above.
• pytorch/botorch is the production Bayesian-optimization library. Read botorch/acquisition/analytic.py for the exact closed-form EI (the formula derived here) and monte_carlo.py for the reparameterized Monte Carlo acquisitions used for batch selection.
• cornellius-gp/gpytorch is the GP engine under BoTorch, scaling exact GPs with conjugate-gradient and Lanczos linear algebra. Read gpytorch/models/exact_gp.py to see the posterior of the derivation implemented with iterative solvers instead of an explicit inverse.
• fmfn/BayesianOptimization is a small, readable pure-Python package good for understanding the loop end to end: fit GP, maximize acquisition, evaluate, repeat. Start at bayes_opt/bayesian_optimization.py.
• GPflow/GPflow (and the older GPy) implement variational and sparse GPs on TensorFlow; read the SVGP model to see how inducing points break the \( O(n^3) \) barrier that limits the exact posterior above.

Common misconceptions

"A POMDP policy needs the whole history." It does not: the belief, a fixed-size distribution over states, is a sufficient statistic for the unbounded history, which is the entire reason the problem is tractable at all. What is unbounded is the reachable set of beliefs, not the representation of any one belief.

"The POMDP value function is some complicated nonlinear surface over the simplex." For a finite POMDP it is piecewise linear and convex, exactly a maximum of finitely many hyperplanes, which is why a finite set of alpha vectors represents it without error. The complexity is in the number of pieces, not in the shape of each piece.

"MCTS is a heuristic with no guarantees." UCT's selection rule is UCB1, whose logarithmic regret is a theorem, and UCT's value estimate at the root is consistent, converging to the true optimal value as simulations grow. The heuristic parts are the rollout policy and the exploration constant, not the selection principle.

"The UCB exploration bonus is an arbitrary tuning term." It is the width of a Hoeffding confidence interval with the failure probability set to \( t^{-4} \); the constant \( \sqrt 2 \) is what makes the failure probabilities summable so that logarithmic regret holds. It is derived, not guessed, even if practitioners then retune it for finite-sample performance.

"Value of information can be negative if the test is unreliable." Never, for a rational expected-utility maximizer: EVPI and EVSI are nonnegative by Jensen's inequality, because the agent can always ignore a test and fall back on the prior-optimal action. A test can be worth less than its cost, which is a different thing, and is exactly when you should decline it.

"Expected Improvement is greedy and under-explores." EI's second term, \( \sigma \varphi(z) \), rewards posterior uncertainty and keeps it sampling regions where the mean is unpromising but the variance is high; a point can have EI far above zero even when its posterior mean is worse than the incumbent, which is precisely how EI escapes local optima. Pure mean minimization is the greedy rule EI is built to avoid.

"A Gaussian process gives you the true uncertainty." It gives you the posterior uncertainty under its prior, the kernel and its hyperparameters; a misspecified kernel is confidently wrong, which is why practitioners marginalize or re-fit hyperparameters and prefer rougher Matern kernels over the over-smooth squared-exponential.

Self-check

References

1. Kochenderfer, M. J. Decision Making Under Uncertainty: Theory and Application, MIT Press, 2015. mitpress.mit.edu
2. Kochenderfer, M. J., Wheeler, T. A., and Wray, K. H. Algorithms for Decision Making, MIT Press, 2022. algorithmsbook.com
3. Russell, S., and Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2020. aima.cs.berkeley.edu
4. von Neumann, J., and Morgenstern, O. Theory of Games and Economic Behavior, Princeton University Press, 1944. press.princeton.edu
5. Rasmussen, C. E., and Williams, C. K. I. Gaussian Processes for Machine Learning, MIT Press, 2006. gaussianprocess.org/gpml
6. Smallwood, R. D., and Sondik, E. J. "The optimal control of partially observable Markov processes over a finite horizon", Operations Research 21(5), 1973. doi:10.1287/opre.21.5.1071
7. Astrom, K. J. "Optimal control of Markov processes with incomplete state information", Journal of Mathematical Analysis and Applications 10(1), 1965. doi:10.1016/0022-247X(65)90154-X
8. Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. "Planning and acting in partially observable stochastic domains", Artificial Intelligence 101(1-2), 1998. doi:10.1016/S0004-3702(98)00023-X
9. Pineau, J., Gordon, G., and Thrun, S. "Point-based value iteration: an anytime algorithm for POMDPs", IJCAI, 2003. ijcai.org/Proceedings/03
10. Kurniawati, H., Hsu, D., and Lee, W. S. "SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces", Robotics: Science and Systems, 2008. doi:10.15607/RSS.2008.IV.009
11. Shani, G., Pineau, J., and Kaplow, R. "A survey of point-based POMDP solvers", Autonomous Agents and Multi-Agent Systems 27, 2013. doi:10.1007/s10458-012-9200-2
12. Silver, D., and Veness, J. "Monte-Carlo planning in large POMDPs", NeurIPS, 2010. papers.nips.cc/paper/2010
13. Somani, A., Ye, N., Hsu, D., and Lee, W. S. "DESPOT: online POMDP planning with regularization", NeurIPS, 2013. papers.nips.cc/paper/2013
14. Auer, P., Cesa-Bianchi, N., and Fischer, P. "Finite-time analysis of the multiarmed bandit problem", Machine Learning 47, 2002. doi:10.1023/A:1013689704352
15. Hoeffding, W. "Probability inequalities for sums of bounded random variables", Journal of the American Statistical Association 58(301), 1963. doi:10.1080/01621459.1963.10500830
16. Kocsis, L., and Szepesvari, C. "Bandit based Monte-Carlo planning", ECML, 2006. doi:10.1007/11871842_29
17. Browne, C., Powley, E., Whitehouse, D., et al. "A survey of Monte Carlo tree search methods", IEEE Transactions on Computational Intelligence and AI in Games 4(1), 2012. doi:10.1109/TCIAIG.2012.2186810
18. Couetoux, A., Hoock, J.-B., Sokolovska, N., Teytaud, O., and Bonnard, N. "Continuous upper confidence trees", LION, 2011. doi:10.1007/978-3-642-25566-3_32
19. Howard, R. A. "Information value theory", IEEE Transactions on Systems Science and Cybernetics 2(1), 1966. doi:10.1109/TSSC.1966.300074
20. Jones, D. R., Schonlau, M., and Welch, W. J. "Efficient global optimization of expensive black-box functions", Journal of Global Optimization 13, 1998. doi:10.1023/A:1008306431147
21. Mockus, J. "On Bayesian methods for seeking the extremum", Optimization Techniques (IFIP), 1974/1978. doi:10.1007/978-3-662-38527-2_55
22. Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. "Gaussian process optimization in the bandit setting: no regret and experimental design", ICML, 2010. arXiv:0912.3995
23. Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and de Freitas, N. "Taking the human out of the loop: a review of Bayesian optimization", Proceedings of the IEEE 104(1), 2016. doi:10.1109/JPROC.2015.2494218
24. Snoek, J., Larochelle, H., and Adams, R. P. "Practical Bayesian optimization of machine learning algorithms", NeurIPS, 2012. arXiv:1206.2944
25. Corso, A., Moss, R. J., Koren, M., Lee, R., and Kochenderfer, M. J. "A survey of algorithms for black-box safety validation of cyber-physical systems", Journal of Artificial Intelligence Research 72, 2021. arXiv:2005.02979