Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

Decisions: Utility, MDPs & Bandits

Choosing well when outcomes are uncertain.

A robot on a slippery floor, a doctor deciding whether to order a test, a website choosing which headline to show: each must act before the outcome is known, and each choice changes what it gets to see next. This lesson builds the machinery for choosing well, from one-shot decision networks to Markov decision processes solved by value and policy iteration, belief states for hidden worlds, and bandit algorithms for when the odds themselves are unknown.

What you’ll learn

  • Evaluate a decision network by maximum expected utility, and compute the value of perfect information for a concrete decision.
  • Derive the Bellman equations of a Markov decision process, and solve for a fixed policy's values as a linear system.
  • Run value iteration, prove that the Bellman backup is a γ\gamma-contraction, and use the resulting error bound as a stopping rule.
  • Explain policy iteration through the policy improvement theorem, and turn a partially observable problem into an MDP over beliefs.
  • Define regret, and compare greedy, ε\varepsilon-greedy, UCB1 and Thompson sampling on a multi-armed bandit.

Decision networks and the value of information

An agent that must act once under uncertainty follows the principle of maximum expected utility (MEU): given evidence ee, choose

a⋆=arg max⁡a EU(a∣e),EU(a∣e)=∑sP(s∣a,e) U(s).a^\star=\argmax_a\ \mathrm{EU}(a\mid e),\qquad \mathrm{EU}(a\mid e)=\sum_sP(s\mid a,e)\,U(s).

Why expected utility, rather than the best or the worst case? The Deep Layer lesson Rationality & Expected Utility proves it: an agent whose preferences over gambles satisfy the von Neumann–Morgenstern axioms behaves as if it maximizes expected utility. This lesson is about computing it.

A decision network, or influence diagram (Howard & Matheson, 1984), is a Bayesian network with two extra kinds of node. Decision nodes (rectangles) hold the agent's choices, and utility nodes (diamonds) hold a function of their parents; chance nodes (ovals) carry conditional probability tables as usual. An arc into a decision node is an information arc: its source is observed before the decision is made, so the decision becomes a function of it.

text
function BEST-DECISION(network, evidence e, decision node D, utility node U):
    for each value d of D:
        fix D = d
        P(x | e, d) ← posterior over the chance parents X of U   # any Bayes-net inference
        EU[d] ← Σ_x P(x | e, d) · U(x, d)
    return argmax_d EU[d]

# With information arcs O → D, run the loop once per observed value o;
# the result is a policy δ(o) = argmax_d EU(d | e, o).

Russell and Norvig's evaluation algorithm. Each action (and each observation value) costs one probabilistic inference, so exact evaluation inherits the NP-hardness of exact inference, and large networks fall back on approximate inference.

ActionRain (P=0.4P=0.4)No rain (P=0.6P=0.6)Expected utility
Take the umbrella70800.4⋅70+0.6⋅80=760.4\cdot70+0.6\cdot80=76
Leave it01000.4⋅0+0.6⋅100=600.4\cdot0+0.6\cdot100=60
The utilities of a commute. Without further information, MEU says take the umbrella: 76>6076>60.
Predict before you look

A perfect forecast would tell you, before you leave, whether it will rain. What is the most it is worth to you, in utility units?

Show the answer

12

With the forecast you take the umbrella when it says rain (utility 70) and leave it otherwise (100), for an expected utility of 0.4⋅70+0.6⋅100=880.4\cdot70+0.6\cdot100=88. Without it the best is 76, so the value of perfect information is 88−76=1288-76=12. An 80%-accurate forecast is worth less: Bayes' rule gives P(rain∣"rain")=0.32/0.44≈0.73P(\text{rain}\mid\text{"rain"})=0.32/0.44\approx0.73 and P(rain∣"dry")=0.08/0.56≈0.14P(\text{rain}\mid\text{"dry"})=0.08/0.56\approx0.14, the best responses are still take and leave, and the expected utility is 0.44⋅72.7+0.56⋅85.7=800.44\cdot72.7+0.56\cdot85.7=80: a value of only 4.

In general, for a variable EjE_j that can be observed before deciding,

VPIe(Ej)=∑ejP(ej∣e) max⁡aEU(a∣e,ej) − max⁡aEU(a∣e).\mathrm{VPI}_e(E_j)=\sum_{e_j}P(e_j\mid e)\,\max_a\mathrm{EU}(a\mid e,e_j)\ -\ \max_a\mathrm{EU}(a\mid e).

