Partial Monitoring · Vaibhav on HTTPS

Corresponds to Lattimore & Szepesvári, Chapter 37.

Motivation: when you can’t even see your own loss

ExampleMatching pennies with costly feedback

The adversary secretly fixes $i_1, \ldots, i_n\in\{\text{heads},\text{tails}\}$ . Each round the learner picks heads, tails or uncertain. A correct guess loses 0, a wrong guess loses 1, and “uncertain” loses $c > 0$ . The twist: the learner never observes its loss. It sees nothing, unless it plays “uncertain”, in which case $i_t$ is revealed.

Replace pennies with emails and “uncertain” with “ask a human for the label”, and this is label-efficient spam filtering. Can sublinear regret be achieved, and at what rate?

IntuitionThe coupling is loosened

In bandits, the feedback is the loss of the chosen action. In partial monitoring the feedback is any known function of (action, outcome). It may reveal everything, nothing, or something in between, and informative actions may be expensive. The chapter gives an essentially complete answer for finite games: four difficulty classes, decided by linear algebra.

Finite adversarial partial monitoring

DefinitionPartial monitoring game $G = (L,\Phi)$

Loss matrix $L\in\mathbb R^{k\times d}$ (rows = $k$ actions, columns = $d$ outcomes), with $L\in[0,1]^{k\times d}$ for the upper bounds.
Feedback matrix $\Phi\in\Sigma^{k\times d}$ over a signal set $\Sigma$ . $m$ is the maximum number of distinct symbols in a row.
The adversary secretly picks outcomes $i_1, \ldots, i_n\in[d]$ . The learner, who knows $L$ and $\Phi$ , plays $A_t$ , suffers $L_{A_ti_t}$ (unseen), and observes $\sigma_t = \Phi_{A_ti_t}$ .

$R_n(\pi,i_{1:n},G) = \max_{a\in[k]}\mathbb E\Big[\sum_{t=1}^n(L_{A_ti_t} - L_{ai_t})\Big],\qquad R_n^*(G) = \inf_\pi\max_{i_{1:n}}R_n$

NoteOnly the pattern of the signals matters

Two feedback matrices carry the same information if each row has the same pattern of equal and unequal entries. The symbols themselves are arbitrary labels.

Examples

Game	$L$	$\Phi$	Minimax regret
Hopeless (37.1)	$\begin{pmatrix}0&1\\1&0\end{pmatrix}$	all $\perp$	$\Omega(n)$ : outcomes can’t be distinguished at all
Trivial (37.2)	$\begin{pmatrix}0&0\\1&1\end{pmatrix}$	all $\perp$	$0$ : action 1 dominates
Matching pennies (37.3)	$\begin{pmatrix}0&1\\1&0\\c&c\end{pmatrix}$	rows $\perp\perp$ , $\perp\perp$ , $HT$	$\Theta(n^{2/3})$ if $c > \frac12$ ; $\Theta(\sqrt n)$ if $c\le\frac12$
Bandits (37.4)	binary losses, $2^k$ columns	$\Phi = L$	$\Theta(\sqrt{kn})$
Full information (37.5)	binary losses	$\Phi_{ai} = i$	$\Theta(\sqrt{n\log k})$
Dynamic pricing (37.6)	price $p$ sells iff value $\ge p$	Y/N	structure: no sale at $3 ⇒ no sale at $4
Apple tasting (Ex. 37.5)	sell: $(-1, c)$ ; taste: $(0,0)$	sell: $\perp\perp$ ; taste: good/rotten	$\Theta(\sqrt n)$

DerivationThe

n^{2/3}

lower bound for matching pennies (

c > \frac12

)

Use a stochastic adversary with $\mathbb P(\text{heads}) = \frac12\pm\varepsilon$ . The guessing actions reveal nothing, so telling the two worlds apart requires about $1/\varepsilon^2$ plays of “uncertain”, each costing about $c - \frac12 + \varepsilon$ more than guessing. Not doing so costs $\Omega(n\varepsilon)$ (guessing wrong half the time in one of the worlds). So $R_n = \Omega(\min\{n\varepsilon, (c - \frac12 + \varepsilon)/\varepsilon^2\})$ , and $\varepsilon = n^{-1/3}$ gives $\Omega((c - \frac12)n^{2/3})$ .

For $c\le\frac12$ the argument fails. “Uncertain” is then optimal on the middle interval $u\in[c,1-c]$ (or at the single point $\frac12$ when $c = \frac12$ ). It sits between heads and tails in the cell structure, so information is available from near-optimal play, and the regret is $\Theta(\sqrt n)$ . (Classification worked here.)

