# Two-Action Apple Tasting with Switching Costs

arXiv: https://arxiv.org/abs/2606.03851 · HTML: https://mlsanity.com/paper/2606.03851/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 10 references that are in the map.
- First posted on arXiv 2 Jun 2026.

## Builds on (most cited first, 4 of 4)

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [Apple Tasting: Combinatorial Dimensions and Minimax Rates](https://mlsanity.com/paper/2310.19064/) (2023)

## Abstract (arXiv)

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 xt∈[-1,1] of the blind action; the blind action gives reward xt 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(T2/3) regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing Omega(T2/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 [ frac12√3·√ T ≤ RT^star ≤ 2√3· √T. ]