It is never negative (the rationality lesson proves it), and it is zero when no possible observation would change the decision. It is not additive: two tests that measure the same thing are worth less together than the sum of their values. So a myopic agent, which keeps buying the single observation with the largest VPI minus cost, can be suboptimal. Information will return inside POMDPs, where gathering it is just another action.

Markov decision processes and the Bellman equations

DerivationThe Bellman expectation equation
  1. Gt=Rt+1+γ(Rt+2+γRt+3+⋯)=Rt+1+γ Gt+1G_t=R_{t+1}+\gamma\big(R_{t+2}+\gamma R_{t+3}+\cdots\big)=R_{t+1}+\gamma\,G_{t+1}

    The return satisfies a one-step recursion:

  2. Vπ(s)=∑s′P(s′∣s,π(s))[R(s,π(s),s′)+γ Vπ(s′)]V^\pi(s)=\sum_{s'}P\big(s'\mid s,\pi(s)\big)\Big[R\big(s,\pi(s),s'\big)+\gamma\,V^\pi(s')\Big]

    Condition on the next state. By the Markov property the expected return from St+1=s′S_{t+1}=s' onward is Vπ(s′)V^\pi(s'), whatever happened before:

  3. Vπ=rπ+γPπVπ⟹Vπ=(I−γPπ)−1rπ=∑k≥0γk(Pπ)krπV^\pi=r^\pi+\gamma P^\pi V^\pi\quad\Longrightarrow\quad V^\pi=\big(I-\gamma P^\pi\big)^{-1}r^\pi=\sum_{k\ge0}\gamma^k\big(P^\pi\big)^kr^\pi

    In matrix form, with Pss′π=P(s′∣s,π(s))P^\pi_{ss'}=P(s'\mid s,\pi(s)) and rπr^\pi the vector of expected immediate rewards, this is a linear system. I−γPπI-\gamma P^\pi is invertible because γPπ\gamma P^\pi has row sums γ<1\gamma<1, so its Neumann series converges:

  4. V ← rπ+γPπV(iterative policy evaluation)V\ \leftarrow\ r^\pi+\gamma P^\pi V\qquad(\text{iterative policy evaluation})

    Evaluating a fixed policy therefore costs one linear solve, O(∣S∣3)\order{|S|^3}, or a few sweeps of the recursion itself.

An optimal policy maximizes the value of every state at once. Its values satisfy the Bellman optimality equation, the same recursion with a maximum over the first action:

V∗(s)=max⁡a∑s′P(s′∣s,a)[R(s,a,s′)+γV∗(s′)],π∗(s)=arg max⁡aQ∗(s,a)V^*(s)=\max_a\sum_{s'}P(s'\mid s,a)\big[R(s,a,s')+\gamma V^*(s')\big],\qquad \pi^*(s)=\argmax_aQ^*(s,a)
The max makes the system nonlinear, so a single linear solve no longer suffices. The next two steps solve it by iterating the right-hand side (value iteration), and by alternating linear solves with greedy improvements (policy iteration).

Two remarks. Discounting keeps returns finite even when episodes never end, ∣Gt∣≤Rmax⁡/(1−γ)\abs{G_t}\le R_{\max}/(1-\gamma), and the rationality lesson shows why stationary preferences over reward streams force exactly this exponential form. And nothing in the optimality equation refers to the past, which is why an optimal policy can depend on the current state alone; the Deep Layer lesson MDPs: Value & Policy Iteration proves it.

Think first In an MDP without terminal states, every reward is increased by 1. How do the values change, and does the optimal policy change?

Every VπV^\pi rises by ∑kγk=1/(1−γ)\sum_k\gamma^k=1/(1-\gamma) in every state, for every policy, so the ranking of policies, and the optimal policy, stay the same. With terminal states it is different: shifting the per-step reward changes how much it pays to end an episode early or late. That is exactly what the living-reward slider in the next widget does.

Value iteration

Value iteration turns the optimality equation into an update. Start from any V0V_0 and apply the Bellman backup BB to every state, over and over, Vk+1=BVkV_{k+1}=BV_k, where