DerivationApple tasting (Exercise 37.5)

Outcomes are (good, rotten) and actions are (sell, taste). As losses (= −reward): selling a good apple gives $-1$ , selling a rotten one $+c$ ; tasting gives 0 either way (a tasted apple can’t be sold). Only tasting reveals the outcome. Selling is optimal when the good-fraction is at least $c/(1+c)$ , tasting otherwise. The two actions are neighbours, and the revealing action is one of them, so the game is locally observable: $\Theta(\sqrt n)$ . Practically, minimax rates hide game-dependent constants. A farm with stochastic apples would also care about the logarithmic stochastic regret (Note 5). (Worked here.)

The structure of partial monitoring

Geometry of losses and actions

DefinitionCells and action types

Let $\ell_a$ be row $a$ of $L$ , and identify outcome $i_t$ with $u_t = e_{i_t}$ , so the loss is $\langle\ell_a,u_t\rangle$ and the adversary effectively plays the empirical frequency $\bar u_n\in\mathcal P_{d-1}$ . The cell of action $a$ is

$C_a = \Big\{u\in\mathcal P_{d-1} : \max_b\langle\ell_a - \ell_b,u\rangle\le0\Big\}$

the convex polytope of outcome distributions where $a$ is optimal.

Type	Definition	Role
Dominated	$C_a = \emptyset$	never optimal, but may be the only informative action
Pareto optimal ( $\Pi$ )	$\dim C_a = d-1$ (full-dimensional)	candidates for the best action
Degenerate	nonempty, lower-dimensional cell	optimal only on a boundary
Duplicates	$\ell_a = \ell_b$	same loss, possibly different feedback, so can’t be merged
Neighbours $(a,b)$	Pareto optimal with $\dim(C_a\cap C_b) = d-2$	adjacent cells sharing a facet
$N_a$	$a$ and its neighbours
$N_{ab}$	$\{c : C_a\cap C_b\subseteq C_c\}$	actions “on the edge” between $a$ and $b$

WarningDominated actions still matter

In matching pennies with $c > \frac12$ , “uncertain” is dominated, yet without it the game would be hopeless. Dominated and degenerate actions are never uniquely optimal, but their feedback can make a game learnable.

LemmaLemma 37.7 — The neighbourhood graph is connected

If Pareto-optimal actions $S$ have cells covering $\mathcal P_{d-1}$ , the graph on $S$ with neighbour edges is connected. So every loss difference between Pareto-optimal actions can be chained along a path of neighbour differences.

LemmaLemma 37.8 — What lies on an edge

If $(a,b)$ are neighbours and $c\in N_{ab}$ with $\ell_c\notin\{\ell_a,\ell_b\}$ , then $\ell_c = \alpha\ell_a + (1-\alpha)\ell_b$ for some $\alpha\in(0,1)$ , $C_c = C_a\cap C_b$ , and $c$ has dimension $d-2$ . So $N_{ab}$ consists of $a$ , $b$ , their duplicates, and degenerate convex combinations of them.

ProofSketch: affine hulls of faces

With $\ker_0(x) = \{u : u^\top x = 0,\ u^\top\mathbf 1 = 1\}$ : $C_a\cap C_b\subseteq C_a\cap C_c$ and both have dimension $d-2$ , so their affine hulls coincide (Exercise 37.2). Hence $\ker_0(\ell_a - \ell_b) = \ker_0(\ell_a - \ell_c)$ , and so $\ell_a - \ell_b$ and $\ell_a - \ell_c$ are proportional (Exercise 37.3), which gives $\ell_c = \alpha\ell_a + (1-\alpha)\ell_b$ . Testing at a point of $C_a$ where $a$ strictly beats $b$ forces $\alpha\le1$ , and symmetrically $\alpha > 0$ . Then $\ell_c$ is strictly beaten wherever $a$ or $b$ strictly beats something, so $C_c = C_a\cap C_b$ .

∎

Estimating loss differences

IntuitionOnly neighbour differences are needed

To compete with the best action, the learner needs neither absolute losses nor differences involving dominated actions, only differences between neighbouring Pareto-optimal actions, chained via Lemma 37.7. Example 37.9: with $L = \begin{pmatrix}0&1&10&11\\1&0&11&10\end{pmatrix}$ and feedback that can’t tell columns 1–2 from 3–4, absolute losses are unknowable, yet differences are always deducible.

DefinitionGlobal and local observability

Sample $A\sim p$ with full support and observe $\sigma = \Phi_{Ai}$ . An estimator $f(A,\sigma)/p_A$ is unbiased for $L_{ai} - L_{bi}$ against every outcome iff

