Decision Making Under Uncertainty

The prior contributes 12 "phantom observations" (2 per face). Combined with 3 real observations, we have 15 total. The prior pulls the estimate toward 1/6 ≈ 0.167, while the data (face 4 appeared 2/3 times = 0.667) pulls it up. The mean 0.267 is a compromise.

The mode is higher than the mean (0.333 vs 0.267) because the mode represents the "peak" of the posterior density, which is pulled more toward the observed data than the mean. For large sample sizes, mode and mean converge.

Dir(1,1,1) is the uniform Dirichlet — it says "any probability vector is equally likely." It contributes only 3 pseudo-counts total. Dir(10,10,10) contributes 30 pseudo-counts — like having already seen 27 evenly-distributed observations. You'd need far more data to move the posterior away from (1/3, 1/3, 1/3) with the Dir(10,10,10) prior.

The "informativeness" of a Dirichlet is controlled by ∑α_i (the concentration). Higher concentration = stronger prior = slower updates.

If we had sampled A=0 instead, the weight would be P(B=1|A=0) = 0.2. Samples consistent with evidence get high weight; inconsistent ones get low weight. Over many samples, the weighted average converges to the true posterior.

javascript
function dirichletPosteriorMean(alphas, counts) {
  const post = alphas.map((a, i) => a + counts[i]);
  const total = post.reduce((s, v) => s + v, 0);
  return post.map(v => v / total);
}

Without the sensor, refueling is optimal. The 40% chance of catastrophic failure makes launching too risky.

A positive reading dramatically increases our confidence: from 60% to 96.6%. The sensor is highly reliable (95% true positive rate), so a positive reading is very informative.

If sensor positive (P=0.59):

If sensor negative (P=0.41):

VOI:

The sensor is worth 2.69 utility. If it costs less than that, buy it. Most of the value comes from the positive case: the sensor lets us confidently launch (EU=9.56) instead of conservatively refueling (EU=5).

VOI = 0 when the optimal action is the same regardless of the observation. For example, if refueling gives EU=100 and launching gives EU=12 even in the best case — no sensor reading could possibly make launching better. The sensor would update your beliefs, but you'd still choose refuel every time. The information is useless for decision-making.

A perfectly accurate sensor can actually have high VOI (it resolves all uncertainty). And uniform priors don't guarantee VOI=0.

javascript
function computeVOI(pState, utils, sensorModel) {
  // EU without sensor
  let euNoSensor = -Infinity;
  for (let a = 0; a < utils.length; a++) {
    let eu = 0;
    for (let s = 0; s < pState.length; s++)
      eu += pState[s] * utils[a][s];
    euNoSensor = Math.max(euNoSensor, eu);
  }
  // EU with sensor
  let euWithSensor = 0;
  for (let o = 0; o < sensorModel.length; o++) {
    let pObs = 0;
    for (let s = 0; s < pState.length; s++)
      pObs += sensorModel[o][s] * pState[s];
    let bestEU = -Infinity;
    for (let a = 0; a < utils.length; a++) {
      let eu = 0;
      for (let s = 0; s < pState.length; s++) {
        let pPost = sensorModel[o][s]*pState[s]/pObs;
        eu += pPost * utils[a][s];
      }
      bestEU = Math.max(bestEU, eu);
    }
    euWithSensor += pObs * bestEU;
  }
  return euWithSensor - euNoSensor;
}

With U₀=0 everywhere, the future value is zero. The first iteration just picks the action with the highest immediate reward: fly gives 5, hover gives 2.

In turbulence, flying is dangerous (reward −1). Hovering is safe (reward 1). The greedy first-iteration policy: fly in calm, hover in turbulence.

Now future values matter! Flying gives 5 immediate reward plus 0.9×(expected future). The expected next-state value is 0.6×5 + 0.4×1 = 3.4 because flying from calm has a 60% chance of staying calm (value 5) and 40% chance of turbulence (value 1).

When γ → 0, the Bellman equation reduces to U(s) = max_a R(s,a). Future states don't matter at all. The agent is completely myopic — it grabs the biggest immediate reward without considering consequences. At γ=0.99, the agent weighs a reward 100 steps in the future at 0.99¹⁰⁰ ≈ 0.37 of its current value — still significant. At γ=0.5, that same reward is worth 0.5¹⁰⁰ ≈ 10⁻³⁰ — essentially zero.

