{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T15:49:31Z","timestamp":1775663371056,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>We develop a general theory to optimize the frequentist regret for sequential learning problems, from which efficient bandit and reinforcement learning algorithms can be derived via unified Bayesian principles. Building on the recent Decision-Estimation Coefficient (DEC) framework, we propose a novel optimization approach to generate \u201calgorithmic beliefs\u201d at each round and use Bayesian posteriors for decision-making. The optimization objective, termed \u201cAlgorithmic Information Ratio\u201d (AIR), represents an intrinsic complexity measure that effectively characterizes the frequentist regret of any algorithm. Although AIR\u2019s minimax regret aligns with that provided by DEC, it additionally offers an algorithm-dependent perspective\u2013distinct from a minimax complexity\u2013facilitating algorithm design and analysis. Specifically, AIR enables deriving explicit algorithms via belief parameterization and provides clear approximation guidelines with provable guarantees. Moreover, the resulting algorithms have a simple structure and are computationally efficient for several representative problems. We illustrate our framework with a novel algorithm for multi-armed bandits that performs strongly across stochastic, adversarial, and non-stationary environments, and demonstrate applicability to linear bandits, convex bandits, and reinforcement learning.<\/jats:p>","DOI":"10.1145\/3766898","type":"journal-article","created":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T11:41:01Z","timestamp":1757590861000},"page":"1-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Bayesian Design Principles for Frequentist Sequential Learning"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4530-764X","authenticated-orcid":false,"given":"Yunbei","family":"Xu","sequence":"first","affiliation":[{"name":"Department of Industrial Systems Engineering & Management, National University of Singapore","place":["Singapore, Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1075-6664","authenticated-orcid":false,"given":"Assaf","family":"Zeevi","sequence":"additional","affiliation":[{"name":"Graduate School of Business, Columbia University","place":["New York, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_4_2_2","volume-title":"Proceedings of the 21st Annual Conference on Learning Theory, COLT 2008","author":"Abernethy Jacob","year":"2008","unstructured":"Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. 2008. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory, COLT 2008."},{"key":"e_1_3_4_3_2","first-page":"1638","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Agarwal Alekh","year":"2014","unstructured":"Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. 2014. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the International Conference on Machine Learning. 1638\u20131646."},{"key":"e_1_3_4_4_2","first-page":"35284","article-title":"Model-based RL with optimistic posterior sampling: Structural conditions and sample complexity","volume":"35","author":"Agarwal Alekh","year":"2022","unstructured":"Alekh Agarwal and Tong Zhang. 2022. Model-based RL with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems 35, Article No.: 2557 (2022), 35284\u201335297.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_5_2","volume-title":"Proceedings of the Conference on Learning Theory","author":"Agrawal Shipra","year":"2012","unstructured":"Shipra Agrawal and Navin Goyal. 2012. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 39\u20131."},{"key":"e_1_3_4_6_2","first-page":"127","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Agrawal Shipra","year":"2013","unstructured":"Shipra Agrawal and Navin Goyal. 2013. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the International Conference on Machine Learning. PMLR, 127\u2013135."},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0362-546X(94)00186-L"},{"key":"e_1_3_4_10_2","volume-title":"Nonlinear Programming","author":"Bertsekas Dimitri P.","year":"1999","unstructured":"Dimitri P. Bertsekas. 1999. Nonlinear Programming. Athena Scientific, Belmont, MA."},{"key":"e_1_3_4_11_2","article-title":"Stochastic multi-armed-bandit problem with non-stationary rewards","volume":"27","author":"Besbes Omar","year":"2014","unstructured":"Omar Besbes, Yonatan Gur, and Assaf Zeevi. 2014. Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in Neural Information Processing Systems 1, 27 (2014), 199\u2013207.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-34514-5"},{"key":"e_1_3_4_13_2","first-page":"583","volume-title":"Proceedings of the Conference on Learning Theory","author":"Bubeck S\u00e9bastien","year":"2016","unstructured":"S\u00e9bastien Bubeck and Ronen Eldan. 2016. Multi-scale exploration of convex functions and bandit convex optimization. In Proceedings of the Conference on Learning Theory. PMLR, 583\u2013589."},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055403"},{"key":"e_1_3_4_15_2","volume-title":"Proceedings of the Conference on Learning Theory","author":"Bubeck S\u00e9bastien","year":"2012","unstructured":"S\u00e9bastien Bubeck and Aleksandrs Slivkins. 2012. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 42\u20131."},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","unstructured":"Fan Chen Song Mei and Yu Bai. 2025. Unified algorithms for RL with decision-estimation coefficients: PAC reward-free preference-based learning and beyond. The Annals of Statistics 53 1 (2025) 426\u2013456.","DOI":"10.1214\/24-AOS2483"},{"key":"e_1_3_4_17_2","article-title":"The price of bandit information for online optimization","volume":"20","author":"Dani Varsha","year":"2007","unstructured":"Varsha Dani, Sham M. Kakade, and Thomas Hayes. 2007. The price of bandit information for online optimization. Advances in Neural Information Processing Systems 20 (2007), 345\u2013352.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-019-09426-y"},{"key":"e_1_3_4_19_2","first-page":"2826","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Du Simon","year":"2021","unstructured":"Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. 2021. Bilinear classes: A structural framework for provable generalization in RL. In Proceedings of the International Conference on Machine Learning. PMLR, 2826\u20132836."},{"key":"e_1_3_4_20_2","first-page":"3199","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Foster Dylan","year":"2020","unstructured":"Dylan Foster and Alexander Rakhlin. 2020. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the International Conference on Machine Learning. PMLR, 3199\u20133210."},{"key":"e_1_3_4_21_2","article-title":"Adapting to misspecification in contextual bandits","volume":"33","author":"Foster Dylan J.","year":"2020","unstructured":"Dylan J. Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. 2020. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems 33, Article No.: 963 (2020), 11478\u201311489.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_22_2","unstructured":"Dylan J. Foster Noah Golowich and Yanjun Han. 2023. Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory. PMLR 3969\u20134043."},{"key":"e_1_3_4_23_2","unstructured":"Dylan J. Foster Noah Golowich Jian Qian Alexander Rakhlin and Ayush Sekhari. 2023. Model-free reinforcement learning with the decision-estimation coefficient. Advances in Neural Information Processing Systems 36 881 (2023) 20080\u201320117."},{"key":"e_1_3_4_24_2","unstructured":"Dylan J. Foster Sham M. Kakade Jian Qian and Alexander Rakhlin. 2021. The statistical complexity of interactive decision making. arXiv:2112.13487. Retrieved from https:\/\/arxiv.org\/abs\/2112.13487"},{"key":"e_1_3_4_25_2","first-page":"35404","article-title":"On the complexity of adversarial decision making","volume":"35","author":"Foster Dylan J.","year":"2022","unstructured":"Dylan J. Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. 2022. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems 35, Article No.: 2566 (2022), 35404\u201335417.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_26_2","volume-title":"Empirical Processes in M-estimation","author":"Geer Sara A.","year":"2000","unstructured":"Sara A. Geer. 2000. Empirical Processes in M-estimation. Vol. 6. Cambridge University Press."},{"key":"e_1_3_4_27_2","first-page":"28575","article-title":"Regret bounds for information-directed reinforcement learning","volume":"35","author":"Hao Botao","year":"2022","unstructured":"Botao Hao and Tor Lattimore. 2022. Regret bounds for information-directed reinforcement learning. Advances in Neural Information Processing Systems 35, Article No.: 2071 (2022), 28575\u201328587.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3007072"},{"key":"e_1_3_4_29_2","first-page":"1704","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Jiang Nan","year":"2017","unstructured":"Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. 2017. Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the International Conference on Machine Learning. 1704\u20131713."},{"key":"e_1_3_4_30_2","article-title":"Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms","volume":"34","author":"Jin Chi","year":"2021","unstructured":"Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. 2021. Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems 34, Article No.: 1027 (2021), 13406\u201313418.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_31_2","first-page":"2137","volume-title":"Proceedings of the Conference on Learning Theory","author":"Jin Chi","year":"2020","unstructured":"Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. 2020. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the Conference on Learning Theory. PMLR, 2137\u20132143."},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.4171\/msl\/17"},{"key":"e_1_3_4_34_2","first-page":"2965","volume-title":"Proceedings of the Conference on Learning Theory","author":"Lattimore Tor","year":"2021","unstructured":"Tor Lattimore and Andras Gyorgy. 2021. Mirror descent and the information ratio. In Proceedings of the Conference on Learning Theory. PMLR, 2965\u20132992."},{"key":"e_1_3_4_35_2","first-page":"2111","volume-title":"Proceedings of the Conference on Learning Theory","author":"Lattimore Tor","year":"2019","unstructured":"Tor Lattimore and Csaba Szepesv\u00e1ri. 2019. An information-theoretic approach to minimax regret in partial monitoring. In Proceedings of the Conference on Learning Theory. PMLR, 2111\u20132139."},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_3_4_37_2","first-page":"2488","volume-title":"Proceedings of the Conference on Learning Theory","author":"Lattimore Tor","year":"2020","unstructured":"Tor Lattimore and Csaba Szepesv\u00e1ri. 2020. Exploration by optimisation in partial monitoring. In Proceedings of the Conference on Learning Theory. PMLR, 2488\u20132515."},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772758"},{"key":"e_1_3_4_39_2","unstructured":"Haolin Liu Chen-Yu Wei and Julian Zimmert. 2025. Decision making in hybrid environments: A model aggregation approach. arXiv:2502.05974. Retrieved from https:\/\/arxiv.org\/abs\/2502.05974"},{"key":"e_1_3_4_40_2","first-page":"17956","article-title":"The pareto frontier of model selection for general contextual bandits","volume":"34","author":"Marinov Teodor Vanislavov","year":"2021","unstructured":"Teodor Vanislavov Marinov and Julian Zimmert. 2021. The pareto frontier of model selection for general contextual bandits. Advances in Neural Information Processing Systems 34, Article No.: 1374 (2021), 17956\u201317967.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature14236"},{"key":"e_1_3_4_42_2","doi-asserted-by":"crossref","unstructured":"Yury Polyanskiy and Yihong Wu. 2025. Information theory: From coding to learning. Cambridge university press.","DOI":"10.1017\/9781108966351"},{"key":"e_1_3_4_43_2","volume-title":"Convex Analysis","author":"Rockafellar Ralph Tyrell","year":"2015","unstructured":"Ralph Tyrell Rockafellar. 2015. Convex Analysis. Princeton University Press."},{"key":"e_1_3_4_44_2","first-page":"2256","volume-title":"Proceedings of the International Conference on Neural Information Processing Systems","author":"Russo Daniel","year":"2013","unstructured":"Daniel Russo and Benjamin Van Roy. 2013. Eluder dimension and the sample complexity of optimistic exploration. In Proceedings of the International Conference on Neural Information Processing Systems. 2256\u20132264."},{"key":"e_1_3_4_45_2","article-title":"Learning to optimize via information-directed sampling","volume":"27","author":"Russo Daniel","year":"2014","unstructured":"Daniel Russo and Benjamin Van Roy. 2014. Learning to optimize via information-directed sampling. Advances in Neural Information Processing Systems 1, 27 (2014), 1583\u20131591.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3007021"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature16961"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1193"},{"issue":"1","key":"e_1_3_4_49_2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.2140\/pjm.1958.8.171","article-title":"On general minimax theorems.","volume":"8","author":"Sion Maurice","year":"1958","unstructured":"Maurice Sion. 1958. On general minimax theorems. Pacific Journal of Mathematics 8, 1 (1958), 171\u2013176.","journal-title":"Pacific Journal of Mathematics"},{"key":"e_1_3_4_50_2","article-title":"Proving that the conditional entropy of a probability measure is concave","volume":"1","author":"Song Myunghyun","year":"2019","unstructured":"Myunghyun Song. 2019. Proving that the conditional entropy of a probability measure is concave. Mathematics Stack Exchange. Retrieved September 1, 2025 from https:\/\/math.stackexchange.com\/q\/3080334","journal-title":"Mathematics Stack Exchange."},{"key":"e_1_3_4_51_2","first-page":"2898","volume-title":"Proceedings of the Conference on Learning Theory","author":"Sun Wen","year":"2019","unstructured":"Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. 2019. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Proceedings of the Conference on Learning Theory. PMLR, 2898\u20132933."},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/25.3-4.285"},{"key":"e_1_3_4_53_2","first-page":"1322","volume-title":"Proceedings of the 36th Annual Conference on Learning Theory","author":"Wagenmaker Andrew J.","year":"2023","unstructured":"Andrew J. Wagenmaker and Dylan J. Foster. 2023. Instance-optimality in interactive decision making: Toward a non-asymptotic theory. In Proceedings of the 36th Annual Conference on Learning Theory. PMLR, 1322\u20131472."},{"key":"e_1_3_4_54_2","first-page":"6123","article-title":"Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension","volume":"33","author":"Wang Ruosong","year":"2020","unstructured":"Ruosong Wang, Russ R. Salakhutdinov, and Lin Yang. 2020. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 33, Article No.: 514 (2020), 6123\u20136135.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_4_55_2","first-page":"1263","volume-title":"Proceedings of the Conference on Learning Theory","author":"Wei Chen-Yu","year":"2018","unstructured":"Chen-Yu Wei and Haipeng Luo. 2018. More adaptive algorithms for adversarial bandits. In Proceedings of the Conference on Learning Theory. PMLR, 1263\u20131291."},{"key":"e_1_3_4_56_2","first-page":"4300","volume-title":"Proceedings of the Conference on Learning Theory","author":"Wei Chen-Yu","year":"2021","unstructured":"Chen-Yu Wei and Haipeng Luo. 2021. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Proceedings of the Conference on Learning Theory. PMLR, 4300\u20134354."},{"key":"e_1_3_4_57_2","doi-asserted-by":"crossref","unstructured":"Yunbei Xu and Assaf Zeevi. 2025. Towards optimal problem dependent generalization error bounds in statistical learning theory. Mathematics of Operations Research 50 1 (2025) 40\u201367.","DOI":"10.1287\/moor.2021.0076"},{"key":"e_1_3_4_58_2","unstructured":"Yunbei Xu and Assaf Zeevi. 2020. Upper counterfactual confidence bounds: A new optimism principle for contextual bandits. arXiv:2007.07876. Retrieved from https:\/\/arxiv.org\/abs\/2007.07876"},{"key":"e_1_3_4_59_2","first-page":"6995","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Yang Lin","year":"2019","unstructured":"Lin Yang and Mengdi Wang. 2019. Sample-optimal parametric Q-learning using linearly additive features. In Proceedings of the International Conference on Machine Learning. PMLR, 6995\u20137004."},{"issue":"5","key":"e_1_3_4_60_2","first-page":"2180","article-title":"From  \\(\\varepsilon\\) -entropy to KL-entropy: Analysis of minimum information complexity density estimation","volume":"34","author":"Zhang Tong","year":"2006","unstructured":"Tong Zhang. 2006. From \\(\\varepsilon\\) -entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics 34, 5 (2006), 2180\u20132210.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1137\/21M140924X"},{"key":"e_1_3_4_62_2","first-page":"27428","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Zhu Yinglun","year":"2022","unstructured":"Yinglun Zhu, Dylan J. Foster, John Langford, and Paul Mineiro. 2022. Contextual bandits with large action spaces: Made practical. In Proceedings of the International Conference on Machine Learning. PMLR, 27428\u201327453."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3766898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:38:02Z","timestamp":1760017082000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3766898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":61,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3766898"],"URL":"https:\/\/doi.org\/10.1145\/3766898","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2024-02-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}