Exponential two-armed bandit problem

Alexander Kolnogorov; Denis Grunev

REVIEW 4 major objections 4 minor 10 references

Exponential two-armed bandit problem

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper establishes that, in the infinite-horizon limit, exponential two-armed bandits obey the same second-order PDE as Gaussian bandits, implying that batched processing is asymptotically as good as one-by-one play.

desk verdict Plausible and useful extension of Gaussian asymptotic analysis to exponential bandits, but the central limit interchange is unproved and one displayed equation has a typo. read the letter →

arxiv 1908.05531 v1 pith:4QEUHG3S submitted 2019-08-15 math.ST stat.TH

Alexander Kolnogorov , Denis Grunev This is my paper · ORCID

classification math.STstat.TH MSC 93E2062L0562C1062C2062F35

keywords exponentialtwo-armedbanditBayesianriskclosedistributionssecond-orderpartialdifferentialequationGaussianbatchprocessingrecursiveBellmanregret

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies a two-armed bandit whose rewards are exponentially distributed with unknown means. It derives a recursive Bellman equation for the Bayesian risk and then passes to the limit of an infinite control horizon inside the close-distributions region. The limit is a second-order partial differential equation, and the paper shows this PDE is identical to the one obtained earlier for a Gaussian two-armed bandit. Because the Gaussian bandit is known to describe batched data processing, the paper concludes that for exponential rewards batching observations does not increase Bayesian risk asymptotically compared with optimal one-by-one processing.

What carries the argument

The load-bearing object is the unnormalized Bayesian risk $\tilde r(x_1,t_1,x_2,t_2)$ evolving under the recursive equation (4.9): each arm's continuation term is an integral of $\tilde r$ against a Gamma-density kernel, rescaled with $\varepsilon=N^{-1}$ and $\delta=N^{-1/2}$. The argument works by replacing the Gamma density $f(X,n|m)$ with its Gaussian central-limit approximation, Taylor-expanding $\tilde r$ in the increment $\delta y$ and time step $\varepsilon$, and collecting terms of order $\varepsilon$ to obtain the PDE (4.15). The same PDE is then shown to follow from the Gaussian bandit's integro-difference equation, which establishes the claimed equivalence.

What would settle it

Compute the Bayesian risk for a concrete exponential two-armed bandit, say $m_1=m+\Delta$ and $m_2=m-\Delta$ with $\Delta=O(N^{-1/2})$, by solving the recursion (2.3) for growing $N$, and compare the normalized risk with the Gaussian batch-processing value predicted by (4.15); if the normalized difference does not tend to zero, the claimed limit equivalence is wrong. Alternatively, check whether the residual in (4.12) induced by the $o(\varepsilon)$ terms in (4.5) vanishes for a non-smooth value function.

Watch

Extended reading notes

Core claim

The central claim is that as the horizon length $N$ tends to infinity, the normalized Bayesian risk of the exponential two-armed bandit satisfies the same second-order PDE (equation 4.15) as the Gaussian two-armed bandit, with the same initial condition. Consequently, the exponential and Gaussian bandits have identical asymptotically optimal strategies in the close-distributions domain, and the asymptotic value of the Bayesian risk is governed by the same constant. This equivalence allows the paper to conclude that batch processing, the practical situation modeled by Gaussian bandits, does not enlarge Bayesian risk for exponential rewards in the large-$N$ limit.

Load-bearing premise

The argument assumes that replacing the Gamma density with a Gaussian approximation and Taylor-expanding the value function leave an error small enough to survive integration in the recursive equation, so that the limit equals the Gaussian bandit's PDE without extra terms.

Editorial extensions

If this is right

