viewof game = {
const {q, rewards} = machines;
const state = {Q: [0, 0], N: [0, 0], history: []};
const progress = html`<span></span>`;
const total = html`<span></span>`;
const newGame = html`<button type="button" class="mab-new">New game</button>`;
newGame.onclick = () => {
const input = viewof gameNo;
input.value = randomGameNo(gameNo);
input.dispatchEvent(new Event("input", {bubbles: true}));
};
const cards = machineNames.map((name, a) => {
const reward = html`<span class="mab-reward">–</span>`;
const button = html`<button type="button" class="mab-machine"
style="--machine: ${machineColors[a]}" aria-label="Pull machine ${name}">
<span class="mab-name">Machine ${name}</span>${reward}<span class="mab-cta">Pull</span>
</button>`;
button.onclick = () => pull(a);
const stats = html`<div class="mab-stats"></div>`;
return {name, reward, button, stats};
});
const message = html`<div class="mab-message" aria-live="polite"></div>`;
const root = html`<div class="mab-game">
<div class="mab-status">${progress}${total}<span class="mab-spacer"></span>${newGame}</div>
<div class="mab-machines">${cards.map(c => html`<div>${c.button}${c.stats}</div>`)}</div>
${message}
</div>`;
// Quarto's OJS runtime gives every button in a cell output Bootstrap's .btn classes,
// whose hover, focus and disabled states would repaint these cards; take them off again.
const unstyle = new MutationObserver(() => {
for (const b of root.querySelectorAll("button.btn")) b.classList.remove("btn", "btn-quarto");
});
unstyle.observe(root, {subtree: true, attributeFilter: ["class"]});
invalidation.then(() => unstyle.disconnect());
// One pull: the first, second, ... pull of machine a pays rewards[a][0], rewards[a][1], ...
function pull(a) {
if (state.history.length >= T) return;
const Qbefore = state.Q.slice();
const greedy = Qbefore[a] === Math.max(...Qbefore);
const reward = rewards[a][state.N[a]];
state.N[a] += 1;
state.Q[a] += (reward - state.Q[a]) / state.N[a];
state.history.push({
t: state.history.length + 1, a, machine: machineNames[a], reward, greedy,
Qbefore, Q: state.Q.slice(), N: state.N.slice()
});
render();
root.value = snapshot();
root.dispatchEvent(new Event("input", {bubbles: true}));
}
function snapshot() {
return {gameNo, T, q, history: state.history.slice(), done: state.history.length === T};
}
function render() {
const t = state.history.length;
const done = t === T;
const last = state.history[t - 1];
const better = q[0] >= q[1] ? 0 : 1;
progress.replaceChildren(html`Pulls: <strong>${t}</strong> / ${T}`);
total.replaceChildren(html`Total reward: <strong>${fmt(state.history.reduce((s, h) => s + h.reward, 0))}</strong>`);
cards.forEach((c, a) => {
const own = state.history.filter(h => h.a === a);
c.reward.textContent = own.length ? signed(own[own.length - 1].reward) : "–";
c.button.classList.toggle("is-latest", last?.a === a);
c.button.disabled = done;
// Separate nodes: html`` wraps several top-level elements in one span, which would
// make the whole row a single flex item.
// The " " separators take no room in the flex row but keep the text readable.
c.stats.replaceChildren(
html`<span><i>N</i>(${c.name}) = ${state.N[a]}</span>`, " ",
html`<span><i>Q</i>(${c.name}) = ${state.N[a] ? fmt(state.Q[a]) : "0 (initial)"}</span>`,
...(done ? [" ", html`<span><i>q</i><sub>∗</sub>(${c.name}) = ${fmt(q[a])}</span>`] : []),
...(done && a === better ? [" ", html`<span class="mab-badge">better</span>`] : []));
});
if (!last) {
message.replaceChildren(html`<span class="mab-muted">Click a machine to make your first pull.</span>`);
return;
}
const a = last.a, name = last.machine, other = machineNames[1 - a];
const Qold = fmt(last.Qbefore[a], 3);
const QoldTerm = Qold.startsWith("−") ? `(${Qold})` : Qold; // R − (−0.5), not R − −0.5
const why = last.Qbefore[0] === last.Qbefore[1]
? html`both estimates were equal`
: last.greedy
? html`<i>Q</i>(${name}) = ${fmt(last.Qbefore[a])} was the higher estimate`
: html`<i>Q</i>(${name}) = ${fmt(last.Qbefore[a])} was below <i>Q</i>(${other}) = ${fmt(last.Qbefore[1 - a])}`;
message.replaceChildren(
html`<div><strong>Pull ${last.t}:</strong> machine ${name} paid <strong>${fmt(last.reward)}</strong>.
${last.greedy ? "Greedy" : "Exploratory"} pull: ${why}.</div>`,
html`<div class="mab-update"><i>N</i>(${name}) ← ${last.N[a]},
<i>Q</i>(${name}) ← ${Qold} + (${fmt(last.reward)} − ${QoldTerm}) / ${last.N[a]} = ${fmt(last.Q[a], 3)}</div>`,
...(done ? [html`<div><strong>That was your last pull.</strong> Your results are below.</div>`] : []));
}
render();
root.value = snapshot();
return root;
}7 A Two-armed Bandit Game
This game puts you in the place of the decision-maker in Multi-armed Bandits. There are two slot machines, A and B, so this is a bandit problem with k = 2 actions. Each machine has a fixed expected reward q_*(a), but you do not know these values; you only see the rewards from your own pulls. You have T pulls, and your goal is to collect as much reward as possible.
This game shows the numbers that the chapter’s algorithm keeps, so it is best played after reading the chapter. To play before reading it, start with the warm-up.
7.1 How to play
Click a machine to pull it. The machine pays a random reward around its expected reward q_*(a). Under each machine, you see the two numbers that the simple bandit algorithm of the chapter stores:
- N(a), the number of times you have pulled machine a, and
- Q(a), the average of the rewards that machine a has paid you, which is your estimate of q_*(a).
When pull t selects A_t and pays R_t, they are updated with the incremental rule
N(A_t) \leftarrow N(A_t) + 1, \qquad Q(A_t) \leftarrow Q(A_t) + \frac{1}{N(A_t)} \left( R_t - Q(A_t) \right).
A pull is greedy (exploitation) if it selects a machine with the highest current estimate, and exploratory (exploration) otherwise. A machine you have not pulled yet has the initial estimate Q(a) = 0, as in the algorithm. After your last pull, the true values q_*(a) are revealed, and your choices are compared with the \epsilon-greedy algorithm playing the same two machines.
7.2 The game
7.3 Your results
7.4 Things to think about
- When did you stop exploring, and how sure were you at that point that you had found the better machine?
- Play a few games with 10 pulls and a few with 50. Did you explore more when you had more pulls? Why does that make sense?
- Find a game in which greedy (\epsilon = 0) does clearly worse than \epsilon = 0.1. What goes wrong for an agent that never explores? Hint: think about an unlucky first reward from the better machine.
- At the end of a game, compare Q(a) with q_*(a) for each machine. Which estimate is more accurate, and why?