The exact worst case of Thompson sampling on two Bernoulli arms at horizons up to eighteen

The exact expected regret of Thompson sampling (independent Beta(1,1) priors, Agrawal-Goyal update) at the deterministic Bernoulli instance (1, 0), horizons T = 1..8: 1/2, 5/6, 25/24, 281/240, 2007/1600, 1983559/1512000, 12736343/9408000, 9855651817/7112448000, from the exact rational forward DP over posterior states.

For every horizon T <= 4 the deterministic instance (1, 0) maximises the expected regret of Thompson sampling over the whole triangle 0 <= q <= p <= 1. Certified by a Bernstein certificate on [0,1]² in the coordinates p = q + (1-q)u, at the base multidegree with NO subdivision (every Bernstein coefficient of the difference is already nonnegative).

At horizon T = 5 the deterministic instance is NOT a worst case: R₅(49/50, 0) = 141187542923/112500000000 > 2007/1600 = R₅(1, 0), two exact rationals.

T = 5 is the SMALLEST horizon at which the deterministic instance (1, 0) is not a worst case for Thompson sampling on two Bernoulli arms – the two halves (TW2 and TW3) in one statement.

Two-sided rational enclosures of the exact worst case past the transition, where the maximiser is an irrational interior point of the edge q = 0: max R₅ in (1255002/1000000, 1255003/1000000] and max R₆ in (1330657/1000000, 1330658/1000000]. Upper bounds by Bernstein certificates with 21- and 23-node subdivision trees on the u axis; lower bounds by the exact rational instances (4893/5000, 0) and (8921/10000, 0).

Model control: P[Beta(a,b) > Beta(c,d)] computed as an order-statistic interleaving count agrees with the independent incomplete-Beta derivation on all 10⁴ quadruples with parameters <= 10; the two orientations sum to 1 and equal posteriors split evenly on all 8⁴ quadruples with parameters <= 8.

Negative controls: the T <= 4 corner bound 2007/1600 is refuted at T = 5 by an explicit instance; no instance of the triangle reaches 1255004/1000000 at T = 5, so the enclosure cannot be widened upward; the region is inhabited by an instance of strictly positive regret and equal arms give regret exactly 0; and at T = 1 the regret is exactly (p - q)/2.

The exact worst case of explore-then-commit with one exploration round per arm on two Bernoulli arms is T²/(8(T-2)) for every horizon T >= 4, attained wherever p - q = T/(2(T-2)), because T²/(8(T-2)) - R^(ETC(1))_T(p,q) = (2(T-2)(p-q) - T)²/(8(T-2)) identically.

T = 11 is the smallest horizon >= 3 at which Thompson sampling's exact worst case falls strictly below the best explore-then-commit rule's: at T = 11 every admissible ETC(m) has an instance costing more than 1.658 >= max R₁1 (certified by a 9-node Bernstein tree; minₘ worst-ETC is exactly 121/72 = 1.6805...), while at every horizon T <= 10 other than T = 2 some ETC(m)'s worst case is at most a regret Thompson sampling actually suffers.

The degenerate exception at T = 2: both admissible explore-then-commit rules have worst case exactly 1 while Thompson sampling's worst case is 5/6, so T = 2 is the one horizon below 11 at which Thompson sampling strictly wins.

The mechanism: along the edge q = 0 the regret is differentiable in p and its derivative at p = 1 changes sign exactly between the two horizons of TW4 – R'₄(1,0) = 31/120 > 0 and R'₅(1,0) = -847/14400 < 0, with the ladder 1/2, 2/3, 13/24, 31/120, -847/14400, -131167/378000 for T = 1..6. The derivative is a Mathlib HasDerivAt statement, not a formal-derivative convention.