Bayesian strategies for exponential two-armed bandits can be approximated for large $N$ by solving the same PDE as for Gaussian bandits, so numerical methods developed for the Gaussian case carry over.
Batched processing of exponential rewards, collecting blocks before updating the strategy, does not asymptotically increase regret relative to fully sequential optimal control.
The asymptotic Bayesian risk scales as $(DN)^{1/2}$ times a constant determined by the PDE, where $D=m^2$ is the variance of an exponential reward.
The equivalence indicates that the close-distributions domain is the only region that determines the asymptotic risk, since that is where the PDE is posed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the limit interchange is valid, a similar equivalence should hold for any one-parameter exponential-family reward whose sufficient statistics satisfy a central limit theorem, because only the first two moments appear in the scaling; the paper does not explicitly discuss this extension.
A testable extension is finite-$N$ simulation of the recursive equation (2.3) for exponential rewards; one would expect the difference between batched and one-by-one Bayesian risks to vanish as $N^{-1/2}$ or faster, but the paper reports no such numerics.
The PDE formulation implicitly predicts that the asymptotic optimal strategy depends on the prior only through the initial rescaled posterior $\rho(v_1,v_2)$, a consequence of the scaling (4.1) that is not spelled out in the paper.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my read. The new content is a recursive equation for exponential two-armed bandits, a scaling limit, and the observation that the limiting PDE matches the Gaussian case [5]. If correct, it extends [5]'s asymptotic framework to exponential rewards and gives theoretical cover for batched processing. The derivation from the Bellman recursion is standard, and the bookkeeping in Section 4 is mostly careful. I believe the authors are thinking about the right objects, and the equivalence claim is likely true.

The two main weaknesses are both at the limit interchange, as expected. Eq. (4.2) replaces the Gamma density with a Gaussian uniformly, and Eq. (4.11) does a second-order Taylor expansion with an o(epsilon) remainder; both have to survive integration against an unbounded kernel. That is asserted, not proved, and it is load-bearing for the PDE (4.15). The claim that maximum expected losses occur in the close-distributions domain is also unproved. Section 5 says 'one can verify' but gives no verification, and there is a concrete typo: Eq. (5.4) as typeset has kernel argument εx1 - t1 y, whose first moment is O(ε); multiplied by δ that is O(ε^(3/2)), so it cannot produce the drift term. The intended comparison likely needs δx1 - t1 y. The self-citation to [5] is fine; that is the right comparison, and the paper does not fit parameters.

Verdict: the central conclusion is plausible, but the unproved limit interchange is serious enough that I would not treat the equivalence as established. A serious referee should ask for either a rigorous proof of the limit interchange or a convincing numerical convergence check. This is not a desk reject. It is a short, specialized paper for people working on asymptotic Bayesian bandits, and it deserves peer review with a request for revision.

Referee Report

4 major / 4 minor

Summary. The paper studies a Bayesian two-armed bandit with exponentially distributed rewards and finite horizon N. It sets up Bellman-type recursions for the risk, introduces a normalized version, and derives, in the regime where the two arm means are within O(N^{-1/2}), a limiting second-order PDE for the normalized risk. It then asserts that the Gaussian two-armed bandit from [5] leads to the same PDE and concludes that, asymptotically, batch processing does not enlarge Bayesian risk for exponential rewards.

Significance. If the derivation were rigorous, the result would be a clean asymptotic equivalence between exponential and Gaussian bandits and would extend the batch-processing optimality from Gaussian to exponential rewards. The paper is also useful for presenting explicit recursive equations and a concrete scaling. However, the central equivalence is achieved through formal asymptotics: uniform CLT approximations and Taylor expansions with uniform error controls are asserted rather than proved, and the printed Gaussian equation in (5.4) is inconsistent with the claimed limit as written. The practical conclusion is therefore conditional on closing these gaps.

major comments (4)