$\sum_{c=1}^kf(c,\Phi_{ci}) = L_{ai} - L_{bi}\quad\forall i\in[d] \tag{37.3}$

$(a,b)$ is globally observable if such an $f$ exists. The set of such $f$ is $\mathcal E^{\mathrm{glo}}_{ab}$ .
$(a,b)$ is locally observable if such an $f$ exists with $f(c,\cdot) = 0$ for $c\notin N_{ab}$ : using only actions on the edge between $a$ and $b$ . The set is $\mathcal E^{\mathrm{loc}}_{ab}$ .

A game is globally or locally observable if every neighbouring pair is.

FormulaLinear-algebra test

Let $S_c\in\{0,1\}^{m\times d}$ be action $c$ ‘s signal matrix, with $(S_c)_{\sigma i} = \mathbb I\{\Phi_{ci} = \sigma\}$ , so $S_ce_i = e_{\Phi_{ci}}$ . Stack the $S_c$ for $c\in N_{ab}$ into $S$ . Then

$(a,b)\text{ locally observable}\iff\ell_a - \ell_b\in\mathrm{im}(S^\top)$

and the same holds globally with all $k$ actions stacked. The game’s classification is therefore computable (Exercise 37.17). By $\mathrm{im}(S^\top)\oplus\ker(S) = \mathbb R^d$ , failure means some $q\in\ker(S)$ has $\langle\ell_a - \ell_b,q\rangle\ne0$ : a direction that changes which action is better while leaving the feedback distributions unchanged.

ExampleExample 37.10 — Six actions, three outcomes

Actions 1–3 are Pareto optimal. Actions 4 and 5 are degenerate (1-dimensional cells) and action 6 is 0-dimensional. The neighbours are $(1,3)$ and $(2,3)$ , but not $(1,2)$ , whose cells meet only in a point ( $d-3$ dimensions). Both pairs are locally observable through the revealing actions 1 and 4, so the game is locally observable. $N_3 = \{1,2,3\}$ , $N_1 = \{1,3\}$ , $N_{23} = \{2,3,4\}$ .

The classification theorem

TheoremTheorem 37.11 — Classification of finite partial monitoring games

$R_n^*(G) = \begin{cases}0 & \text{no pairs of neighbouring actions (trivial)},\\ \Theta(n^{1/2}) & \text{locally observable, with neighbours (easy)},\\ \Theta(n^{2/3}) & \text{globally but not locally observable (hard)},\\ \Omega(n) & \text{not globally observable (hopeless)}.\end{cases}$

The $\Theta$ hides dependence on $k$ , $d$ , $m$ and the structure of $G$ .

ImportantThe picture

Trivial: one action is optimal everywhere.
Easy: information about every close call is available from the actions involved in it, so near-optimal play is also informative. Bandit-like.
Hard: some close call can only be resolved by playing a clearly suboptimal action. Explore-then-commit-like costs give $n^{2/3}$ .
Hopeless: some close call can’t be resolved at all.

Nothing in between exists. Two-action games are never hard: $N_{ab} = \{a,b\}$ , so global observability implies local (Exercise 37.6).

Lower bounds

NoteStochastic adversaries suffice

In stochastic partial monitoring, $I_t$ is i.i.d. with distribution $u\in\mathcal P_{d-1}$ , and $R_n(\pi,u) = \max_a\mathbb E\sum_t\langle\ell_{A_t} - \ell_a,u\rangle$ . Then $R_n^*(G)\ge\inf_\pi\max_uR_n(\pi,u)$ . Use the KL-to- $\chi^2$ bound $D(u,q)\le\sum_i(u_i - q_i)^2/q_i$ (37.4).

TheoremTheorem 37.12 — Hard games: $R_n^*\ge c_Gn^{2/3}$

If $G$ is globally but not locally observable, then $R_n^*(G)\ge c_Gn^{2/3}$ .

ProofTwo worlds that only costly actions can tell apart

Step 1: The alternatives. Take neighbours $(a,b)$ that are not locally observable, $u$ the centroid of $C_a\cap C_b$ , and $\varepsilon = \min_{c\notin N_{ab}}\langle\ell_c - \ell_a,u\rangle > 0$ (actions off the edge are strictly worse at $u$ ). Since $\ell_a - \ell_b\notin\mathrm{im}(S^\top)$ for the stack over $N_{ab}$ , there is $q$ with $Sq = 0$ , $\langle\mathbf 1,q\rangle = 0$ and $\langle\ell_a - \ell_b,q\rangle = 1$ . Set $u_a = u - \Delta q\in C_a$ and $u_b = u + \Delta q\in C_b$ , so that each world’s best action wins by $\Delta$ (37.7).