Initialize → Bellman backup → Check convergence → Repeat → Extract policy

Initialize U=0, then repeatedly apply Bellman backups to all states. After each sweep, check if max|U_k+1(s)−U_k(s)| < ε. If not converged, repeat. Once converged, extract the greedy policy: π(s) = argmax_a [R(s,a) + γ∑T(s'|s,a)U(s')].

javascript
function bellmanBackup(state, actions, R, T, U, gamma) {
  let bestQ = -Infinity;
  for (const a of actions) {
    let q = R[state][a];
    for (const [prob, ns] of T[state][a]) {
      q += gamma * prob * U[ns];
    }
    bestQ = Math.max(bestQ, q);
  }
  return bestQ;
}

Similarly: d₂ = √(0.16+1.44) = √1.60 = 1.265, and d₃ = √(0.36+0.64) = √1.00 = 1.000. Point x₃ is closest to the query.

x₃ is closest, so it gets the largest kernel value. The kernel decays exponentially with squared distance — moving from d=1.0 to d=1.342 drops the weight from 0.607 to 0.407 (a 33% decrease).

The prediction ≈ 2.86. Point x₃ (y=4) gets the most weight (41.5%) because it's closest. The result is pulled toward y₃=4 but tempered by the other points.

As σ → ∞, exp(−d²/(2σ²)) → exp(0) = 1 for all points, regardless of distance. All kernel values become equal, so all weights become 1/n. The prediction converges to the simple average: (1+3+4)/3 = 2.667. Infinite bandwidth = maximum smoothing = global average. Conversely, as σ→0, only the nearest point matters (nearest-neighbor interpolation).

javascript
function kernelSmooth(xq, xs, ys, sigma) {
  xq = xq[0]; // unwrap single-element array
  let sumKY = 0, sumK = 0;
  for (let i = 0; i < xs.length; i++) {
    let d2 = 0;
    for (let j = 0; j < xq.length; j++)
      d2 += (xq[j] - xs[i][j]) ** 2;
    const k = Math.exp(-d2 / (2 * sigma * sigma));
    sumK += k;
    sumKY += k * ys[i];
  }
  return sumKY / sumK;
}

UCB1(hover)=3.73 > UCB1(fly)=3.43. MCTS selects Hover. Hover wins not just because it has a higher Q̄ (3.2 vs 3.0), but also because it has fewer visits (4 vs 6), giving it a larger exploration bonus. Both factors align here.

With c=5.0, the exploration term c·√(ln(N)/N(a)) becomes ~7x larger than with c=0.7. For our example, UCB1(fly) = 3.0 + 5.0×0.62 = 6.10 and UCB1(hover) = 3.2 + 5.0×0.76 = 6.99. The Q-values (3.0 vs 3.2) are dwarfed by the exploration bonuses (3.10 vs 3.80). The algorithm becomes almost purely exploratory — the visit count difference matters more than the estimated value difference.

javascript
function ucb1Score(qAvg, nAction, nTotal, c) {
  return qAvg + c * Math.sqrt(Math.log(nTotal) / nAction);
}

The gradient pushes θ₁ up by 1.43, making Boost more likely for similar states. The gradient is small because π=0.881 is already high — the policy already "wanted" to Boost, so it gets only a modest reinforcement.

Gradient normalization (or clipping) prevents catastrophically large updates when the gradient magnitude explodes — common in RL where returns can vary wildly across trajectories.

In policy gradient methods, the gradient Δθ is multiplied by the trajectory return U(τ). Returns can vary enormously: one lucky rollout might return 500 while the average is 10. That single sample creates a gradient 50x larger than normal, potentially jumping the parameters to a terrible region. Gradient clipping/normalization caps the magnitude, keeping updates stable even when returns are noisy.

CEM is a derivative-free optimization method. You don't need to differentiate through the policy or the environment — you just need to evaluate "how good is this parameter vector?" by rolling out trajectories. This makes CEM applicable to non-differentiable systems, discrete action spaces, and black-box environments. The tradeoff: CEM scales poorly with parameter dimension (it's essentially sampling in parameter space).

javascript
function gradientScale(grad, maxNorm) {
  const norm = Math.sqrt(grad.reduce((s, g) => s + g*g, 0));
  if (norm <= maxNorm || norm === 0) return [...grad];
  return grad.map(g => g * maxNorm / norm);
}