[Section 4, Eq. (4.2)] The replacement of the Gamma density by a Gaussian density with relative error o(1) and the resulting formula for G^(l) are used without uniform error bounds. Since the subsequent equalities (4.5) and the integrations in (4.9)-(4.12) involve unbounded functions of y and x, an error that is merely pointwise o(1) can become non-negligible after integration and after multiplication by delta and epsilon. The coefficients g^(l) in (4.3) are therefore not rigorously identified.
[Section 4, Eq. (4.11)] The Taylor expansion of tilde r(x1+delta y, t1+epsilon, x2, t2) is legitimate for the stated conclusion only if tilde r is C^2 in x1 with second derivative uniformly bounded in (x,t,N) and the o(epsilon) remainder is uniform in y over the support of the kernel f1(1+y). None of these regularity properties is proved; the kernel has unit-order variance and unbounded support, so the remainder term can in principle contribute at order delta or epsilon. Equation (4.12) and hence the PDE (4.15) rest on this unproved limit interchange.
[Section 4, first paragraph] The paper asserts without proof that the maximum expected losses take place in the domain |m1-m2| <= c N^{-1/2}. This domain restriction is the justification for the scaling (4.1) and for the entire limiting description; a reader cannot verify that the PDE characterizes the Bayesian or minimax risk of the original problem without a supporting argument or reference.
[Section 5, Eq. (5.4)] As printed, the Gaussian recursion has kernel f_{t1(t1+epsilon)}(epsilon x1 - t1 y), which gives y mean epsilon x1/t1, so the first moment of the transition is O(epsilon); after multiplication by delta the drift contribution is O(epsilon^{3/2}) and cannot produce the term r'_x1 * x1/t1 in (4.15). The claimed identity of the exponential and Gaussian limiting PDEs therefore does not follow from the equation as written. If this is a typo for delta x1 - t1 y, with a correspondingly adjusted prefactor, the argument needs to be restated; the sentence "one can verify" is not a proof.

minor comments (4)

[Section 2, Eq. (2.2)] The notation in the denominator of (2.2) uses t1 and t2, while the function is defined with arguments n1 and n2; the notation should be made consistent.
[Section 4, Eq. (4.10)] The double integral is typeset as "integral integral infinity -infinity"; it should be written as a double integral over R^2.
[Section 4, Eqs. (4.12)-(4.13)] The partial derivatives r'_t1, r'_x1, and r''_x1 x1 are used without being defined explicitly; a sentence identifying them as partial derivatives of tilde r with respect to the scaled variables would help.
[Section 5] The comparison with the Gaussian case relies entirely on the reference [5], but the paper does not state which theorem or equation from [5] is being transferred; adding a precise quotation would make the comparison checkable.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the exponential limiting PDE is derived from the paper's own recursion, and the only notable self-citation is a minor, non-forcing reference for the Gaussian comparison.

full rationale

The paper's central derivation is self-contained: Sections 2-3 construct Bayesian recursions for the exponential bandit from the stated Gamma likelihood, and Section 4 converts the discrete recursion (4.9) into the limiting PDE (4.15) via a CLT approximation and a Taylor expansion. No parameter is fitted to data, and the exponential limiting equation is not defined in terms of the Gaussian one. The comparison in Section 5 does import the Gaussian integro-difference equation (5.4) and the batch-processing interpretation from the authors' earlier paper [5], which is a self-citation; however, it is not load-bearing in a circular sense, because the exponential PDE is derived internally and the cited Gaussian result is an externally checkable published statement rather than a definition tailored to force equality. The paper does contain unproved limit interchanges, such as the uniform Taylor/CLT error needed around (4.11), and a possible typo in the kernel argument of (5.4), but these are rigor and consistency concerns, not circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the Bayesian bandit model, the Gaussian approximation of the Gamma likelihood, the smoothness of the value function, the concentration of regret in close distributions, and the prior result that Gaussian bandits describe batch processing. No data was fitted; the only hand-chosen parameter is the domain cutoff c.

free parameters (1)

c = large but finite, independent of N (unspecified)
Section 4 restricts the analysis to the close-distributions domain |m1-m2| <= c N^{-1/2}. The paper asserts that maximum expected losses occur there but does not prove it; the result should be insensitive to c for c large, but c is hand-chosen.

assumptions (5)