Step 2: The divergence. By the partial-monitoring divergence decomposition (Exercise 37.16), $D(\mathbb P_{u_a},\mathbb P_{u_b}) = \sum_c\mathbb E_{u_a}[T_c(n)]D(P_{cu_a},P_{cu_b})$ . Actions in $N_{ab}$ contribute zero: $S_cu_a = S_cu_b$ . Others contribute at most $\tilde C_u\Delta^2$ (data processing plus $\chi^2$ ). So $D\le\tilde C_u\Delta^2\,\mathbb E[\tilde T(n)]$ , where $\tilde T$ counts plays off the edge.

Step 3: The regret. Every play off the edge costs at least about $\varepsilon/2$ . Every edge action $c = \alpha\ell_a + (1-\alpha)\ell_b$ satisfies $\langle\ell_c - \ell_a,u_a\rangle + \langle\ell_c - \ell_b,u_b\rangle = \Delta$ , so it is $\Delta/2$ -bad in at least one world. By Bretagnolle–Huber,

$R_n(u_a) + R_n(u_b)\ge\frac\varepsilon2\mathbb E[\tilde T(n)] + \frac{n\Delta}8\exp\big(-\tilde C_u\Delta^2\mathbb E[\tilde T(n)]\big)$

Step 4: Balance. With $\Delta\approx n^{-1/3}$ : if $\mathbb E\tilde T\gtrsim n^{2/3}$ the first term is $\gtrsim n^{2/3}$ ; otherwise the exponential is constant and the second term is about $n^{2/3}$ .

∎

TheoremTheorems 37.13–37.14 — Hopeless and easy lower bounds

Not globally observable (at least two non-dominated actions): $R_n^*\ge c_Gn$ . The same construction with $q$ in the kernel of the full stack makes $D(\mathbb P_{u_a},\mathbb P_{u_b}) = 0$ for every policy, so the two worlds are perfectly indistinguishable.
Locally observable with neighbours: $R_n^*\ge c_G\sqrt n$ . Perturb the centroid toward $C_a$ or $C_b$ by $\Delta = 1/\sqrt n$ . Then $D\le c_Gn\Delta^2$ , the standard bandit-style two-point bound.
Feedback richness matters (Exercise 37.15): a locally observable two-action game with $m$ signals needs $R_n^*\ge c(m-1)\sqrt n$ .

Policy and upper bounds

DefinitionVector estimation functions $\mathcal E^{\mathrm{vec}}$

Functions $f : [k]\times\Sigma\to\mathbb R^k$ with $f(a,\sigma)_b = 0$ for $b\notin\Pi$ , and for each outcome $i$ some constant $c$ with $\sum_af(a,\Phi_{ai})_b = L_{bi} + c$ for all $b\in\Pi$ : unbiased up to a common shift, so for $A\sim p$ , $\mathbb E\big[\langle e_a - e_b,f(A,\Phi_{Ai})\rangle/p_A\big] = \langle\ell_a - \ell_b,e_i\rangle$ .

FormulaThe exponential-weights stability term

With $\Psi_q(z) = \langle q, e^{-z} + z - 1\rangle$ , which is the Bregman divergence of the dual negentropy, $D_{F^*}(\nabla F(q) - z,\nabla F(q))$ (Example 26.11), exponential weights $Q_t$ on any estimates $\hat y_t$ satisfy

$\sum_t\sum_aQ_{ta}(\hat y_{ta} - \hat y_{ta^*})\le\frac{\log k}\eta + \frac1\eta\sum_t\Psi_{Q_t}(\eta\hat y_t) \tag{37.11}$

(Theorem 28.4).

DefinitionThe exploration–estimation program

For $q$ supported on $\Pi$ ,

$\mathrm{opt}_q(\eta) = \inf_{\substack{f\in\mathcal E^{\mathrm{vec}}\\ p\in\mathrm{ri}(\mathcal P_{k-1})}}\max_{i\in[d]}\Big[\underbrace{\frac1\eta(p - q)^\top Le_i}_{\text{cost of playing }p\text{ not }q} + \underbrace{\frac1{\eta^2}\sum_ap_a\Psi_q\Big(\frac{\eta f(a,\Phi_{ai})}{p_a}\Big)}_{\text{stability of the estimates}}\Big] \tag{37.12}$

and $\mathrm{opt}^*(\eta) = \sup_q\mathrm{opt}_q(\eta)$ . The inner objective is convex because $p_a\Psi_q(\eta f/p_a)$ is a perspective of a convex function (Exercise 37.1).

