How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets

Valeriy Avanesov

REVIEW 2 major objections 4 minor 27 references

How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets

T0 review · 2 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 proves that a Gaussian-process bandit can handle an unknown number of abrupt reward changes, detecting them from uniform samples, and still achieve the same sub-linear regret rate as the stationary GP-UCB algorithm.

desk verdict A promising algorithm for non-stationary X-armed bandits, but Theorem 3.1's assumption is impossible as printed and the continuous-action UCB analysis is missing, so the main result is not established. read the letter →

arxiv 1908.07636 v3 pith:CU45MVG3 submitted 2019-08-20 stat.ML cs.LGmath.STstat.TH

Valeriy Avanesov This is my paper · ORCID

classification stat.MLcs.LGmath.STstat.TH MSC 62L0568T0560G15

keywords non-stationarybanditsX-armedGaussianprocesschange-pointdetectionGP-UCBcumulativeregretMatérnkernelsub-linear

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 $\mathcal{X}$-armed bandits, where an agent picks points from a continuous domain and receives noisy rewards from an unknown function, and asks what happens when that function abruptly changes at unknown times an unknown number of times. It proposes GP-UCB-CPD, which spends a controlled number of steps sampling uniformly, runs a Gaussian-process change-point detector on those samples, and resets the model whenever a change is flagged. The central result is a regret bound that stays sub-linear and, for a fixed change magnitude, matches the best known bound for the stationary GP-UCB algorithm. If correct, this means the difficulty of abrupt non-stationarity can be handled with no asymptotic overhead, while remaining adaptive to the number and size of changes.

What carries the argument

The load-bearing object is the change-point detector (Algorithm 1): it trains two Gaussian-process regressions on the first and second half of the most recent $2n$ uniformly sampled pairs, computes the $L^2$ distance $\hat\Delta^2=\int_{\mathcal X}(\mu_1(x)-\mu_2(x))^2 dx$, and compares it to a threshold $\theta_n=C(F^2+g^2\log^2T)n^{-(2\alpha+d)/(2\alpha+d+1)}$. Uniform sampling guarantees the detector sees a spread of inputs rather than a concentrated UCB cluster, so the consistency bound for GPR yields a separation between the no-change and change regimes. On detection the algorithm wipes its history and resumes GP-UCB, so each stationary interval is treated as a fresh GP-UCB run. The separation condition (3.2), namely $(\log T/\Delta)^{2+2/(2\alpha+d)} \sqrt{\max_i T_i/\min_i T_i}=o(1)$, is what gives the detector time to accumulate enough uniform samples before each change.

What would settle it

For $d=1$, $\alpha=5/2$, and change-points spaced equally with $\Delta$ held fixed, the theorem predicts $E[R_T]=O(T^{11/14}\log^3 T)$. If a simulation with these settings yields fitted regret growth close to $T^1$ rather than $T^{11/14}$, the central claim would be refuted.

Watch

Extended reading notes

Core claim

The paper's central claim is that non-stationarity can be absorbed asymptotically for free by an $\mathcal{X}$-armed bandit when the reward functions lie in a Matérn reproducing-kernel Hilbert space and changes are abrupt and separated. GP-UCB-CPD combines the GP-UCB optimistic rule with a uniform-sampling schedule that feeds a change-point detector; the detector trains Gaussian-process regressions on the two halves of the most recent $2n$ uniform samples, measures their $L^2$ distance, and compares it to a threshold. Theorem 3.1 states that for Matérn smoothness $\alpha$ in dimension $d$, minimal gap $\Delta$ between consecutive functions, and interval lengths $T_i$, expected regret is bounded by $O(\Delta^{-(2+2/(2\alpha+d))}\sum_i T_i^{(2\alpha+3d(d+1))/(4\alpha+2d(d+1))}\log^3 T)$. For fixed $\Delta$ this matches the stationary GP-UCB rate, so detecting changes carries no asymptotic overhead; for $\alpha \gg d$ the exponent approaches the minimax lower bound. The algorithm requires no knowledge of the number of change-points $K$ or of $\Delta$, and its tuning parameters depend on $\log T$ rather than $\sqrt{T}$.