domain assumption Exponential reward model with unknown means m1,m2 and known prior mu(m1,m2) on a known parameter set Theta.
Section 1 defines the bandit and Bayesian risk; all subsequent results are conditional on this model.
ad hoc to paper For large n, the Gamma density f(X,n|m) is uniformly approximated by a Gaussian density with relative error o(1) over the relevant integration range.
Section 4, Eq. (4.2), uses the central limit theorem as a pointwise approximation but does not prove the uniform error needed after integration and limiting.
ad hoc to paper The value function tilde r is smooth enough for a second-order Taylor expansion with o(epsilon) remainder after integration.
Section 4, Eq. (4.11), assumes this regularity; no proof of existence or smoothness of the solution is given.
domain assumption The maximum expected losses occur in the close-distributions domain |m1-m2| <= c N^{-1/2}.
Section 4, first paragraph, states this without proof; the limiting PDE is derived only inside this domain.
domain assumption The Gaussian two-armed bandit with batch processing has the limiting description given by Eq. (4.15), as established in ref. [5].
Section 5 invokes the authors' prior paper [5] for the Gaussian batch-processing result; this is a self-cited external result, not re-derived here.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exponential two-armed bandit problem." pith.science (2026). https://pith.science/paper/4QEUHG3S

@misc{pith2026190805531,
  author       = {Pith},
  title        = {Pith review of: Exponential two-armed bandit problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4QEUHG3S}},
  note         = {Machine review of arXiv:1908.05531}
}

read the original abstract

We consider exponential two-armed bandit problem in which incomes are described by exponential distribution densities. We develop Bayesian approach and present recursive equation for determination of Bayesian strategy and Bayesian risk. In the limiting case as the control horizon goes to infinity, we obtain the second order partial differential equation in the domain of "close distributions". Results are compared with Gaussian two-armed bandit. It turned out that exponential and Gaussian two-armed bandits have the same description in the limiting case. Since Gaussian two-armed bandit describes the batch processing, this means that in case of exponential two-armed bandit batch processing does not enlarge Bayesian risk in comparison with one-by-one optimal processing as the total number of processed data items goes to infinity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 6 canonical work pages

[5]

close distributions

Comparison with Gaussian two-armed bandit. Gaussian two- armed bandit is characterized by incomes ξn, n = 1, 2,...,N , which values depend only on currently chosen actions yn∈{ 1, 2} and are described by Gaussian (normal) distribution density fD(x|m𝓁) = (2πD)−1/2 exp ( −(x−m𝓁)2/(2D) ) ,(5.1) if yn = 𝓁, 𝓁 = 1, 2. The variance D is assumed to be known and e...

work page
[1]

Exponential two-armed bandit problem