AlgorithmExponential weights for partial monitoring (Algorithm 26)

Each round:

compute exponential weights $Q_t$ over the Pareto-optimal actions from past estimates;
solve (37.12) at $q = Q_t$ to precision $\varepsilon$ , obtaining the play distribution $P_t$ (which may include dominated or degenerate actions for information) and the estimator $f_t$ ;
sample $A_t\sim P_t$ and observe $\sigma_t$ ;
set $\hat y_t = f_t(A_t,\sigma_t)/P_{tA_t}$ .

IntuitionDecouple “what you’d like to play” from “what you actually play”

$Q_t$ is the exponential-weights belief about which action is best. $P_t$ is chosen to pay a little regret relative to $Q_t$ in exchange for information that keeps the loss estimates stable. This is the same trade-off as Thompson sampling’s information ratio: Algorithm 26 grew out of that analysis.

TheoremTheorem 37.15 — Generic regret bound

$R_n\le\frac{\log k}\eta + n\eta\big(\mathrm{opt}^*(\eta) + \varepsilon\big)$

Proof: split the regret into $Q_t$ ‘s regret on the estimates, bounded by (37.11) where the stability term in expectation is exactly the second part of (37.12), plus $\sum_t(P_t - Q_t)^\top Le_{i_t}$ , the first part.

TheoremTheorems 37.16–37.17 — Bounding the program

With $v_{\mathrm{glo}} = \max_e\min_{f\in\mathcal E^{\mathrm{glo}}_e}\lVert f\rVert_\infty$ and $v_{\mathrm{loc}}$ defined analogously:

Globally observable: $\mathrm{opt}^*(\eta)\le2v_{\mathrm{glo}}k^2/\sqrt\eta$ for small $\eta$ , so $R_n = O\big((v_{\mathrm{glo}}k^2n)^{2/3}(\log k)^{1/3}\big)$ .
Locally observable: $\mathrm{opt}^*(\eta)\le9k^3\max(1,v_{\mathrm{loc}}^2)$ for small $\eta$ , so $R_n = O\big(v_{\mathrm{loc}}k^{3/2}\sqrt{n\log k}\big)$ .

These are the matching upper bounds of the classification theorem.

TheoremProposition 37.18 — Size of the estimators

$v_{\mathrm{glo}}, v_{\mathrm{loc}}\le d^{1/2}k^{d/2}$ (via the smallest nonzero singular value of the integer matrix $S$ ). For locally observable non-degenerate games (all $\lvert N_e\rvert = 2$ ), $v_{\mathrm{loc}}\le m$ . These can be exponentially large in $d$ , and that is unavoidable for global observability (Exercise 37.13: $2^{d/2}$ ).

TheoremProposition 37.19 — Recovering Exp3 and Hedge

Bandits ( $\Phi = L$ ): $\mathrm{opt}^*(\eta)\le k/2$ , giving $R_n\le\sqrt{2nk\log k}$ , which is Exp3’s bound.
Full information: $\mathrm{opt}^*(\eta)\le1/2$ , giving $\sqrt{2n\log k}$ , which is exponential weights.

The program recovers the classical estimators and distributions (Exercises 37.14, 37.19).

Globally observable games (proof of Theorem 37.16)

ProofIn-trees of estimators plus uniform exploration

Step 1: Build $f$ from neighbour estimators along an in-tree. Take a directed spanning tree $T$ of the neighbourhood graph (on Pareto-optimal actions without duplicates; it exists by Lemma 37.7) with edges pointing to a root. Choose $f_e\in\mathcal E^{\mathrm{glo}}_e$ with $\lVert f_e\rVert_\infty\le v$ and set $f(a,\sigma)_b = \sum_{e\in\mathrm{path}_T(b)}f_e(a,\sigma)$ . Telescoping gives $\sum_af(a,\Phi_{ai})_b = L_{bi} - L_{\mathrm{root},i}$ , so $f\in\mathcal E^{\mathrm{vec}}$ , and $\lVert f\rVert_\infty\le kv$ .

Step 2: Explore uniformly. $p = (1-\gamma)q + \gamma\mathbf 1/k$ with $\gamma = vk^2\sqrt\eta$ . Then $\eta f/p_a\ge-\sqrt\eta\ge-1$ , so the quadratic bound $\Psi_q(z)\le\sum_bq_bz_b^2$ for $z\ge-1$ applies (the Exp3 inequality): stability $\le\sum_a\frac{(kv)^2}{\gamma/k} = \frac{k^4v^2}\gamma = \frac{k^2v}{\sqrt\eta}$ .

