Asymptotic randomised control with applications to bandits

Samuel N. Cohen; Tanut Treetanthiploet

doi:10.3934/naco.2026016

Article Contents

2026, Volume 19: 133-167. Doi: 10.3934/naco.2026016

This volume Previous Article Some notes concerning preconditioning of linear parabolic optimal control problems Next Article $ p $-hyperconvexity with application to nonlinear PDE

Asymptotic randomised control with applications to bandits

Samuel N. Cohen^1, , and
Tanut Treetanthiploet^{1, 2,}

1.
Mathematical Institute, University of Oxford, United Kingdom
2.
Infinitas by Krungthai, Bangkok, Thailand

^*Corresponding author: Samuel N. Cohen
^*Corresponding author: Samuel N. Cohen

Received: April 25, 2024

Revised: February 20, 2026

Early access: May 7, 2026

Published online: May 7, 2026

The first author acknowledges the support of the UKRI Prosperity Partnership Scheme (FAIR) under EPSRC grant EP/V056883/1,the Alan Turing Institute, and the Oxford-Man Institute for Quantitative Finance.

Abstract / Introduction Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

We consider a general multi-armed bandit problem with correlated (and simple contextual and restless) elements, as a relaxed control problem. By introducing an entropy premium, we obtain a smooth asymptotic approximation to the value function. This yields a novel semi-index approximation of the optimal decision process. This semi-index can be interpreted as explicitly balancing an exploration–exploitation trade-off as in the UCB (Upper Confidence Bound) principle where the learning premium explicitly describes asymmetry of information available in the environment and non-linearity in the reward function.

Performance of the resulting Asymptotic Randomised Control (ARC) algorithm compares favourably well with other approaches to correlated multi-armed bandits.

Keywords:

Mathematics Subject Classification: Primary: 60J20, 93E35, 90C40, 41A58.

Citation:

Full Text(HTML)

Figure 1. (a) $ \tilde{V}^\lambda \qquad \qquad $ (b) $ V^{\lambda, ARC}_\infty \qquad\qquad $ (c) $ (V^{\lambda, ARC}_\infty - \tilde{V}^\lambda)/\tilde{V}^\lambda $

Download: Full-size image PowerPoint slide

Figure 2. (a) $ \tilde{p}^{\lambda,*} \qquad\qquad $ (b) $ p^{\lambda, ARC}_\infty \qquad\qquad $ (c) $ p^{\lambda, ARC}_\infty - \tilde{p}^{\lambda,*} $

Download: Full-size image PowerPoint slide

Figure 3. Regret for the classical bandit

Download: Full-size image PowerPoint slide

Figure 4. Regret for the bandit with an informative arm

Download: Full-size image PowerPoint slide