(BV)(s)=max⁡a∑s′P(s′∣s,a)[R(s,a,s′)+γV(s′)](BV)(s)=\max_a\sum_{s'}P(s'\mid s,a)\big[R(s,a,s')+\gamma V(s')\big]
One sweep costs O(∣S∣2∣A∣)\order{|S|^2|A|}, or O(∣S∣ ∣A∣ b)\order{|S|\,|A|\,b} when each action has at most bb possible successors. With V0=0V_0=0, VkV_k is the optimal value of the problem cut off after kk steps.
text
function VALUE-ITERATION(S, A, P, R, γ, ε):
    V ← 0 for every state
    repeat
        δ ← 0
        for each state s:
            V′(s) ← max_a Σ_s′ P(s′ | s, a) · [R(s, a, s′) + γ · V(s′)]
            δ ← max(δ, |V′(s) − V(s)|)
        V ← V′
    until δ < ε · (1 − γ) / γ
    return V, and the greedy policy π(s) = argmax_a Σ_s′ P(s′ | s, a) · [R(s, a, s′) + γ · V(s′)]

The stopping rule guarantees that the returned values are within ε\varepsilon of V∗V^* in every state, as the proof below shows.

DerivationProof, and a stopping rule
  1. ∣max⁡af(a)−max⁡ag(a)∣≤max⁡a∣f(a)−g(a)∣\Big|\max_af(a)-\max_ag(a)\Big|\le\max_a\big|f(a)-g(a)\big|

    For two functions on a finite set, the maxima differ by at most the largest pointwise difference:

  2. ∣(BV)(s)−(BV′)(s)∣≤max⁡aγ∑s′P(s′∣s,a) ∣V(s′)−V′(s′)∣≤γ∥V−V′∥∞\big|(BV)(s)-(BV')(s)\big|\le\max_a\gamma\sum_{s'}P(s'\mid s,a)\,\big|V(s')-V'(s')\big|\le\gamma\norm{V-V'}_\infty

    Apply it in each state. The rewards cancel, and the transition probabilities average the differences, which cannot exceed their maximum:

  3. ∥Vk+1−V∗∥∞≤γ(∥Vk−Vk+1∥∞+∥Vk+1−V∗∥∞) ⟹ ∥Vk+1−V∗∥∞≤γ1−γ∥Vk+1−Vk∥∞\norm{V_{k+1}-V^*}_\infty\le\gamma\big(\norm{V_k-V_{k+1}}_\infty+\norm{V_{k+1}-V^*}_\infty\big)\ \Longrightarrow\ \norm{V_{k+1}-V^*}_\infty\le\frac{\gamma}{1-\gamma}\norm{V_{k+1}-V_k}_\infty

    A bound you can compute: since V∗=BV∗V^*=BV^*, go through VkV_k with the triangle inequality and rearrange:

  4. k ≥ 11−γ ln⁡Rmax⁡ε (1−γ)k\ \ge\ \frac{1}{1-\gamma}\,\ln\frac{R_{\max}}{\varepsilon\,(1-\gamma)}

    So stopping once the largest change falls below ε(1−γ)/γ\varepsilon(1-\gamma)/\gamma leaves an error below ε\varepsilon. A priori, from V0=0V_0=0 with ∣R∣≤Rmax⁡\abs{R}\le R_{\max} the initial error is at most Rmax⁡/(1−γ)R_{\max}/(1-\gamma), and since ln⁡(1/γ)≥1−γ\ln(1/\gamma)\ge1-\gamma, this many sweeps always suffice. The factor 1/(1−γ)1/(1-\gamma) is the effective horizon:

Policy iteration

Value iteration improves values and lets the policy follow. Policy iteration (Howard, 1960) does the opposite: it holds a policy, computes that policy's values exactly, improves the policy greedily, and repeats until the policy stops changing.

text
function POLICY-ITERATION(S, A, P, R, γ):
    π ← any deterministic policy
    repeat
        V ← solution of V(s) = Σ_s′ P(s′ | s, π(s)) · [R(s, π(s), s′) + γ · V(s′)]    # evaluate: O(|S|³)
        stable ← true
        for each state s:                                                            # improve
            Q(s, a) ← Σ_s′ P(s′ | s, a) · [R(s, a, s′) + γ · V(s′)]   for every a
            if max_a Q(s, a) > Q(s, π(s)):
                π(s) ← argmax_a Q(s, a);   stable ← false
    until stable
    return π, V

Changing an action only on a strict gain prevents cycling between equally good policies.

DerivationProof sketch, and termination
  1. Tπ′Vπ=BVπ ≥ TπVπ=VπT^{\pi'}V^\pi=BV^\pi\ \ge\ T^\pi V^\pi=V^\pi

    Write Tπ′T^{\pi'} for the backup that follows π′\pi', a linear version of BB. Greedy choice means that one step of π′\pi' followed by π\pi is at least as good as π\pi:

  2. Vπ≤Tπ′Vπ≤(Tπ′)2Vπ≤⋯ ⟶ Vπ′V^\pi\le T^{\pi'}V^\pi\le\big(T^{\pi'}\big)^2V^\pi\le\cdots\ \longrightarrow\ V^{\pi'}

    Tπ′T^{\pi'} is monotone (larger values in, larger values out), so applying it again preserves the inequality. The iterates converge to the fixed point of Tπ′T^{\pi'}, which is Vπ′V^{\pi'}:

  3. Vπ0≤Vπ1≤Vπ2≤⋯≤V∗,at most ∣A∣∣S∣ roundsV^{\pi_0}\le V^{\pi_1}\le V^{\pi_2}\le\cdots\le V^*,\qquad\text{at most }|A|^{|S|}\text{ rounds}

    If no state improves, BVπ=VπBV^\pi=V^\pi, so VπV^\pi is the unique fixed point of BB, namely V∗V^*. Otherwise some value rises strictly and none falls, so no policy can ever repeat; with only ∣A∣∣S∣|A|^{|S|} deterministic policies, the algorithm terminates:

Check your understanding

Policy iteration changes an action only when the new one is strictly better. Why must it terminate?

  1. The values contract by a factor γ\gamma each round, so they eventually stop changing
  2. Each round settles the action of one more state, so it stops after at most ∣S∣|S| rounds
  3. Each round raises some state's value strictly and lowers none, so no policy repeats, and there are finitely many deterministic policies
  4. The linear system gets smaller every round
Show the answer

C. Each round raises some state's value strictly and lowers none, so no policy repeats, and there are finitely many deterministic policies

By the policy improvement theorem the value functions increase monotonically, strictly until the optimum. A repeated policy would have to have the same values as before, which strict improvement rules out, and there are at most ∣A∣∣S∣|A|^{|S|} policies. In practice the number of rounds is tiny compared with that bound.

Between the two algorithms lies modified policy iteration, which evaluates each policy with a few sweeps instead of an exact solve (Puterman & Shin, 1978). There is a third exact method too: V∗V^* is the smallest function satisfying V(s)≥∑s′P(s′∣s,a)[R(s,a,s′)+γV(s′)]V(s)\ge\sum_{s'}P(s'\mid s,a)[R(s,a,s')+\gamma V(s')] for every state and action, so a linear program with ∣S∣|S| variables and ∣S∣∣A∣|S||A| constraints computes it. That proves MDPs can be solved in polynomial time; the Deep Layer derives the LP and its dual.

When the state is hidden: POMDPs

A partially observable MDP (POMDP) adds an observation model: after action aa the agent lands in s′s' but sees only an observation oo, drawn with probability Z(o∣s′,a)Z(o\mid s',a). It cannot act on the state, so it acts on a belief, a probability distribution b(s)b(s) over states given everything it has done and seen. After action aa and observation oo, the belief updates by Bayes' rule:

b′(s′)=Z(o∣s′,a)∑sP(s′∣s,a) b(s)P(o∣b,a),P(o∣b,a)=∑s′Z(o∣s′,a)∑sP(s′∣s,a) b(s)b'(s')=\frac{Z(o\mid s',a)\sum_sP(s'\mid s,a)\,b(s)}{P(o\mid b,a)},\qquad P(o\mid b,a)=\sum_{s'}Z(o\mid s',a)\sum_sP(s'\mid s,a)\,b(s)
The predict–update loop of HMM filtering from Markov Chains, HMMs & Filters, with a transition model chosen by the action.

The belief summarizes the past completely: no other function of the history predicts future observations and rewards better. So a POMDP is an MDP whose states are beliefs, with reward ρ(b,a)=∑sb(s)R(s,a)\rho(b,a)=\sum_sb(s)R(s,a). The catch is that this state space is a continuous simplex. Two landmark results, both proved in the Deep Layer: as functions of the belief, finite-horizon optimal values are piecewise linear and convex (Smallwood & Sondik, 1973), and finite-horizon POMDP planning is PSPACE-complete (Papadimitriou & Tsitsiklis, 1987), far harder than planning in MDPs.

Think first If the tiger's position were visible (a fully observable MDP), would an optimal agent ever listen?

Never. Listening costs 1 and tells the agent nothing it does not already know, so it would open the safe door at once. Information-gathering actions are worth something only under partial observability, which is why POMDP policies can look cautious, probing and roundabout.

Bandits: when the odds are unknown

Everything so far assumed a known model. When the agent must learn while acting, every action does double duty: it earns reward and it gathers information. The multi-armed bandit isolates this exploration–exploitation trade-off: one state and KK arms, where arm ii pays i.i.d. rewards with unknown mean μi\mu_i. With μ∗=max⁡iμi\mu^*=\max_i\mu_i, gaps Δi=μ∗−μi\Delta_i=\mu^*-\mu_i and Ti(n)T_i(n) the number of pulls of arm ii in nn rounds, the regret splits into a sum over arms:

Rn=nμ∗−E[∑t=1nμIt]=∑iΔi E[Ti(n)]R_n=n\mu^*-\E\Big[\sum_{t=1}^n\mu_{I_t}\Big]=\sum_i\Delta_i\,\E\big[T_i(n)\big]
Good algorithms pull each suboptimal arm only O(log⁡n)\order{\log n} times. Learning a whole MDP from experience is the subject of the reinforcement learning topic.
StrategyRuleRegret
Greedypull the best empirical meanlinear in the worst case: an unlucky start can lock it onto a bad arm forever
ε\varepsilon-greedygreedy, except a uniformly random arm with probability ε\varepsilonlinear for fixed ε\varepsilon, about εnΔˉ\varepsilon n\bar\Delta with Δˉ\bar\Delta the average gap: it explores forever
UCB1pull arg max⁡i Xˉi+2ln⁡t/Ti\argmax_i\ \bar X_i+\sqrt{2\ln t/T_i}O(∑iln⁡n/Δi)\order{\sum_i\ln n/\Delta_i}; proof in Monte Carlo Tree Search & UCT
Thompson samplingdraw θi∼Beta(1+si,1+fi)\theta_i\sim\mathrm{Beta}(1+s_i,1+f_i) for every arm, pull the largestO(log⁡n)\order{\log n}, with the optimal constant for Bernoulli arms
Xˉi\bar X_i is arm ii's empirical mean, and sis_i, fif_i count its successes and failures; the Beta posteriors are those of Bayesian Reasoning.
Check your understanding

ε\varepsilon-greedy with a fixed ε=0.1\varepsilon=0.1 plays the widget's 5-armed bandit for a million pulls. How does its regret grow with nn?

  1. Logarithmically: exploration stops mattering once the estimates are accurate
  2. Linearly: it keeps pulling a random arm on 10% of the rounds forever
  3. It stops growing once the best arm has been identified
  4. Like n\sqrt n, the minimax rate
Show the answer

B. Linearly: it keeps pulling a random arm on 10% of the rounds forever

Exploration at a fixed rate never stops: about 0.1n0.1n pulls go to uniformly random arms, each costing the average gap. Here that is 0.1×0.30=0.030.1\times0.30=0.03 per round, so about 30,000 over a million pulls. A decaying schedule εt∝1/t\varepsilon_t\propto1/t can achieve logarithmic regret, but only if its constant is tuned to the unknown gaps.

Key takeaways

  • Maximum expected utility picks arg max⁡a∑sP(s∣a,e) U(s)\argmax_a\sum_sP(s\mid a,e)\,U(s). Decision networks compute it with Bayes-net inference, and the value of perfect information, never negative, prices an observation (12 for the umbrella forecast).
  • An MDP's values satisfy Bellman equations: linear for a fixed policy, Vπ=(I−γPπ)−1rπV^\pi=(I-\gamma P^\pi)^{-1}r^\pi, and nonlinear for the optimum, V∗=BV∗V^*=BV^*.
  • The backup BB is a γ\gamma-contraction, so value iteration converges geometrically, and stopping when the changes fall below ε(1−γ)/γ\varepsilon(1-\gamma)/\gamma guarantees an error below ε\varepsilon.
  • Policy iteration alternates exact evaluation with greedy improvement. The policy improvement theorem makes the values monotone, so it terminates, usually after a handful of costly rounds.
  • A POMDP is an MDP over beliefs updated by Bayes' rule, in which gathering information has value. A bandit makes exploration explicit: regret ∑iΔiE[Ti(n)]\sum_i\Delta_i\E[T_i(n)] must grow like log⁡n\log n, and UCB1 and Thompson sampling achieve that rate.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Value iteration with γ=0.9\gamma=0.9 stops when the largest change in a sweep is 0.01. What does the contraction argument guarantee about the remaining error ∥Vk+1−V∗∥∞\norm{V_{k+1}-V^*}_\infty?

  1. At most 0.01
  2. At most 0.001
  3. At most 0.09
  4. At most 0.1
Show the answer

C. At most 0.09

∥Vk+1−V∗∥∞≤γ1−γ∥Vk+1−Vk∥∞=9×0.01=0.09\norm{V_{k+1}-V^*}_\infty\le\frac{\gamma}{1-\gamma}\norm{V_{k+1}-V_k}_\infty=9\times0.01=0.09. A small change per sweep does not mean a small error: near γ=1\gamma=1, each sweep can move the values only a little while they are still far from converged.

Question 2

Why can a fixed policy's values be computed with one linear solve, while the optimal values cannot?

  1. The fixed-policy Bellman equation has no max, so it is linear in VV; the max in the optimality equation makes it nonlinear
  2. The optimal values are not unique
  3. A fixed policy's values do not depend on the transition model
  4. Optimal values exist only for γ<0.5\gamma<0.5
Show the answer

A. The fixed-policy Bellman equation has no max, so it is linear in VV; the max in the optimality equation makes it nonlinear

Vπ=rπ+γPπVπV^\pi=r^\pi+\gamma P^\pi V^\pi is linear and solved by (I−γPπ)−1rπ(I-\gamma P^\pi)^{-1}r^\pi. The optimality equation takes a maximum over actions in every state, a piecewise-linear but nonlinear map. Value iteration iterates it; policy iteration solves a sequence of linear systems, one per policy.

Question 3

On a large MDP, policy iteration converges in 6 rounds while value iteration needs 400 sweeps. Why might value iteration still finish first?

  1. Only value iteration can be parallelized
  2. Each policy-iteration round solves a linear system in ∣S∣|S| unknowns, which can cost far more than a sweep
  3. Policy iteration may return a suboptimal policy
  4. Value iteration works on fewer states
Show the answer

B. Each policy-iteration round solves a linear system in ∣S∣|S| unknowns, which can cost far more than a sweep

A sweep costs at most O(∣S∣2∣A∣)\order{|S|^2|A|}, while an exact evaluation costs O(∣S∣3)\order{|S|^3}, which dominates when ∣S∣|S| is large. Modified policy iteration, which evaluates with a few sweeps, interpolates between the two.

Question 4

A POMDP agent tracks a belief b(s)b(s) instead of only the most likely state. What would it lose by acting as if the most likely state were certain?

  1. Nothing, as long as the most likely state has probability above one half
  2. Only some computation time
  3. The ability to use the current observation
  4. The value of its uncertainty: it would never choose an action whose only payoff is information
Show the answer

D. The value of its uncertainty: it would never choose an action whose only payoff is information

The belief is a sufficient statistic for the history; the most likely state is not. An agent that treats the likeliest state as certain never takes actions whose only value is reducing uncertainty, such as listening for the tiger, and it cannot weigh the risk of being wrong.

Question 5

In Beta–Bernoulli Thompson sampling, with what probability is arm ii pulled at round tt?

  1. 1/K1/K, until every arm has been pulled once
  2. In proportion to arm ii's empirical mean
  3. The posterior probability, given the data so far, that arm ii is the best arm
  4. 1 for the arm with the largest posterior mean, 0 for the others
Show the answer

C. The posterior probability, given the data so far, that arm ii is the best arm

Drawing one sample per arm and pulling the largest picks arm ii exactly when its sample is the largest, which happens with the posterior probability that θi\theta_i is the largest. This probability matching explores arms in proportion to how plausible it is that they are best, and a clearly bad arm's probability shrinks fast.

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapters 16–17.
  • R. S. Sutton & A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (MIT Press, 2018), chapters 2–4.
  • M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming (Wiley, 1994).
  • T. Lattimore & C. Szepesvári, Bandit Algorithms (Cambridge University Press, 2020).