For every horizon T <= 17 the worst case of Thompson sampling (independent Beta(1,1) priors, Agrawal-Goyal update) on two Bernoulli arms is attained on the EDGE q = 0: every instance of the triangle 0 <= q <= p <= 1 is dominated by the edge instance ((p-q)/(1-q), 0). One Bernstein certificate per horizon for R_T(u,0) - R_T(q + u(1-q), q) >= 0 on [0,1]² in the box coordinates p = q + (1-q)u; up to T = 16 every Bernstein coefficient is already nonnegative at the base multidegree (no subdivision at all), and at T = 17 two splits of the u axis suffice.

At horizon T = 18 the interior instance (29/50, 1/100), with q = 1/100 > 0, has strictly larger regret than EVERY instance of the edge q = 0: R₁8(29/50, 1/100) = 1.9764401426391007... (an exact 89-digit-over-89-digit rational) against maxᵤ R₁8(u, 0) in (1976265/10⁶, 1976266/10⁶], the upper bound by a 19-node one-variable Bernstein tree and the lower bound by the exact instance (5771/10000, 0).

T = 18 is the EDGE-DEPARTURE HORIZON: the smallest horizon at which the worst case of Thompson sampling on two Bernoulli arms is not attained on the edge q = 0 – the two halves (TW12 and TW13) in one statement.

The certified worst-case ladder of Thompson sampling at horizons T = 7..17, each enclosed on both sides to 10⁻6: (1.404396, 1.404397], (1.474045, 1.474046], (1.539283, 1.539284], (1.600311, 1.600312], (1.657475, 1.657476], (1.711140, 1.711141], (1.761644, 1.761645], (1.809293, 1.809294], (1.854356, 1.854357], (1.897070, 1.897071], (1.937644, 1.937645]; plus the edge maximum at T = 18, (1.976265, 1.976266]. Upper bounds by one-variable Bernstein certificates on the edge polynomial (15-21 nodes), lifted to the whole triangle by the edge dominance of TW12; lower bounds by exact rational edge instances.

Negative controls for the edge-departure rows: the T <= 17 edge dominance is REFUTED at T = 18 by the explicit interior instance; the T = 18 edge enclosure cannot be pushed down (1.976265 is beaten by an exact instance) and the T = 12 enclosure cannot be widened up (nothing in the triangle reaches 1.711142); the departure witness is a genuine interior point of the triangle with q > 0; and the certificate route is not degenerate – the very subdivision tree that certifies edge dominance at T = 17 evaluates to false at T = 18.

The q-derivative of the Thompson-sampling regret at the edge q = 0, as a Mathlib HasDerivAt along the box line p = q + u(1-q) with u fixed: the regret restricted to that line is differentiable in q at every point, with the derivative built by the product rule from the same state list tsTerms T that carries the regret. At the edge point u = 5771/10000 the exact rational values at q = 0, each enclosed on both sides at 10⁻6, are -.260866, -.183009, -.107287, -.034412, +.035163, +.101198 for T = 14..19; the sign changes exactly between T = 17 and T = 18.

The departure of the worst case from the edge at T = 18 is a FIRST-ORDER event at the edge: for every horizon T <= 17 and every edge point u in [0,1] the q-derivative of the regret at (u, 0) along the box line is <= 0, while at T = 18 it is strictly positive at the edge point u = 5771/10000 (in (0.035163, 0.035164)), whose regret R₁8(u,0) > 1.976265 is within 10⁻6 of the certified edge maximum <= 1.976266. Consequently, at T = 18 arbitrarily small interior steps q > 0 from that point already give R₁8(q + u(1-q), q) > R₁8(u, 0), while at every T <= 17 no infinitesimal step off the edge, from anywhere on the edge, increases the regret.

Negative controls for the derivative rows: the T = 18 edge q-derivative at u = 5771/10000 is NOT >= 0.036 and the T = 17 one is NOT <= -0.035, so neither 10⁻6 enclosure can be pushed outward; dropping the hypothesis T <= 17 makes the non-positivity statement FALSE, because the same derivative is strictly positive at T = 18; the T <= 17 bound d <= 0 is met STRICTLY at an explicit edge point, so it is not vacuous; and edge dominance at T = 18 is refuted a second time by the derivative sign alone, independently of the previous pull's Bernstein control and interior witness.