Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization
Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization
复制标题
通过贝叶斯风险估计和最小化在线找到最佳探索-利用权衡
DOI：
10.1016/j.artint.2024.104096
复制
发表时间：
2024
影响因子：
14.4
通讯作者：
Girdhar, Yogesh
中科院分区：
文献类型：
--
作者：
Jamieson, Stewart;How, Jonathan P.;Girdhar, Yogesh
我们提出针对政策集的内生贝叶斯风险最小化（EBRM）作为跨各种设置的在线学习方法。许多现实世界的在线学习问题都具有复杂性，例如依赖于行动和信念的奖励、奖励的时间贴现以及行动和反馈的异质成本；我们发现现有的在线学习启发式方法无法利用大多数特定问题的信息，从而损害了其性能。我们引入了信念空间马尔可夫决策过程（BMDP）模型，可以捕获这些复杂性，并进一步将任意、认知和过程风险的概念应用于在线学习。这些风险函数分别描述了学习问题固有的风险、由于代理缺乏知识而导致的风险以及其策略的相对质量。我们演示了计算和最小化这些风险函数如何引导在线学习代理在任何随机在线学习问题中实现最佳探索-利用权衡，这构成了 EBRM 方法的基础。我们还展示了贝叶斯风险（随机在线学习问题中的最小化目标）如何分解为上述任意风险、认知风险和过程风险。在模拟实验中，EBRM 算法在各种经典在线学习问题上实现了最先进的性能，包括高斯和伯努利多臂老虎机、最佳臂识别、具有依赖于行动和信念的奖励的混合目标，以及动态定价、有限部分监控问题。据我们所知，它也是第一个计算高效的在线学习方法，可以提供算法贝叶斯风险的在线界限。最后，由于 EBRM 方法是由一组策略算法参数化的，因此它可以扩展以纳入在线学习算法的新发展，因此非常适合作为开发现实世界学习代理的基础。
We proposeendogenous Bayesian risk minimization(EBRM) over policy sets as an approach to online learning across a wide range of settings. Many real-world online learning problems have complexities such as action- and belief-dependent rewards, time-discounting of reward, and heterogeneous costs for actions and feedback; we find that existing online learning heuristics cannot leverage most problem-specific information, to the detriment of their performance. We introduce a belief-space Markov decision process (BMDP) model that can capture these complexities, and further apply the concepts ofaleatoric,epistemic, andprocessrisks to online learning. These risk functions describe the risk inherent to the learning problem, the risk due to the agent's lack of knowledge, and the relative quality of its policy, respectively. We demonstrate how computing and minimizing these risk functions guides the online learning agent towards the optimal exploration-exploitation trade-off in any stochastic online learning problem, constituting the basis of the EBRM approach. We also show how Bayes' risk, the minimization objective in stochastic online learning problems, can be decomposed into the aforementioned aleatoric, epistemic, and process risks.In simulation experiments, EBRM algorithms achieve state-of-the-art performance across various classical online learning problems, including Gaussian and Bernoulli multi-armed bandits, best-arm identification, mixed objectives with action- and belief-dependent rewards, and dynamic pricing, a finite partial monitoring problem. To our knowledge, it is also the first computationally efficient online learning approach that can provide online bounds on an algorithm's Bayes' risk. Finally, because the EBRM approach is parameterized by a set of policy algorithms, it can be extended to incorporate new developments in online learning algorithms, and is thus well-suited as the foundation for developing real-world learning agents.
登录
查看更多内容
影响因子：
1.7
作者：
Bartok, Gabor;Foster, Dean P.;Szepesvari, Csaba
通讯作者：
Szepesvari, Csaba
多臂老虎机问题中一期前瞻策略的鲁棒性
DOI：
--
发表时间：
2010
期刊：
International Conference on Conceptual Structures
影响因子：
--
作者：
I. Ryzhov;P. Frazier;Warrren B Powell
通讯作者：
Warrren B Powell
DOI：
10.1287/opre.1110.0999
发表时间：
2012
期刊：
Oper. Res.
影响因子：
--
作者：
I. Ryzhov;Warren B. Powell;Peter I. Frazier
通讯作者：
I. Ryzhov;Warren B. Powell;Peter I. Frazier
DOI：
10.1609/icaps.v29i1.3505
发表时间：
2019-01
期刊：
--
影响因子：
--
作者：
Apoorva Sharma;James Harrison;Matthew W. Tsao;M. Pavone
通讯作者：
Apoorva Sharma;James Harrison;Matthew W. Tsao;M. Pavone
寻求人类帮助来管理半自主移动操作中的计划失败风险
影响因子：
3.1
作者：
Sarah Al;N. Dhanaraj;J. Gregory;R. Joseph;Shantanu Thakar;Brual C. Shah;Jeremy A. Marvel;Satyandra K. Gupta
通讯作者：
Satyandra K. Gupta