Where the worst case leaves the corner: the Bayes-optimal and regularised greedy policies on two Bernoulli arms at small horizons

The corner ladder of the horizon-T Bayes-optimal policy (independent Beta(1,1) priors, fair coin at exact ties) on two Bernoulli arms is FLAT: the exact expected regret at both deterministic instances (1,0) and (0,1) is 1/2 at every horizon T <= 12. Exact rational forward dynamic programme over posterior states, with the policy itself computed in Lean by backward induction on the Bellman value table.

For every horizon T <= 2 the deterministic corner is a worst case of the Bayes-optimal policy over the WHOLE square [0,1]²: R_T(p,q) <= 1/2 at every Bernoulli instance. Two Bernstein certificates per horizon – one per triangle, for (p-q)E[N₂] and for (q-p)(T-E[N₂]) – all four at the base multidegree with no subdivision at all.

At horizon T = 3 the deterministic corner is NOT a worst case of the Bayes-optimal policy: the instance (99/100, 0), at Lⁱnf-distance 1/100 from the corner, has R₃ = 2029401/4000000 > 1/2 = R₃(1,0). Two exact rationals.

T_c = 3 for the horizon-T Bayes-optimal policy: 3 is the SMALLEST horizon at which the deterministic corner is not a worst case over [0,1]² – the two halves BO2 and BO3 in one statement. For Thompson sampling with the same prior the answer is 5 (ts-worstcase-corner TW4), so the Bayes-optimal policy leaves the corner two horizons earlier than the heuristic that approximates it.

The EXACT worst case of the horizon-4 Bayes-optimal policy over the whole square is the rational 2/3, attained at (2/3, 0). Both halves are exact – the upper bound is a polynomial inequality on the square (E[N₂(4)] = 2 + (3/2)q - (3/2)p + pq² - p² q, obtained from the state list by native_decide, then nlinarith on each triangle), the lower bound the exact rational value – and on the edge q = 0 the deficit is an exact square, 2/3 - R₄(p,0) = (3/2)(p - 2/3)².

Negative controls for the Bayes-DP column: the T <= 2 corner bound 1/2 is REFUTED at T = 3 by an explicit instance; nothing in the square beats 2/3 at T = 4, so the exact value cannot be pushed up; the region is inhabited by an instance of strictly positive regret and equal arms give regret exactly 0.

Reproduction control (the compute-first gate): THIS family's generic dynamic programme, run with the Thompson-sampling decision rule instead of a counts-based one, reproduces the certified corner ladder 1/2, 5/6, 25/24, 281/240, 2007/1600, 1983559/1512000 of the landed family ts-worstcase-corner (its row TW1) and its certified corner-derivative ladder 1/2, 2/3, 13/24, 31/120, -847/14400, -131167/378000 (row TW11, sign flip at T_c = 5 included); run with the explore-then-commit rule it reproduces that family's exact ETC(1) worst case T²/(8(T-2)) at T = 5, 6, 7 (rows TW8/TW9), attained at p - q = T/(2(T-2)).

The corner ladder of regularised greedy RG(alpha,beta) is FLAT at 1: for every (alpha,beta) in (0,0),(1,2),(2,4) and every horizon T <= 12 the exact expected regret at the deterministic instance (0,1) is 1, and at (1,0) it is 1 for every T >= 2 and 0 at T = 1. The T = 1 asymmetry is the initialisation order of arXiv:2607.29375's Algorithm 1 (Aₜ = t), and it is why every bound in this family is taken over the whole square rather than a triangle.

For every horizon strictly below its onset horizon the deterministic corner is a worst case of RG(alpha,beta) over the WHOLE square: R_T <= 1 for T <= 6 at (0,0), for T <= 9 at (1,2) and for T <= 10 at (2,4). Two Bernstein certificates per horizon (one per triangle) in the plain square coordinates, 50 certificates in all; no subdivision at all below T = 6, 7, 7 respectively, and at most a 15-node subdivision tree anywhere.

At its onset horizon each RG(alpha,beta) is beaten by an interior instance that is strictly worse than EVERY instance of the boundary of the square: at T = 7 the regret of RG(0,0) is at most 1 on all four edges (eight Bernstein certificates, every one at the base multidegree) while (7/50, 17/20) has regret > 1; at T = 10 the same for RG(1,2) with the instance (27/100, 19/25); at T = 11 the regret of RG(2,4) is at most 1011/1000 on the boundary while (29/100, 37/50) exceeds it.