Step 3: the cost of exploration is $\frac\gamma\eta\le\frac{vk^2}{\sqrt\eta}$ . Summing gives $2vk^2/\sqrt\eta$ . The $1/\sqrt\eta$ is what turns $\sqrt n$ into $n^{2/3}$ .

∎

Locally observable games (proof of Theorem 37.17)

ExampleWhy uniform exploration fails, and the fix

Matching pennies with $c = \frac14$ : “uncertain” (action 3) reveals the outcome and sits between heads and tails in the neighbourhood graph (1–3–2). Take $q = p = (\frac{1-\varepsilon}2,\frac{1-\varepsilon}2,\varepsilon)$ . The natural estimator only fires on action 3, and the stability term is about $\frac1{32} + \frac{1-\varepsilon}{4\varepsilon}$ , which blows up as $\varepsilon\to0$ : most mass sits on two non-neighbours that can only be compared through a rarely played action.

Fix: move mass toward the revealing action, $p = q - \min(q_1,q_2)(e_1 + e_2) + 2\min(q_1,q_2)e_3$ . This lowers the expected loss (each unit moved from heads+tails to “uncertain” saves $1 - \frac12$ ). Shift the estimator to be zero on the most-played action. The stability term is then at most $\frac12(\frac12 + 1)$ : bounded.

FormulaDuality: one exploration plan per outcome distribution

By Sion’s theorem,

$\mathrm{opt}_q(\eta) = \max_{\lambda\in\mathcal P_{d-1}}\inf_{f,p}\Big[\frac{(p - q)^\top L\lambda}\eta + \frac1{\eta^2}\sum_i\lambda_i\sum_ap_a\Psi_q\Big(\frac{\eta f(a,\Phi_{ai})}{p_a}\Big)\Big] \tag{37.16}$

So it suffices to find a good $(p,f)$ for each fixed outcome distribution $\lambda$ , rather than one pair that works against every outcome.

Definition $T$ -increasing vectors

For an in-tree $T$ , $y\in\mathbb R^k$ is $T$ -increasing if it is constant on duplicates and increases toward the root along every tree edge, including the degenerate actions on that edge, ordered by their convex-combination weight. $T$ -decreasing means $-y$ is $T$ -increasing.

LemmaLemma 37.20 — The water transfer operator

For any in-tree $T$ and $q\in\mathcal P_{k-1}$ , some $r\in\mathcal P_{k-1}$ satisfies (a) $r\ge q/k$ , (b) $r$ is $T$ -increasing, and (c) $\langle r - q,y\rangle\le0$ for every $T$ -decreasing $y$ .

Construction (no duplicates or degenerate actions): spread each action’s mass equally over its ancestors, $r_a = \sum_{b\in\mathrm{desc}(a)}q_b/\lvert\mathrm{anc}(b)\rvert$ . Mass flows downhill toward the root, like water. Each action keeps at least $q_b/\lvert\mathrm{anc}(b)\rvert\ge q_b/k$ of its own mass. Moving mass toward lower-loss ancestors can’t increase a $T$ -decreasing loss.

LemmaLemma 37.21 — Losses are decreasing along some in-tree

For each $\lambda\in\mathcal P_{d-1}$ , some in-tree $T$ makes $L\lambda$ $T$ -decreasing. Root it at an action optimal for $\lambda$ , and let each other action’s parent be its lowest-loss neighbour. A geometric argument (segment from $\mathrm{ri}(C_b)$ to $\lambda$ crossing a neighbouring cell; Exercise 37.10) shows losses strictly decrease toward the root. Boundary $\lambda$ are handled by a limiting argument, since there are finitely many trees.

ProofProof of Theorem 37.17

Fix $\lambda$ . Take the in-tree $T$ from Lemma 37.21 and the water-transferred $r$ from Lemma 37.20. Play $p = (1-\gamma)r + \gamma\mathbf 1/k$ with $\gamma = \eta vk^2$ , and use the path-sum estimator built from local $f_e\in\mathcal E^{\mathrm{loc}}_e$ .

Stability: $f(a,\cdot)_b$ is nonzero only if $a$ lies on an edge of $\mathrm{path}_T(b)$ , and each action lies on at most two path edges. $r$ is $T$ -increasing, so for such $a$ , $r_a\ge r_b\ge q_b/k$ . Hence $\sum_a\sum_bq_bf^2/p_a\le8v^2\sum_a\sum_bq_b/r_b\le8k^3v^2$ .
Regret relative to $q$ : $\frac{1-\gamma}\eta(r - q)^\top L\lambda\le0$ by Lemma 37.20(c), since $L\lambda$ is $T$ -decreasing. Exploration adds at most $k^2v$ .

