# A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 41 references that are in the map.
- First posted on arXiv 11 Feb 2022.

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

- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Prediction with Expert Advice: a PDE Perspective](https://mlsanity.com/paper/1904.11401/) (2019)
- [New Potential-Based Bounds for Prediction with Expert Advice](https://mlsanity.com/paper/1911.01641/) (2019)
- [Optimal anytime regret with two experts](https://mlsanity.com/paper/2002.08994/) (2020)
- [Finite-Time 4-Expert Prediction Problem](https://mlsanity.com/paper/1911.10936/) (2019)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [On the asymptotic optimality of the comb strategy for prediction with expert advice](https://mlsanity.com/paper/1902.02368/) (2019)
- [A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts](https://mlsanity.com/paper/2007.12732/) (2020)
- [New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice](https://mlsanity.com/paper/1912.03132/) (2019)
- [Online Prediction With History-Dependent Experts: The General Case](https://mlsanity.com/paper/2008.00052/) (2020)
- [PDE approach to the problem of online prediction with expert advice: a construction of potential-based strategies](https://mlsanity.com/paper/1705.01091/) (2017)
- [Asymptotically optimal strategies for online prediction with history-dependent experts](https://mlsanity.com/paper/2008.13703/) (2020)

## Built on by (most cited first, 3 of 3)

- [Continuous-in-time Limit for Bayesian Bandits](https://mlsanity.com/paper/2210.07513/) (2022)
- [A PDE approach for regret bounds under partial monitoring](https://mlsanity.com/paper/2209.01256/) (2022)
- [A note on continuous-time online learning](https://mlsanity.com/paper/2405.10399/) (2024)

## Abstract (arXiv)

This work addresses a version of the two-armed Bernoulli bandit problem where the sum of the means of the arms is one (the symmetric two-armed Bernoulli bandit). In a regime where the gap between these means goes to zero as the number of prediction periods approaches infinity, i.e., the difficulty of detecting the gap increases as the sample size increases, we obtain the leading order terms of the minmax optimal regret and pseudoregret for this problem by associating each of them with a solution of a linear heat equation. Our results improve upon the previously known results; specifically, we explicitly compute these leading order terms in three different scaling regimes for the gap. Additionally, we obtain new non-asymptotic bounds for any given time horizon. Although optimal player strategies are not known for more general bandit problems, there is significant interest in considering how regret accumulates under specific player strategies, even when they are not known to be optimal. We expect that the methods of this paper should be useful in settings of that type.