The onset horizons of regularised greedy are T_c = Tₑ = 7, 10, 11 for (alpha,beta) = (0,0), (1,2), (2,4): at every smaller horizon the deterministic corner is a worst case (hence the worst case is on the boundary), and at the onset horizon a single interior instance is strictly worse than every boundary instance. Corner departure and edge departure coincide for all three policies – unlike Thompson sampling, where they are 5 and 18 (ts-worstcase-corner TW4, TW14).

Regularisation strictly delays the departure: T_c(0,0) = 7 < T_c(1,2) = 10 < T_c(2,4) = 11, stated as the four certified facts that pin the two strict inequalities (the corner is still a worst case of RG(1,2) at T = 7, where it has already failed for RG(0,0), and still a worst case of RG(2,4) at T = 10, where it has already failed for RG(1,2)).

Negative controls for the regularised-greedy column: the corner bound 1 is REFUTED at the onset horizon for all three policies; the 1011/1000 boundary bound of RG(2,4) at T = 11 is not removable slack – the boundary itself already carries more than the corner value there, witnessed by the explicit edge instance (417785/1000000, 0) – while for RG(0,0) no boundary instance at all beats the corner at T = 7; and the hypotheses are non-vacuous (strictly positive regret at the corner, exactly 0 on the diagonal).

The corner edge-derivative ladders. Along the edge q = 0 the regret is a one-variable polynomial in p and its derivative at p = 1 is an exact rational: 1/2, 0, -3/4, -1, -1, -1, -1, -1, -1, -1, -3/2, -3/2 for the Bayes-optimal policy at T = 1..12; 2^(2-T) for pure greedy and 1 then 1/2 for RG(1,2) and RG(2,4) at every 2 <= T <= 14; and, as the control, 1/2, 2/3, 13/24, 31/120, -847/14400, -131167/378000 for Thompson sampling, which is ts-worstcase-corner's certified row TW11. The derivative is a Mathlib HasDerivAt statement, not a formal-derivative convention.

The mechanism is algorithm-dependent, and the corner derivative separates the two classes. FIRST-ORDER for the Bayes-optimal policy: the edge derivative at the corner is exactly 0 at T = 2, the last horizon at which the corner is a worst case, and -3/4 < 0 at T = 3 = T_c, so the corner is not even a local maximiser along the edge there. ZEROTH-ORDER for regularised greedy: the same derivative is STRICTLY POSITIVE at every horizon 2 <= T <= 14 for all three (alpha,beta) – 1/32 at T = 6 and 1/64 at T = 7 for pure greedy – with no sign change anywhere near T_c = 7, 10, 11, so the corner remains a strict local maximiser along the edge at and past its own departure horizon and no first-order test at the corner can detect the departure.

Negative controls for the derivative rows: the Bayes-DP ladder does not stay at -1 (it is -3/2 at T = 11), the pure-greedy derivative at the departure horizon is not 0 (so the zeroth-order statement is not the vacuous 'the derivative vanishes'), and it is not constant across the departure either.

MEASUREMENT (float, unbound). UCB1 with the index Sᵢ/Nᵢ + sqrt(2 ln n / Nᵢ), n the number of plays already made, arm 1 pulled first, fair coin at exact ties: the worst case over [0,1]² at T = 1..12 is 1, 1, 1, 1, 1.208876, 1.294452, 2, 2, 2, 2, 2.015427, 2.072208, so its corner-worst set is NOT an initial segment – T_c = 5, but the corner is a worst case again at T = 7,...,10. The reason is exact: at (1,0) the trajectory is deterministic and the regret is the number of re-explorations of the dead arm, which happen at rounds 2, 7, 16, 31, 54, 87, 135, 205, 307, 455, 670, 983, 1441, 2117 (so R_T(1,0) is 1 on 2 <= T <= 6, 2 on 7 <= T <= 15, 3 on 16 <= T <= 30,...). That integer sequence is not in OEIS (queried 2026-09-07).

MEASUREMENT (float, unbound). KL-UCB with exploration function ln t (t the current round, no log-log term), arm 1 pulled first, fair coin at exact ties: the worst case over [0,1]² at T = 1..12 is 1 for T <= 7 and then 1.042075, 1.108734, 1.140842, 1.178284, 1.230835, so T_c = 8 – and, unlike regularised greedy, the corner is beaten by a BOUNDARY instance there ((0, 0.5523)), with the worst case leaving the boundary only at Tₑ = 10 (maximiser (0.0270, 0.5467)). The horizon-T Bayes-optimal policy's own worst case over the square runs 1/2, 1/2,.598076, 2/3,.716877,.764695,.816951,.847054,.900656,.937890,.983479, 1.018754 for T = 1..12, attained in the interior of the square from T = 8 on – so Tₑ(Bayes-DP) = 8, ten horizons before its analogue for Thompson sampling but five after its own T_c.