The total $9k^3\max(1,v^2)$ doesn’t depend on $\lambda$ , so (37.16) finishes the proof.

∎

ImportantWhy local observability gives $\sqrt n$

Water transfer puts mass where information is, namely the actions on the edges between the currently plausible best actions, at no extra regret, because those actions are no worse in the direction of the root. The stability term then stays $O(1)$ in $\eta$ (instead of $1/\sqrt\eta$ ), giving $\sqrt n$ .

Completing the classification

TheoremTheorem 37.22 — Trivial games

With no neighbouring actions, one action’s cell is the whole simplex, and always playing it has zero regret. Together with the lower bounds (Section 37.4) and upper bounds (Theorems 37.15–37.17), this proves Theorem 37.11.

Notes

RemarkLinear-algebra facts used

For $A\in\mathbb R^{m\times n}$ : $\mathrm{im}(A)\oplus\ker(A^\top) = \mathbb R^m$ , and the two are orthogonal. For subspaces, $(L^\perp)^\perp = L$ and $(L\cap M)^\perp = L^\perp\oplus M^\perp$ . The affine hull $\mathrm{aff}(A)$ is the set of affine combinations, and its dimension is that of the parallel subspace (Axler).

RemarkPractical aspects of Algorithm 26 (Notes 7–9)

Adaptive learning rate: $\eta_t = \min\{1/B,\sqrt{\log k/(1 + \sum_{s<t}V_s)}\}$ with $V_s = \max\{0,\mathrm{opt}_{Q_s}(\eta_s)\}$ . It avoids computing $\mathrm{opt}^*$ (which may be nonconvex in $q$ ), depends on the game only through $B$ , and yields data-dependent bounds.
Variants: penalising bias instead of requiring $f\in\mathcal E^{\mathrm{vec}}$ , and moment-generating-function objectives for high-probability bounds.
Numerics: the exponential-cone program is unstable for small $\eta$ or large $k, d$ . Replacing $\Psi_q$ by a quadratic, with constraints keeping the approximation valid, gives a second-order cone program, with the theory unchanged. Matching pennies’ $\mathrm{opt}^*$ as a function of $c$ jumps at $c = \frac12$ , reflecting the easy/hard transition (Exercise 37.18).

RemarkRefinements for easy games (Note 12)

Point-locally observable games (every pair of weak neighbours, i.e. touching cells, is pairwise observable) admit $R_n\le\frac1{\varepsilon_G}\sqrt{k_{\mathrm{loc}}n\log n}$ (Bartók 2013), and asymptotically $\limsup R_n/\sqrt n\le8(2 + m)\sqrt{2k_{\mathrm{loc}}\log k}$ (Lattimore–Szepesvári 2019), where $k_{\mathrm{loc}}$ is the largest set of Pareto-optimal actions whose cells share a point.

DefinitionRegret for hopeless games (Note 13; Rustichini 1999)

Compete with the best action against the worst outcome distribution that is indistinguishable from the actual one. With $I(p) = \{q : \sum_i(p_i - q_i)\mathbb I\{\Phi_{ai} = \sigma\} = 0\ \forall a,\sigma\}$ and $f(p) = \max_{q\in I(p)}\min_a\sum_iq_iL_{ai}$ , policies exist with $\max_{i_{1:n}}\mathbb E\big[\frac1n\sum_tL_{A_ti_t} - f(\bar u_n)\big]\to0$ , via Blackwell approachability. Rates have been obtained only recently (Mannor–Shimkin; Perchet; Mannor et al. 2014).

RemarkStochastic, contextual and continuous variants

Stochastic partial monitoring (Note 5): non-hopeless games admit logarithmic regret with a notion of asymptotic optimality (Bartók et al. 2012; Komiyama et al. 2015). The intermediate horizon regime is open.
General stochastic PM (Note 6): a kernel $P_{\theta,a}$ on (signal, reward), with the reward unobserved.
Infinite or continuous outcomes (Note 11): largely unstudied. Linear feedback structures: Lin et al. (2014); Chaudhuri–Tewari (2016, explore-then-commit, $n^{2/3}\log n$ ); Kirschner et al. (2020, IDS, including contextual).
Contextual: Bartók–Szepesvári (2012); contextual apple tasting (Helmbold et al. 2000). Compare contextual bandits.
Between bandits and full information: graph feedback, where you see your arm’s and its neighbours’ losses (Mannor–Shamir 2011; Alon et al. 2013), and Gaussian arms with action-dependent observation variances (Wu et al. 2015).

RemarkApplications (Note 10)