Load-bearing premise

The proof relies on a regret bound that assumes the agent chooses from a finite list of options, but the algorithm's optimistic step maximizes over the whole continuous input space, and no discretization or exact-optimization procedure is specified.

Editorial extensions

If this is right

For fixed $\Delta$, the regret bound becomes $O(\sum_i T_i^p\log^3T)$ with $p=(2\alpha+3d(d+1))/(4\alpha+2d(d+1))$, identical in $T$-dependence to the stationary GP-UCB bound; the price of change detection is asymptotically zero.
As $\alpha$ grows, $p$ approaches $(\alpha+d)/(2\alpha+d)$, the minimax rate for the stationary problem, so the method is nearly optimal for very smooth reward functions.
The procedure is adaptive to the unknown number of change-points and to the minimal change magnitude, so a practitioner does not need to specify $K$ or $\Delta$ in advance.
Because all parameters depend only on $\log T$, choosing a wrong horizon $T$ degrades performance only mildly, unlike methods that need $\sqrt{T}$.
The change-point detector is a standalone tool: it can be used for regression change detection whenever uniform or sufficiently spread covariates are available.

Reading between the lines

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

The unanalyzed continuous maximization in the UCB step is the clearest place to extend the proof: adding a mesh-size or approximate-optimization term to the regret would make the finite-action bound apply to the algorithm as actually run.
The separation condition implies a phase transition: if changes arrive faster than the detector's required sample size $n^*$, the reset mechanism never gets enough uniform samples, and the regret could turn linear; probing that boundary would test the theorem's limits.
Measuring change magnitude by $L^2$ gap means localized changes on small-volume regions are hard to detect even with large pointwise effect; comparing with a sup-norm gap measure would likely produce different thresholds and rates.
The uniform-exploration fraction $\xi$ is a free design parameter; tuning it adaptively could reduce the constant overhead while preserving the asymptotic rate.

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

Colleague, this paper extends GP-UCB to piecewise-stationary X-armed bandits with an unknown number of change points, using adaptive uniform exploration and a Gaussian-process-based change-point detector. The algorithmic idea is sensible and the claimed rates—matching stationary GP-UCB for fixed change size—are the right target. But I would not take Theorem 3.1 at face value as printed. The assumption (3.2) reads (log T / Δ)^{2+2/(2α+d)} sqrt(max_i T_i / min_i T_i) = o(1). Since Δ→0, the first factor blows up and sqrt(max/min) ≥ 1, so the LHS cannot go to 0. The assumption is unsatisfiable, making the theorem vacuously true and the advertised result unestablished. The proof's actual condition (A.2) is different—a bound on n* sqrt(max T_i) by min T_i—and that one is satisfiable, so I suspect a typo in the statement, but as written the paper does not deliver the promised bound.

The second issue is the one the stress-test flagged: Lemma B.6 adapts the finite-action GP-UCB bound to the continuous set X without any discretization, mesh analysis, or exact-optimization oracle. Since Algorithm 2 uses argmax over X, the confidence band 'for all x∈X' requires an epsilon-net argument that is absent. Without it, the per-interval regret bound does not follow for the algorithm as written. This is fixable in the usual way, but it needs to be written down.

What the paper does well: the uniform-exploration schedule with CPD is a genuinely new way to adapt to unknown K and Δ, and the comparison to oracle and no-detector baselines in the 1D experiments is reasonable. The exponents in the experiments roughly match the (intended) theory. No code or data, though.

My overall read: the core idea is worth pursuing, and a serious referee should see it, but this version is not ready. The main theorem needs a corrected, satisfiable condition and the continuous-action analysis needs to be supplied. If both are fixed, this could be a solid contribution to non-stationary Bayesian optimization. As it stands, I would not rely on the result or cite it as proven.