Introduction. We consider the two-armed bandit problem (see, e.g. [1, 2]) in the following setting. Let ξn, n = 1, 2,...,N , be a controlled random process which values are interpreted as incomes, depend only on currently chosen actions yn∈{ 1, 2} and are described by exponential dis- tribution density f(x|m𝓁) = { m−1 𝓁 exp(−xm−1 𝓁 ), x≥ 0, 0, x< 0,(1.1) ...

work page Pith review arXiv 2010
[2]

Recursive equation. Let’s consider control strategies{σ𝓁(X1,t 1,X 2,t 2)} which are deﬁned by a condition Pr(yn+1 =𝓁|X1,n 1,X 2,n 2) =σ𝓁(X1,n 1,X 2,n 2), where n1,n 2 are current cumulative times of both actions applications, X1,X 2 are corresponding current cumulative incomes. The posterior dis- tribution at the point of time n =n1 +n2 is calculated as µ...

work page
[3]

In this section, we obtain another version of recursive Bellman-type equation

One more version of recursive equation. In this section, we obtain another version of recursive Bellman-type equation. Let’s denote ˜R(X1,n 1,X 2,n 2) =R(X1,n 1,X 2,n 2)×µ(X1,n 1,X 2,n 2), where{R(X1,n 1,X 2,n 2)} are Bayesian risks calculated with respect to the posterior distribution (2.1) and{µ(X1,n 1,X 2,n 2)} are deﬁned in (2.2). Then the following r...

work page
[4]

close distributions

A limiting description. In this section, we present a limiting de- scription by the second order partial diﬀerential equation. We consider the domain of “close distributions”, satisfying condition |m1−m2|≤ cN−1/2 with c large enough but independent from N, because just in this domain the maximum expected losses take place. Denote ε = N−1, δ = N−1/2, so th...

work page
[6]

Berry, D. A. and Fristedt, B. (1985). Bandit Problems: Sequential Allocation of Experiments, Chapman & Hall, London

1985
[7]

Presman, E. L. and Sonin, I. M. (1990). Sequential Control with Incomplete Infor- mation: Bayesian Approach, Academic Press, New York

1990
[8]

Sragovich, V. G. (2006). Mathematical Theory of Adaptive Control , World Sci., Singapore

2006

Show all 10 references

[9]

and Lugosi

Cesa-Bianchi, N. and Lugosi. G. (2006) Prediction, Learning, and Games , Cam- bridge Univ. Press, Cambridge

2006
[10]

Kolnogorov, A. V. (2018). Gaussian Two-Armed Bandit and Optimization of Batch Data Processing. Problems of Information Transmission 54 84–100. 41 B.Saint-Petersburgskaya Str., Velikiy Novgorod, Russia, 173003 Applied Mathematics and Information Science Department E-mail: Alexa...

2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

close distributions

Comparison with Gaussian two-armed bandit. Gaussian two- armed bandit is characterized by incomes ξn, n = 1, 2,...,N , which values depend only on currently chosen actions yn∈{ 1, 2} and are described by Gaussian (normal) distribution density fD(x|m𝓁) = (2πD)−1/2 exp ( −(x−m𝓁)2/(2D) ) ,(5.1) if yn = 𝓁, 𝓁 = 1, 2. The variance D is assumed to be known and e...

work page

[2] [1]

Exponential two-armed bandit problem

Introduction. We consider the two-armed bandit problem (see, e.g. [1, 2]) in the following setting. Let ξn, n = 1, 2,...,N , be a controlled random process which values are interpreted as incomes, depend only on currently chosen actions yn∈{ 1, 2} and are described by exponential dis- tribution density f(x|m𝓁) = { m−1 𝓁 exp(−xm−1 𝓁 ), x≥ 0, 0, x< 0,(1.1) ...

work page Pith review arXiv 2010

[3] [2]

Recursive equation. Let’s consider control strategies{σ𝓁(X1,t 1,X 2,t 2)} which are deﬁned by a condition Pr(yn+1 =𝓁|X1,n 1,X 2,n 2) =σ𝓁(X1,n 1,X 2,n 2), where n1,n 2 are current cumulative times of both actions applications, X1,X 2 are corresponding current cumulative incomes. The posterior dis- tribution at the point of time n =n1 +n2 is calculated as µ...

work page

[4] [3]

In this section, we obtain another version of recursive Bellman-type equation

One more version of recursive equation. In this section, we obtain another version of recursive Bellman-type equation. Let’s denote ˜R(X1,n 1,X 2,n 2) =R(X1,n 1,X 2,n 2)×µ(X1,n 1,X 2,n 2), where{R(X1,n 1,X 2,n 2)} are Bayesian risks calculated with respect to the posterior distribution (2.1) and{µ(X1,n 1,X 2,n 2)} are deﬁned in (2.2). Then the following r...

work page

[5] [4]

close distributions

A limiting description. In this section, we present a limiting de- scription by the second order partial diﬀerential equation. We consider the domain of “close distributions”, satisfying condition |m1−m2|≤ cN−1/2 with c large enough but independent from N, because just in this domain the maximum expected losses take place. Denote ε = N−1, δ = N−1/2, so th...

work page

[6] [6]

Berry, D. A. and Fristedt, B. (1985). Bandit Problems: Sequential Allocation of Experiments, Chapman & Hall, London

1985

[7] [7]

Presman, E. L. and Sonin, I. M. (1990). Sequential Control with Incomplete Infor- mation: Bayesian Approach, Academic Press, New York

1990

[8] [8]

Sragovich, V. G. (2006). Mathematical Theory of Adaptive Control , World Sci., Singapore

2006