Figure 5. Regret for the linear bandit

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	R. Agrawal, Sample mean based index policies by $O(\log N)$ regret for the multi-armed bandit problem, Advances in Applied Probability, 47 (2016), 1054-1078. doi: 10.2307/1427934.
[2]	P. Auer, N. Cesa-Bianchi and P. Fischer, Finite-time analysis of the multiarmed bandit problem, Machine Learning, 47 (2022), 235-256. doi: 10.1023/A:1013689704352.
[3]	M. Brezzi and T. Lai, Optimal learning and experimentation in bandit problems, Journal of Economic Dynamics and Control, 27 (2002), 87-108. doi: 10.1016/S0165-1889(01)00028-8.
[4]	G. Burtini, J. Loeppky and R. Lawrence, A survey of online experiment design with the stochastic multi-armed bandit, arXiv: 1510.00757v4.
[5]	N. Cesa-Bianchi, C. Gentile, G. Lugosi and G. Neu, Boltzmann exploration done right, in NIPS'17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 30 (2017).
[6]	V. Chernozhukov, D. Chetverikov and K. Kato, Comparison and anti-concentration bounds for maxima of Gaussian random vectors, Probability Theory and Related Fields, 162 (2015), 47-70. doi: 10.1007/s00440-014-0565-9.
[7]	S. N. Cohen, Data-driven nonlinear expectations for statistical uncertainty in decisions, Electronic Journal of Statistics, 11 (2017), 1858-1889. doi: 10.1214/17-EJS1278.
[8]	S. N. Cohen and T. Treetanthiploet, Gittins' theorem under uncertainty, Electronic Journal of Probability, 27 (2022), 1-48. doi: 10.1214/22-EJP742.
[9]	F. Coquet, Y. Hu, J. Mémin and S. Peng, Filtration consistent nonlinear expectations and related $g$-expectations, Probability Theory and Related Fields, 123 (2002), 1-27. doi: 10.1007/s004400100172.
[10]	E. Even-Dar, S. Mannor and Y. Mansour, Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems, Journal of Machine Learning Research, 7 (2006), 1079-1105.
[11]	S. Filippi, O. Cappé, A. Garivier and C. Szepesvári, Parametric bandits: the generalized linear case, in NIPS'10: Proceedings of the 23rd International Conference on Neural Information Processing Systems, 2010.
[12]	H. Föllmer and A. Schied, Stochastic Finance: An Introduction in Discrete Time, 4th edition, De Gruyter, 2016.
[13]	M. Frittelli and E. R. Gianin, Putting order in risk measures, Journal of Banking & Finance, 26 (2002), 1473-1486. doi: 10.1016/S0378-4266(02)00270-4.
[14]	J. C. Gittins and D. M. Jones, A dynamic allocation index for the sequential design of experiments, in Progress in Statistics (ed. J. Gani), Amsterdam: North Holland, (1974), 241-266.
[15]	E. Kaufmann, O. Cappé and A. Garivier, On Bayesian upper confidence bounds for bandit problems, in Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), La Palma, Canary Islands, (2012), 592-600.
[16]	J. M. Keynes, A Treatise on Probability, Macmillan and Co., 1921, Reprint BN Publishing, 2008.
[17]	J. Kirschner and A. Krause, Information directed sampling and bandits with heteroscedastic noise, in Proceedings of Machine Learning Research, (2018), 1-28. doi: 10.3929/ETHZ-B-000310984.
[18]	F. H. Knight, Risk, Uncertainty and Profit, Houghton Mifflin, 1921, Reprint Dover 2006.
[19]	T. Lattimore and C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2019.
[20]	C. Reisinger and Y. Zhang, Regularity and stability of feedback relaxed control, SIAM Journal on Control and Optimization, 59 (2021), 3118-3151. doi: 10.1137/20M1312435.
[21]	R. Rockafellar, Convex Analysis, Princeton University Press, 1972.
[22]	P. Rusmevichientong, A. Mersereau and J. N. Tsitsiklis, A structured multiarmed bandit problem and the greedy policy, in Proceedings of the IEEE Conference on Decision and Control, 2009.
[23]	D. Russo, A note on the equivalence of upper confidence bounds and gittins indices for patient agents, Operations Research, 69 (2021), 273-278. doi: 10.1287/opre.2020.198.
[24]	D. Russo and B. V. Roy, An information-theoretic analysis of Thompson sampling, Journal of Machine Learning Research, 17 (2016), Article No: 17.
[25]	D. Russo and B. V. Roy, Learning to optimize via information-directed sampling, Operations Research, 66 (2018), 230-252. doi: 10.1287/opre.2017.1663.
[26]	D. Russo, B. V. Roy, A. Kazerouni, I. Osband and Z. Wen, A tutorial on Thompson sampling, Foundations and Trends in Machine Learning, 11 (2018), 1-96. doi: 10.1561/2200000070.
[27]	I. O. Ryzhov, W. B. Powell and P. I. Frazier, The knowledge gradient algorithm for a general class of online learning problems, Operations Research, 60 (2012), 180-195. doi: 10.1287/opre.1110.0999.
[28]	S. P. Singh, T. Jaakkola, M. L. Littman and C. Szepesvári, Convergence results for single-stepon-policy reinforcement-learning algorithms, Machine Learning, 38 (2000), 287-308. doi: 10.1023/A:1007678930559.
[29]	D. Šiška and Ł. Szpruch, Gradient flows for regularized stochastic control problems, SIAM Journal on Control and Optimization, 62 (2024), 2036-2070. doi: 10.1137/20M1373645.
[30]	W. R. Thompson, On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika, 25 (1933), 285-294. doi: 10.1093/biomet/25.3-4.285.
[31]	J. Vermorel and M. Mohri, Multi-armed bandit algorithms and empirical evaluation, in European Conference on Machine Learning, (2005), 437-448. doi: 10.1007/11564096_42.
[32]	H. Wang, T. Zariphopoulou and X. Zhou, Reinforcement learning in continuous time and space: A stochastic control approach, Journal of Machine Learning Research, 21 (2020), Article No: 198, 1-34.
[33]	L. Zhou, A survey on contextual multi-armed bandits, arXiv: 1508.03326.