Two-Action Apple Tasting with Switching Costs

Tommaso Cesari; Roberto Colomboni

cs.LGJun 2, 2026

Two-Action Apple Tasting with Switching Costs

Authors: Tommaso Cesari, Roberto Colomboni

Abstract

We study the two-action apple-tasting problem with switching costs against an oblivious adversary. In an equivalent normalized formulation, at each round the learner chooses between a revealing action and a blind action: the revealing action gives reward $0$ and reveals the hidden value $x_t\in[-1,1]$ of the blind action; the blind action gives reward $x_t$ but reveals nothing. The learner pays one unit whenever they switches actions, and regret is measured against the best fixed action in hindsight. General feedback-graph algorithms with switching costs give $\widetilde O(T^{2/3})$ regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing $Ω(T^{2/3})$ obstruction in the switching-cost classification: such a lower bound would have transferred to a large family of still-unclassified feedback graphs. We prove that this obstruction is not there: the oblivious minimax expected regret for this problem satisfies

\frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T}.

Explore similar work

Aug 10, 2026cs.LG

Tracking the Best Strategy in an Extensive-Form Game

We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter

ρ>0

and achieves a switching regret of

\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T})

where

K

is the number of switches in the comparator sequence,

H

is the maximum number of the learner's information sets that can be traversed during a play of the game and

A

is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only

\mathcal{O}(H B)

where

B

is the maximum number of actions available to the learner at any of its information sets.

Stephen Pasteris, Rahul Savani, Theodore Turocy

Imperfect-Information Games

Ask PDF

Sep 14, 2026cs.LG

Bandits with Probing: Optimal Regret and the Limits of Winner Feedback

A learner probes at most

k

n

arms each round, receives the maximum of their rewards in

[0,1]

, and competes with the best fixed arm. When does the probing advantage pay for learning? We determine two minimax laws. Under independent stochastic rewards with winner feedback (the maximum and a winning label), or on arbitrary fixed sequences given a single signed contrast between block maxima, the minimax regret has order

Φ_{n,k}(T)=\min\{\frac{n-k}{n}T,\frac{n-k}{k}\}

2\le k<n

. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order

R_{n,k}(T)=\frac{n-k}{n}\min\{T,\frac{n+T}{k},\sqrt{\frac{nT}{k}}\}

. Both laws have universal constants and anytime upper bounds. The first reduces regret to a pure coverage cost: same-round contrasts absorb the stability cost, and independence permits exact resampling whose gains fund sample advancement. The second adds a learning cost that becomes comparable to coverage at horizon

n

; beyond

nk

, numerical maxima improve over labels alone. The lower bound allows every adaptive action size.

Yongjie Guan

Minimax Bandits Feedback Learning Learners

Ask PDF

Apr 28, 2026stat.ML

Online learning with Erdős-Rényi side-observation graphs

We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with a fixed but unknown probability

r

, independently of each other and the action of the learner. We propose two algorithms that work for different ranges of

r

. We show that after

T

rounds in a bandit problem with

N

arms, the expected regret of our first algorithm is

O(\sqrt{(T /r) \log N })

whenever

r\ge(\log T)/(2N)

, while our second algorithm achieves a regret of

O(\sqrt{(T/r) \log (N+T)})

for smaller values of

r

. We also give a quick estimation procedure that decides the range of~

r

. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know~

r

Tomáš Kocák, Gergely Neu, Michal Valko

Bandits Optimal Sample Complexity Exponential Random Graph Models Online Learning Arms

Ask PDF