Referee Report

2 major / 4 minor

Summary. The paper proposes an algorithm (GP-UCB-CPD) for X-armed bandits with piecewise-stationary reward functions and unknown change-points. The algorithm alternates uniform exploration with GP-UCB exploitation, using the uniformly sampled points to run a Gaussian-process change-point detector on recent tails and resetting history when a change is detected. The main result, Theorem 3.1, bounds the expected cumulative regret by O(Δ^{-(2+2/(2α+d))} Σ_i T_i^p log^3 T), where p=(2α+3d(d+1))/(4α+2d(d+1)), matching (up to a Δ factor) the stationary GP-UCB rate and implying, for fixed Δ, that change-point detection causes no asymptotic overhead. Experiments on one-dimensional Matérn-5/2 environments show exponents in T and K consistent with the theorem's predictions.

Significance. If the theorem is established, the paper provides a useful extension of GP-UCB to non-stationary environments with adaptivity to the number of change-points K and to the change magnitude Δ, without degrading the stationary rate. The change-point detection subroutine is a plausible byproduct of independent interest. The theory contains no fitted constants, and the empirical exponents (0.74 vs 0.786 for T, 0.282 vs 0.214 for K) agree well with the predicted rates. The main caveat is that the central proof relies on an unstated continuous-optimization oracle and on an imported finite-action GP-UCB bound, and the stated sublinear-regret claim is not delivered by the bound in part of the parameter regime; these issues are fixable but need to be addressed before the result is fully supported.

major comments (2)

[Section B, Lemmas B.4 and B.6] The confidence statement and per-interval regret bound are imported from the finite-action GP-UCB analysis of [19], but Algorithm 2 (line 19) maximizes the acquisition function over the continuous compact set X. Lemma B.4 claims a confidence bound for all x∈X without supplying a discretization, an ε-net or chaining argument, or an explicit exact-maximization oracle, and its proof only says 'we can replace Lemma 7.1' without providing the required union bound over the continuum. Consequently the cumulative regret bound in Lemma B.6, and with it every term in Theorem 3.1, is not established for the algorithm as written; the experiments in Section 4 use a 1000-point grid, i.e., a discretized version. The authors should either assume an exact argmax oracle and prove the continuous confidence bound under explicit Lipschitz or covering assumptions, or state the theorem for a discretized action set and incorporate the discretization error and log|D_t| factors into the regret.
[Theorem 3.1 and Abstract] The claimed sub-linear regret is not delivered by the stated bound for all α>1. The exponent p := (2α+3d(d+1))/(4α+2d(d+1)) in the first display of Theorem 3.1 exceeds 1 whenever d(d+1)>2α; for example, d=2 and α=2 give p=1.1. In such cases E[R_T]=O(T^p log^3 T) does not imply E[R_T]/T→0, so the Abstract's statement that the algorithm 'attains sub-linear cumulative regret' and the introduction's 'no-regret' claim are not consequences of the theorem as stated. The theorem should be restricted to the regime q<2α (or a separate no-regret statement should be made only there), and the Abstract and contribution list should be qualified accordingly.

minor comments (4)

[Lemma B.5] The probability statement 'at least 1−δ− exp(u)' should presumably be '1−δ−exp(−u)'; as written the claimed probability can be negative for large u.
[Section 3, footnote about Δ→0] The footnote asserts without proof that Δ can approach 0 at a polynomial rate while still matching the GP-UCB bound; please state the admissible rate explicitly or remove the claim.
[Algorithm 1 and Section 4] Algorithm 1 computes an integral over the continuous set X, but the paper gives no implementation details; the experiments appear to rely on a 1000-point discretization of X=[0,5]. Please state how the integral is computed and how the discretization relates to the theoretical guarantees.
[General typography] There are several minor typos and formatting inconsistencies (e.g., 'X -armed', duplicated 'Theorem Theorem 3.1', and the date line 'January 19, 2021' in the arXiv header); these should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the regret bound follows from independent GP-UCB and GPR-concentration results; the self-citation is not a circular load-bearing step.

