A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit
  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 and the
number of prediction periods approaches infinity, we obtain the leading order
terms of the expected regret and pseudoregret for this problem by associating
each of them with a solution of a linear parabolic partial differential
equation. Our results improve upon the previously known results; specifically
we explicitly compute the leading order term of the optimal regret and
pseudoregret in three different scaling regimes for the gap. Additionally, we
obtain new non-asymptotic bounds for any given time horizon.
