The exact minimax regret of the adversarial two-armed bandit at small horizons, with and without a switching cost

V_bandit(2,4) = 33/40: the exact minimax expected regret of the adversarial two-armed bandit with losses in 0,1, an oblivious adversary, bandit feedback (the learner sees only the loss of the arm it pulls), regret against the best fixed arm, and horizon 4 – as an ATTAINED infimum (IsLeast) over all behaviour strategies with probabilities in an arbitrary linearly ordered field, R included. The certificate is two-sided: an explicit 85-node behaviour strategy whose worst case over all 4⁴ = 256 oblivious loss matrices is exactly 33/40, and an explicit 20-point adversary distribution against which NO behaviour strategy whatsoever gets regret below 33/40

Bandit feedback first strictly costs at horizon 4, and the exact price of the missing observation there is 33/40 - 3/4 = 3/40. For T <= 3 the minimax regret of the two-armed binary-loss game is the same under bandit feedback as under full information (1/2, 1/2, 3/4), and at T = 4 it is 33/40 under bandit feedback against 3/4 under full information

V_bandit(2,1) = V_bandit(2,2) = 1/2 and V_bandit(2,3) = 3/4, each as an attained infimum over all behaviour strategies with a two-sided certificate (adversary supports 2, 2, 6) – so bandit feedback is free below horizon 4

V_full(2,T) = ceil(T/2)*C(T,floor(T/2))/2^T for T <= 5, i.e. 1/2, 1/2, 3/4, 3/4, 15/16 – Cover's 1965 value for two experts, re-derived here from the definition of the game and pinned by a two-sided certificate at every one of the five horizons (adversary supports 2, 2, 6, 6, 20). The unreduced numerators 1, 2, 6, 12, 30 are OEIS A100071

The two-sided certificate calculus for both feedback models, kernel-clean and horizon-free: for every nonnegative weighted list L of loss matrices of length n and EVERY behaviour strategy S of depth n with probabilities in [0,1], the weighted expected loss of S against L is at least the backward-induction value brB n L (bandit) or brF n L (full information) – an ordinary structural induction valid in any commutative ring with a linear order and a strict-ordered-ring structure, with no finiteness assumption on the strategy space; plus the transfer that turns a rational certificate into the statement IsLeast over an arbitrary linearly ordered field

15/16 <= V_bandit(2,5) <= 53/40, both ends by explicit kernel-bound certificates: the lower end is the optimal adversary of the FULL-INFORMATION horizon-5 game (support 20, from the (rounds-left, loss-difference) dynamic program) read under bandit feedback, the upper end is the explicit learner that plays the horizon-4 optimum for four rounds and then a fair coin, evaluated against all 4⁵ = 1024 loss matrices. With it, the measured price of the EXACT value of V_bandit(2,5): at least 4 CPU-hours in this dispatch's exact-rational Python simplex

Vₛwitch(2,T) = 3/2, 2, 7/3, 31/12, 167/60 for T = 1..5: the exact minimax expected regret of the adversarial two-armed bandit with losses in 0,1, an oblivious adversary, bandit feedback, regret against the best fixed arm, and a UNIT SWITCHING COST added to the learner's loss each time it changes arm (Dekel-Ding-Koren-Peres eq. (1), with X₀ = 0 outside the action set so the first action always counts as a switch) – each an ATTAINED infimum (IsLeast) over all behaviour strategies with probabilities in an arbitrary linearly ordered field, R included. Each value has a two-sided certificate: a behaviour strategy of 1, 5, 21, 85, 341 nodes whose worst case over all 4^T loss matrices is exactly the value, and an adversary distribution of support 2, 2, 4, 6, 8 against which NO behaviour strategy whatsoever does better

The exact price of a unit switching cost at each horizon: Vₛwitch(2,T) - V_bandit(2,T) = 1, 3/2, 19/12, 211/120 for T = 1..4, and a bracket [35/24, 443/240] at T = 5 (where the plain value is itself only bracketed, row A6). Net of DDKP's deterministic opening switch the price is 0, 1/2, 7/12, 91/120: the switching cost is free at T = 1, where there is no second round to switch into, and strictly positive from T = 2 on

The five exact values are exactly H_T + 1/2 with H_T the T-th harmonic number, and the two other readings of DDKP's first-round convention give exactly H_T (X₀ a distinguished arm) and H_T - 1/2 (no charge on round 1) at every T <= 4. A FIT TO FIVE POINTS that provably cannot continue: DDKP's Theorem 1 is Omega (T^(2/3)) for k = 2 and their section 5.1 adapts the construction to 0,1 losses, which is this family's loss model, and T^(2/3) outgrows log T. Row A12 exhibits a horizon at which it does break: T = 7

WITH A UNIT SWITCHING COST, BANDIT FEEDBACK FIRST STRICTLY COSTS AT HORIZON 3, and the exact price of the missing observation there is 7/3 - 9/4 = 1/12. VₛwitchFull(2,T) = 3/2, 2, 9/4 for T = 1..3 – the same game under full information, where the learner sees the whole loss pair each round – against Vₛwitch = 3/2, 2, 7/3 under bandit feedback. In the plain game the first separation is at T = 4 (price 3/40, row A2), so adding the switching cost moves the onset of the bandit-versus-full-information gap one horizon earlier. Each full-information value is an IsLeast over the whole space of 8-ARY behaviour strategies with a two-sided certificate (adversary supports 2, 2, 4)

The switching-cost certificate calculus, kernel-clean and horizon-free, in both feedback models: for every nonnegative weighted list L of loss matrices of length n, every previously played arm, and EVERY behaviour strategy of depth n with probabilities in [0,1], the weighted expected cost (adversarial loss plus unit switching cost) is at least the backward-induction value srB (bandit, 4-ary trees) or srF8 (full information, 8-ary trees) – an ordinary structural induction valid in any commutative ring with a linear order and a strict-ordered-ring structure, with no finiteness assumption on the strategy space; plus the transfer that turns a rational certificate into IsLeast over an arbitrary linearly ordered field

THE HARMONIC FIT FAILS AT T = 7. An explicit twelve-point adversary – the 'delayed-commitment' family: play (1,1) for j rounds (both arms lose, so the learner learns nothing while it pays), then commit to a single losing arm for the remaining T - j rounds – guarantees 373/120 against every horizon-7 behaviour strategy, and 373/120 > H₇ + 1/2 = 433/140. So Vₛwitch(2,7) > H₇ + 1/2 and the fit of row A9, exact at T <= 5, is false at T = 7. The same family with the closed-form weights w₀ = 1/T and wⱼ = 1/((T-j)(T-j+1)) for 1 <= j <= T-2, split evenly between the two arms, guarantees EXACTLY H_T + 1/2 at every horizon T = 2..10 – so H_T + 1/2 is a lower bound with a reason, and an equality only up to T = 5. Also kernel-bound: Vₛwitch(2,6) >= 59/20 = H₆ + 1/2, by the ten-point member of the same family