full rationale

The central derivation is self-contained in the sense required by the circularity pass. Theorem 3.1 is assembled from two independent blocks: the per-interval UCB regret bound (Lemma B.6, adapted from the external GP-UCB result [19]) and the change-point detection delay estimate (Lemmas C.1-C.3). The detection analysis uses Lemma D.1, cited as 'Theorem 1 in [3]' (Avanesov, COLT 2020). Although this is a self-citation, the cited theorem is a general L2 consistency result for Gaussian process regression with sub-Gaussian noise under kernel eigenvalue and eigenfunction assumptions; it does not assume the bandit regret or any quantity from the present paper, so under Rule 4 it is independent support and does not raise the circularity score. The Delta-dependence in the regret bound is not fitted: it enters through condition (C.1), n* >= 2(C(F^2+x^2g^2)/Delta^2)^{1+1/(2alpha+d)}, which is a lower bound on the number of uniform samples needed for the detector to separate the hypotheses, combined with the spacing assumption (3.2). The experimental power-law fits (Figures 1-2) are ex-post comparisons with the theorem, not inputs to the proof. The most serious concern in the paper, namely that Lemma B.4/B.6 extend finite-action GP-UCB confidence bounds to the continuous action set without an explicit discretization or exact-optimization oracle, is a proof gap or unstated computational premise, not a circular reduction: the theorem's conclusion is not assumed in its hypotheses. Accordingly, no circular step can be exhibited, and the appropriate finding is 'no significant circularity'.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central bound rests on standard GPR concentration, spectral properties of Matérn kernels, and sufficient spacing between changes. The main hidden premise is an exact continuous maximization oracle for line 19. Tuning constants ξ, c, D, and the threshold scale are not specified constructively, which limits practical reproducibility of the guarantees. No new physical entities are introduced.

free parameters (4)

ξ (uniform exploration rate constant) = √3 in experiments
Controls how many uniform exploration steps are taken relative to history size. The theory allows any positive ξ; Section 4 sets ξ=√3 by hand.
c (CPD regularization scale) = not specified
ρ_CPD_n = c n^{-(2α+d)/(2α+d+1)}. The constant C in the threshold θ_n depends on c and the kernel, but no constructive default is given, so a practitioner must choose c without guidance.
D (UCB exploration constant in β_t) = 0.02 in experiments
β_t = D t^{d(d+1)/(2α+d(d+1))} log^4 T. The theorem says D depends on F and k but does not provide a value; experiments hand-set D=0.02.
Threshold scale in θ_n = 2.6 in experiments
θ_n = C(F² + g log²T) n^{-(2α+d)/(2α+d+1)}. The constant C is stated to depend on c and k but is not computed; experiments use θ_n = 2.6 n^{-6/7}.

assumptions (6)

