Source
Kwon and Perchet (2017), LIT-1526, §4.1 (the algorithm), Lemma A.4 of the supplement (the estimate), Theorem 4.1 (γ) and §4.3 (outcome-dependent signals). Read in NOTE-1159. The derivation below follows Lemma A.4.
What was actually shown
At stage t the decision maker draws i_t with P[i_t = i | G_t] = (1 − γ)a_t
- γ/|I| ≥ γ/|I|, then sees s_t ~ s(i_t, j_t). The flag is f_t = (s(i, y_t))_{i∈I}, the signal law each decision would have under Nature’s current mixed action. The estimate is
f̂_t^i = 1{i_t = i} δ_{s_t} / P[i_t = i | G_t], for each i ∈ I.
Unbiased. Conditional on G_t, f̂_t^i is nonzero only on {i_t = i}, which has probability P[i_t = i | G_t]. So E[f̂_t^i | G_t] = E[δ_{s_t} | G_t, i_t = i] = E[s(i, y_t) | G_t] = E[f_t^i | G_t].
Second moment. At most one component is nonzero, and ‖δ_s‖² = 1, so E[‖f̂_t‖² | G_t] = Σ_i P[i_t = i] · 1/P[i_t = i]² = Σ_i 1/P[i_t = i] ≤ |I| · |I|/γ = |I|²/γ. Almost surely ‖f̂_t‖² ≤ (|I|/γ)².
The floor’s size. Theorem 4.1 sets γ = min{(11L_r|I||K||A|/(4‖g‖))^{2/3} T^{−1/3}, 1}. As a heuristic reading, which is the record’s and not the proof’s: exploration costs O(γ) in distance, and the estimate’s variance costs about √(|I|²/(γT)) by the second moment above. Balancing the two gives γ ∝ T^{−1/3}, and the distance then also scales as T
No floor when signals do not depend on the decision. If s(i, j) does not depend on i, then the one signal s_t has law s(i, y_t) for every i at once. So f̂_t = (δ_{s_t})_i is unbiased for every component, with ‖f̂_t‖² = |I|, without any decision being forced (§4.3).
Checked by simulation on the approach–avoid signals: avoid shows one symbol whatever the outcome, approach reveals it, the danger probability is 0.3, and the policy always avoids except for the floor. Over 2 × 10⁵ stages the estimate recovered both flags, approach’s (0.3, 0.7) to within 0.012. The empirical second moment matched Σ 1/P exactly (5.32 against 5.33 at γ = 0.5, 21.2 against 21.1 at γ = 0.1, and 99 against 101 at γ = 0.02), within the bound |I|²/γ.
What could have failed: the decision maker might have been able to infer an unplayed decision’s flag component from the others. In general it cannot, since Nature’s mixed actions that agree on the played components can differ on the rest. THEORY-962’s kernel construction is the finite case.
What this does not say
- Not that a floor is the only device. Bartók et al.’s CBP, against stochastic opponents, samples informative actions as confidence widths demand and has no fixed floor (NOTE-1164). The floor is this algorithm’s device for adversarial Nature.
- Not that the floor must be uniform. It is uniform for simplicity. The variance depends on Σ_i 1/P[i_t = i], so only the decisions whose signals matter need protecting.
- Not a prescription for organizations or people. That defensive authority removing approach is a zero floor is CLAIM-446’s reading.
- Not that the T^{−1/3} rate is caused by the floor alone. The rate is proved for this algorithm and matches a lower bound. Lemma A.4 is one of its parts.
Connections
- CLAIM-446. Its evidence-access correction is a positive floor on approach. The approach–avoid signals are decision-dependent, so the general case applies.
- THEORY-932, THEORY-925. The same frequency factor. THEORY-932’s expected update scales with how often an option is chosen, and COMA keeps a probability floor for this reason. Here the cost is explicit, as the variance Σ 1/P.
- QUESTION-271. When feedback is bandit-like, information about an untried process costs exploration. When it is outcome-dependent, it does not.
- THEORY-947. The rates this estimate serves.