Spam filtering (paying for labels), dynamic pricing, medical diagnosis (ordering costly tests before treating), and factory quality control (costly destructive testing). Hard games typically arise when information must be bought.

RemarkHistory

Rustichini (1999): Hannan consistency via Blackwell approachability, with refined regret for hopeless games. Piccolboni–Schindelhauer (2001): $O(n^{3/4})$ for globally observable games. Cesa-Bianchi et al. (2006): $O(n^{2/3})$ . Foster–Rakhlin (2012): $O(\sqrt n)$ for non-degenerate locally observable games. Classification: Bartók et al. (2010, $d = 2$ ; 2014, general non-degenerate); degenerate games by Lattimore–Szepesvári (2019), who also found errors in the core proofs of earlier policies that require changing the algorithms. Beware: “neighbours” is defined differently across papers. Algorithm 26 is from Lattimore–Szepesvári (2019), following their information-theoretic analysis.

WarningStill poorly understood (Note 14)

The dependence of the regret on $k$ , $d$ , $m$ and the game’s structure is mostly unknown, the lower bounds of Section 37.4 are surely conservative, and the hopeless-game regret of Note 13 lacks tight rates in $n$ .

Quick reference

Object	Statement	Note
Game	$(L,\Phi)$ ; loss $L_{A_ti_t}$ unseen; signal $\Phi_{A_ti_t}$
Cell	$C_a = \{u : \max_b\langle\ell_a - \ell_b,u\rangle\le0\}$
Action types	dominated, Pareto optimal, degenerate, duplicate
Neighbours	Pareto optimal with $\dim(C_a\cap C_b) = d-2$	connected graph
Edge actions	$N_{ab}$ : $a$ , $b$ , duplicates, convex combinations	Lemma 37.8
Unbiased differences	$\sum_cf(c,\Phi_{ci}) = L_{ai} - L_{bi}$
Global / local	any actions / only $N_{ab}$
Test	$\ell_a - \ell_b\in\mathrm{im}(S^\top)$
Classification	trivial 0; easy $\sqrt n$ ; hard $n^{2/3}$ ; hopeless $n$
Hard lower bound	two worlds identical on $N_{ab}$ ; balance $\Delta\approx n^{-1/3}$
Stability	$\Psi_q(z) = \langle q,e^{-z} + z - 1\rangle$	dual-negentropy Bregman
Program	$\min_{p,f}\max_i[\text{regret vs }q + \text{stability}]$	convex (perspective)
Generic bound	$\frac{\log k}\eta + n\eta\,\mathrm{opt}^*(\eta)$
Global	$\mathrm{opt}^*\le2vk^2/\sqrt\eta$ ; $R_n = O((vk^2n)^{2/3}(\log k)^{1/3})$	in-tree + uniform exploration
Local	$\mathrm{opt}^*\le9k^3\max(1,v^2)$ ; $R_n = O(vk^{3/2}\sqrt{n\log k})$	Sion + water transfer
Special cases	bandits $k/2$ ; full information $1/2$	Exp3, Hedge
Estimator size	$v\le d^{1/2}k^{d/2}$ ; $v_{\mathrm{loc}}\le m$ if non-degenerate

Facts to keep to hand

Partial monitoring unifies feedback models. Bandits, full information, label-efficient prediction, pricing and apple tasting are all special cases. Only the pattern of signals matters, and only loss differences between neighbouring Pareto-optimal actions need to be learned.
Linear algebra decides the rate. If every neighbour pair’s loss difference is in the span of the signal matrices of the actions on their shared edge, the game is easy ( $\sqrt n$ ). If it needs off-edge (costly) actions, the game is hard ( $n^{2/3}$ ). If it isn’t in the span at all, the game is hopeless. Nothing in between exists.
Lower bounds hide differences in the kernel. Two outcome distributions differing along a kernel direction look identical to the uninformative actions, so either pay $\varepsilon$ per informative play or $\Delta$ per round of confusion. Balancing gives $n^{2/3}$ .
Upper bounds optimise exploration against stability. Exponential weights proposes $Q_t$ , and a convex program picks the played $P_t$ and an unbiased estimator. Global observability needs uniform exploration ( $n^{2/3}$ ). Local observability lets water transfer push mass toward informative edge actions for free ( $\sqrt n$ ), and bandits and full information fall out as special cases.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapter 37
Bartók, Foster, Pál, Rakhlin & Szepesvári, “Partial monitoring — classification, regret bounds, and algorithms” (2014)
Lattimore & Szepesvári, “Exploration by optimisation in partial monitoring” (2019)
Cesa-Bianchi & Lugosi, Prediction, Learning, and Games (2006) — Blackwell approachability