domain assumption The reward functions f_i belong to the RKHS of a Matérn kernel with smoothness α > 1 and sup_i ||f_i||_k ≤ F.
Theorem 3.1 and Lemmas D.2/C.3 require this to control Gaussian process regression error and UCB bias. The norm bound F is also used to set β_t and θ_n.
domain assumption The noise ε_t is centered, independent, and sub-Gaussian with parameter g.
Definition 3.1 and Lemma B.5 rely on sub-Gaussianity to obtain uniform concentration of the noise and to choose σ² = 6g² log T.
domain assumption The eigenfunctions and eigenvalues of the Matérn covariance operator under uniform design satisfy Assumptions D.1 and D.2 with b = 2α + d.
Imported from reference [22] to apply Lemma D.1 (from the author's own prior work [3]) as the GPR consistency bound. The paper does not prove these spectral properties.
domain assumption The change-point locations are sufficiently separated so that condition (3.2), equivalently (A.2), holds.
This ensures each stationary interval is long enough for n* uniform samples to accumulate after a change and for the change-point detector to fire before the next change.
ad hoc to paper The algorithm has access to an exact maximizer of the GP-UCB acquisition function over the continuous compact set X (Algorithm 2, line 19).
This is an unstated computational premise. Lemma B.6 applies a finite-action GP-UCB bound to the continuous domain, and without an exact optimization oracle or a discretization analysis, the proof does not cover the algorithm as written.
domain assumption The reward functions are piecewise constant, changing only at the change points τ_i, with no drift within each stationary interval.
This is the formal problem setting in Section 1. The regret benchmark is an oracle that knows each f_i on each interval.

how reviews work

0 comments

Cite this review

Pith. "Pith review of How to gamble with non-stationary $\mathcal{X}$-armed bandits and have no regrets." pith.science (2026). https://pith.science/paper/CU45MVG3

@misc{pith2026190807636,
  author       = {Pith},
  title        = {Pith review of: How to gamble with non-stationary $\mathcalX$-armed bandits and have no regrets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CU45MVG3}},
  note         = {Machine review of arXiv:1908.07636}
}

abstract

In $\mathcal{X}$-armed bandit problem an agent sequentially interacts with environment which yields a reward based on the vector input the agent provides. The agent's goal is to maximise the sum of these rewards across some number of time steps. The problem and its variations have been a subject of numerous studies, suggesting sub-linear and some times optimal strategies. The given paper introduces a novel variation of the problem. We consider an environment, which can abruptly change its behaviour an unknown number of times. To that end we propose a novel strategy and prove it attains sub-linear cumulative regret. Moreover, in case of highly smooth relation between an action and the corresponding reward, the method is nearly optimal. The theoretical result are supported by experimental study.

Figures

Figures reproduced from arXiv: 1908.07636 by the authors.