Scanning LA gives info about whether LA is high or low. s₁=LA-high, s₂=LB-high (LA is part of the state through s₁).

We need P(positive | s_i) for the scan at LA:

Actually, let's redefine cleanly. Assume each state encodes a particular mineral configuration across all sites. Let s₁,s₂ be states where LA has high minerals, and s₃,s₄ be states where LA has low minerals:

Full updated belief: b₁ = [0.389, 0.389, 0.111, 0.111]. The positive reading doubles our confidence in the "high mineral" states.

Full: b₂ ≈ [0.284, 0.284, 0.216, 0.216]. The negative LB scan decreases our belief in states where LB is high (s₁,s₂), while increasing belief in states where LB is low (s₃,s₄).

MDP value iteration computes U(s) for each state s and the policy maps states to actions. But in a POMDP, the agent never observes s directly — it only has observations. The policy must map beliefs (probability distributions over states) to actions. The belief space is continuous and (|S|−1)-dimensional, so you can't just enumerate "states." This is why POMDP solving requires specialized algorithms like point-based value iteration, QMDP, or alpha-vector methods.

javascript
function beliefUpdate(belief, obsProbs) {
  const unnorm = belief.map((b, i) => b * obsProbs[i]);
  const total = unnorm.reduce((s, v) => s + v, 0);
  return unnorm.map(v => v / total);
}

α₁ wins because our belief puts 80% probability on states s₁,s₂ (where α₁ gives +50) and only 10% on s₃ (where α₂ gives +50). The policy samples the location we're most confident about.

QMDP computes the alpha vector for action a as: α_a(s) = R(s,a) + γ∑_s'T(s'|s,a)V_MDP(s'). The V_MDP(s') is the fully observable MDP value — it assumes perfect state knowledge from step 2 onward. In reality, the agent will still be uncertain. Since V_MDP(s) ≥ V_POMDP(b) for any b consistent with s, QMDP overestimates. This means QMDP never takes information-gathering actions (like scanning) because it thinks it won't need the information.

FIB (Fast Informed Bound) helps by computing a tighter upper bound that accounts for the observation model, narrowing the gap between QMDP and the true value.

PBVI performs Bellman backups at a set of sampled belief points, explicitly incorporating the observation model. This means it can discover that "scanning before sampling" is valuable — it models the information gain. QMDP, by assuming observability, thinks information has zero value and will always skip scanning. For problems where you must gather information before acting (like the mineral survey), PBVI dramatically outperforms QMDP.

The number of conditional plans grows doubly exponentially with the horizon. Going from 2 to 3 steps multiplied the plan count by 625. This explosive growth is why exact POMDP solving is intractable for long horizons — and why approximate methods (PBVI, SARSOP, etc.) are essential.

The strong positive reading boosted b(s₁) to 69.2%, making extraction highly favorable (EU=60.73 vs abandon=5). Without the scan, the prior would give EU(extract) = (1/3)(100−20−50) = 10 — much less decisive.

Exact is impossible: with |A|=4 and |O|=3, the 10-step plan tree has astronomically many branches. QMDP can't handle information-gathering (it assumes observability after step 1). MDP ignores partial observability entirely. PBVI/SARSOP samples belief points, performs backups with full observation modeling, and scales to 50 states and horizon 10. It's the right tool: it models information value while staying computationally tractable.

javascript
function beliefDecide(belief, obsProbs, rewards) {
  // 1. Update belief
  const unnorm = belief.map((b, i) => b * obsProbs[i]);
  const total = unnorm.reduce((s, v) => s + v, 0);
  const bPost = unnorm.map(v => v / total);
  // 2. Compute EU for each action
  let bestA = 0, bestEU = -Infinity;
  for (let a = 0; a < rewards.length; a++) {
    let eu = 0;
    for (let s = 0; s < bPost.length; s++)
      eu += bPost[s] * rewards[a][s];
    if (eu > bestEU) { bestEU = eu; bestA = a; }
  }
  return { action: bestA, eu: Math.round(bestEU * 100) / 100 };
}

Note: the rounding in the return is for cleaner test comparison. In practice you'd return the raw float.

Since we already believe s₁ is likely (69.2%), and the second scan has P(pos|s₁)=0.8, a positive result is highly probable. The interesting question is whether the marginal value of this second scan justifies its cost — we already have a strong belief.