Scholarlink

<p>The multi-armed bandit (MAB) problems are widely studied in fields of operations research, stochastic optimization, and reinforcement learning. In this paper, we consider the classical MAB model with heavy-tailed reward distributions and introduce the extended robust UCB policy, which is an extension of the results of Bubeck et al. (IEEE Trans Inf Theory 59:7711–7717, 2013) and Lattimore (Adv Neural Inf Process Syst, 30:1–10, 2017)that are further based on the pioneering idea of UCB policies e.g. (Auer et al. in Mach Learn, 47:235–256, 2002). The previous UCB policies require some strict conditions on reward distributions, which can be difficult to guarantee in practical scenarios. Our extended robust UCB generalizes Lattimore’s seminary work (for moments of orders <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(p=4\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(q=2\)</EquationSource> </InlineEquation>) to arbitrarily chosen <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(p&gt;q&gt;1\)</EquationSource> </InlineEquation> as long as the two moments have a known controlled relationship, while still achieving the optimal regret growth order <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(O(\log T)\)</EquationSource> </InlineEquation>, thus providing a broadened application area of UCB policies for heavy-tailed reward distributions. Furthermore, we achieve a near-optimal regret order without any knowledge of the reward distributions as long as their <i>p</i>-th moments exist for some&#xa0;<InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(p&gt;1\)</EquationSource> </InlineEquation>. Finally, we briefly present our earlier work on light-tailed reward distributions for a complete illustration of the amazing simplicity and power of UCB policies.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Extended UCB Policies for Multi-armed Bandit Problems

  • 期刊论文

  • 发表日期：

    2025年12月25日

查看全文
  • Keqin Liu,
  • Tianshuo Zheng,
  • Zhi-Hua Zhou

摘要

The multi-armed bandit (MAB) problems are widely studied in fields of operations research, stochastic optimization, and reinforcement learning. In this paper, we consider the classical MAB model with heavy-tailed reward distributions and introduce the extended robust UCB policy, which is an extension of the results of Bubeck et al. (IEEE Trans Inf Theory 59:7711–7717, 2013) and Lattimore (Adv Neural Inf Process Syst, 30:1–10, 2017)that are further based on the pioneering idea of UCB policies e.g. (Auer et al. in Mach Learn, 47:235–256, 2002). The previous UCB policies require some strict conditions on reward distributions, which can be difficult to guarantee in practical scenarios. Our extended robust UCB generalizes Lattimore’s seminary work (for moments of orders \(p=4\) and \(q=2\) ) to arbitrarily chosen \(p>q>1\) as long as the two moments have a known controlled relationship, while still achieving the optimal regret growth order \(O(\log T)\) , thus providing a broadened application area of UCB policies for heavy-tailed reward distributions. Furthermore, we achieve a near-optimal regret order without any knowledge of the reward distributions as long as their p-th moments exist for some  \(p>1\) . Finally, we briefly present our earlier work on light-tailed reward distributions for a complete illustration of the amazing simplicity and power of UCB policies.