**Figure 2.** Cumulative regret RT for the number of stationary periods running from 3 to 9 under fixed horizon T. The fitted curve 502K0.282 is shown with a dashed line. Both axes are in log scale. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** The plot demonstrates averaged cumulative regret of several algo [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 18 canonical work pages

[19]

Gaussian process optimization in the bandit setting: No regret and ex- perimental design

Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and ex- perimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, page 1015–1022, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077

work page 2010
[1]

Online bandit learning against an adaptive adversary: From regret to policy regret

Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: From regret to policy regret. Proceedings of the 29th International Conference on Machine Learning, ICML 2012 , 2: 1503–1510, 2012

work page 2012
[2]

Adaptively tracking the best bandit arm with an unknown number of distribution changes

Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Pro- ceedings of the Thirty-Second Conference on Learning Theory , volume 99 of Proceedings of Machine Learning Research , pages 138–158, Phoenix, USA, 25–28 Jun 2019. PMLR. URL http://proceedings.mlr.press/ v99/auer19a.html

work page 2019
[3]

Data-driven conﬁdence bands for distributed nonpara- metric regression

Valeriy Avanesov. Data-driven conﬁdence bands for distributed nonpara- metric regression. In Proceedings of the Thirty-Third Conference on Learn- ing Theory, volume 125 ofProceedings of Machine Learning Research, pages 300–322. PMLR, 09–12 Jul 2020. URL http://proceedings.mlr.press/ v125/avanesov20a.html

work page 2020
[4]

Kleinberg

Baruch Awerbuch and Robert D. Kleinberg. Adaptive routing with end- to-end feedback: Distributed learning and geometric approaches. In Pro- ceedings of the Thirty-sixth Annual ACM Symposium on Theory of Com- puting, STOC ’04, pages 45–53, New York, NY, USA, 2004. ACM. ISBN 1-58113-852-0. doi: 10.1145/1007352.1007367. URL http://doi.acm.org/ 10.1145/100735...

arXiv 2004
[5]

The ﬁnancing of innovation : learning and stopping

Dirk Bergemann and Ulrich Hege. The ﬁnancing of innovation : learning and stopping. The RAND Journal of Economics , 36, 02 2001

work page 2001
[6]

Learning and strategic pricing

Dirk Bergemann and Juuso V¨ alim¨ aki. Learning and strategic pricing. Econometrica, 64(5):1125–49, 1996. URL https://EconPapers.repec. org/RePEc:ecm:emetrp:v:64:y:1996:i:5:p:1125-49

work page 1996
[7]

Stochastic multi- armed-bandit problem with non-stationary rewards

Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi- armed-bandit problem with non-stationary rewards. In Advances in Neural Information Processing Systems 27 , pages 199–207. Cur- ran Associates, Inc., 2014. URL http://papers.nips.cc/paper/ 5378-stochastic-multi-armed-bandit-problem-with-non-stationary-rewards. pdf

work page 2014

Show all 27 references

[8]

X- armed bandits

S´ ebastien Bubeck, R´ emi Munos, Gilles Stoltz, and Csaba Szepesv´ ari. X- armed bandits. J. Mach. Learn. Res., 12:1655–1695, July 2011. ISSN 1532-

2011
[9]

Gittens and Michael Dempster

J C. Gittens and Michael Dempster. Bandit processes and dynamic allo- cation indices [with discussion]. Journal of the Royal Statistical Society. Series B: Methodological , 41:148–177, 02 1979. doi: 10.1111/j.2517-6161. 1979.tb01068.x. 20

1979 doi
[10]

Gaussian process optimization with adaptive sketch- ing: Scalable and no regret

Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketch- ing: Scalable and no regret. In Proceedings of Machine Learning Research, volume 99, pages 533–557, Phoenix, USA, 25–28 Jun 2019. P...

2019
[11]

Nearly optimal adaptive procedure with change detection for piecewise-stationary ban- dit

Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationary ban- dit. In Proceedings of Machine Learning Research, volume 89, pages 418–
[12]

On kernelized multi-armed bandits

Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. 34th International Conference on Machine Learning, ICML 2017 , 2:1397–1422, 2017

2017
[13]

High-Dimensional Gaussian Process Bandits

Josip Djolonga, Andreas Krause, and Volkan Cevher. High-Dimensional Gaussian Process Bandits. Advances in Neural Information Processing Sys- tems 26, pages 1025–1033, 2013. ISSN 10495258

2013
[14]

J. C. Gittins. Multi-armed Bandit Allocation Indices . Wiley, Chichester, NY, 1989

1989
[15]

J. C. Gittins and D. M. Jones. A dynamic allocation index for the dis- counted multiarmed bandit problem. Biometrika, 66(3):561–565, 1979. ISSN 00063444. URL http://www.jstor.org/stable/2335176

1979
[16]

Kleinberg and T

R. Kleinberg and T. Leighton. The value of knowing a demand curve: bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594–605, Oct 2003. doi: 10.1109/SFCS.2003.1238232

2003 arXiv
[17]

Gaussian Processes for Machine Learning

Rasmussen and Williams. Gaussian Processes for Machine Learning. MIT Press, 2006. ISBN 026218253X. doi: 10.1142/S0129065704001899

2006 doi
[18]

Lower bounds on regret for noisy Gaussian process bandit optimization

Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proceedings of Machine Learning Research , volume 65, pages 1723–1742, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR. URL http://proceedings.mlr. pre...

2017
[20]

P. Whittle. Arm-acquiring bandits. Ann. Probab. , 9(2):284–292, 04
[21]

P. Whittle. Restless bandits: Activity allocation in a changing world. Journal of Applied Probability , 25:287–298, 1988. ISSN 00219002. URL http://www.jstor.org/stable/3214163

1988
[22]

Bayesian model selection consistency and oracle inequality with intractable marginal likelihood

Yun Yang and Debdeep Pati. Bayesian model selection consistency and oracle inequality with intractable marginal likelihood. pages 1–38, 2017. URL http://arxiv.org/abs/1701.00311

2017 arXiv
[23]

Linear submodular bandits and their ap- plication to diversiﬁed retrieval

Yisong Yue and Carlos Guestrin. Linear submodular bandits and their ap- plication to diversiﬁed retrieval. In Advances in Neural Information Pro- cessing Systems 24 , pages 2483–2491. Curran Associates, Inc., 2011

2011
[24]

M. Zelen. Play the winner rule and the controlled clinical trial. Journal of the American Statistical Association, 64(325):131–146, 1969. doi: 10.1080/ 01621459.1969.10500959. URL https://www.tandfonline.com/doi/abs/ 10.1080/01621459.1969.10500959. 22

1969
[427]

URL http://proceedings.mlr.press/v89/ cao19a.html

PMLR, 16–18 Apr 2019. URL http://proceedings.mlr.press/v89/ cao19a.html

2019
[1981]

URL https://doi.org/10.1214/ aop/1176994469

doi: 10.1214/aop/1176994469. URL https://doi.org/10.1214/ aop/1176994469. 21
[4435]

URL http://dl.acm.org/citation.cfm?id=1953048.2021053

Pith tools

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

[1] [19]

Gaussian process optimization in the bandit setting: No regret and ex- perimental design

Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and ex- perimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, page 1015–1022, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077

work page 2010

[2] [1]

Online bandit learning against an adaptive adversary: From regret to policy regret

Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: From regret to policy regret. Proceedings of the 29th International Conference on Machine Learning, ICML 2012 , 2: 1503–1510, 2012

work page 2012

[3] [2]

Adaptively tracking the best bandit arm with an unknown number of distribution changes

Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Pro- ceedings of the Thirty-Second Conference on Learning Theory , volume 99 of Proceedings of Machine Learning Research , pages 138–158, Phoenix, USA, 25–28 Jun 2019. PMLR. URL http://proceedings.mlr.press/ v99/auer19a.html

work page 2019

[4] [3]

Data-driven conﬁdence bands for distributed nonpara- metric regression

Valeriy Avanesov. Data-driven conﬁdence bands for distributed nonpara- metric regression. In Proceedings of the Thirty-Third Conference on Learn- ing Theory, volume 125 ofProceedings of Machine Learning Research, pages 300–322. PMLR, 09–12 Jul 2020. URL http://proceedings.mlr.press/ v125/avanesov20a.html

work page 2020

[5] [4]

Kleinberg

Baruch Awerbuch and Robert D. Kleinberg. Adaptive routing with end- to-end feedback: Distributed learning and geometric approaches. In Pro- ceedings of the Thirty-sixth Annual ACM Symposium on Theory of Com- puting, STOC ’04, pages 45–53, New York, NY, USA, 2004. ACM. ISBN 1-58113-852-0. doi: 10.1145/1007352.1007367. URL http://doi.acm.org/ 10.1145/100735...

arXiv 2004

[6] [5]

The ﬁnancing of innovation : learning and stopping

Dirk Bergemann and Ulrich Hege. The ﬁnancing of innovation : learning and stopping. The RAND Journal of Economics , 36, 02 2001

work page 2001

[7] [6]

Learning and strategic pricing

Dirk Bergemann and Juuso V¨ alim¨ aki. Learning and strategic pricing. Econometrica, 64(5):1125–49, 1996. URL https://EconPapers.repec. org/RePEc:ecm:emetrp:v:64:y:1996:i:5:p:1125-49

work page 1996

[8] [7]

Stochastic multi- armed-bandit problem with non-stationary rewards

Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi- armed-bandit problem with non-stationary rewards. In Advances in Neural Information Processing Systems 27 , pages 199–207. Cur- ran Associates, Inc., 2014. URL http://papers.nips.cc/paper/ 5378-stochastic-multi-armed-bandit-problem-with-non-stationary-rewards. pdf

work page 2014