揭示奖励方差如何影响上下文赌博机的遗憾，关键在于函数类复杂度。
How Does Variance Shape the Regret in Contextual Bandits?
- 引入方差依赖的遗憾分析，强调埃尔德维维度的关键作用。
- 弱对手下，遗憾下界为Ω(√(min{A,d_elu}Λ)+d_elu)，上界近似匹配。
- 强对手下，方差与分布信息可进一步降低遗憾，适合理论研究者。
我们研究可实现的上下文赌博机与通用函数逼近，探讨小奖励方差如何带来优于极小极大遗憾界的性能。不同于极小极大界，我们发现函数类的埃尔德维维度 $d_{\text{elu}}$ 在方差依赖的界限中起关键作用。考虑两种对抗者：(1) 弱对抗者：在观察学习者动作前设定奖励方差。在此设定下，当 $d_{\text{elu}}\leq\sqrt{AT}$ 时，遗憾下界为 $Ω(\sqrt{\min\{A,d_{\text{elu}}\}Λ}+d_{\text{elu}})$，其中 $A$ 为动作数，$T$ 为总轮数，$Λ$ 为 $T$ 轮内总方差。对于 $A\leq d_{\text{elu}}$ 的情形，当方差在每轮开始时已知时，我们给出几乎匹配的上界 $\tilde{O}(\sqrt{AΛ}+d_{\text{elu}})$。(2) 强对抗者：在观察学习者动作后设定奖励方差。我们证明当 $\sqrt{d_{\text{elu}}Λ}+d_{\text{elu}}\leq\sqrt{AT}$ 时，遗憾下界为 $Ω(\sqrt{d_{\text{elu}}Λ}+d_{\text{elu}})$，并提供上界 $\tilde{O}(d_{\text{elu}}\sqrt{Λ}+d_{\text{elu}})$。此外，我们考察了王等人（2024）研究的带分布信息的函数类，证明其 $\tilde{O}(\sqrt{d_{\text{elu}}Λ}+d_{\text{elu}})$ 的遗憾界不可改进。但若采用不同的总方差定义并假设奖励服从高斯分布，可达到 $\tilde{O}(\sqrt{AΛ}+d_{\text{elu}})$。
原文摘要 · Abstract (English)
We consider realizable contextual bandits with general function approximation, investigating how small reward variance can lead to better-than-minimax regret bounds. Unlike in minimax bounds, we show that the eluder dimension $d_\text{elu}$$-$a complexity measure of the function class$-$plays a crucial role in variance-dependent bounds. We consider two types of adversary: (1) Weak adversary: The adversary sets the reward variance before observing the learner's action. In this setting, we prove that a regret of $Ω(\sqrt{\min\{A,d_\text{elu}\}Λ}+d_\text{elu})$ is unavoidable when $d_{\text{elu}}\leq\sqrt{AT}$, where $A$ is the number of actions, $T$ is the total number of rounds, and $Λ$ is the total variance over $T$ rounds. For the $A\leq d_\text{elu}$ regime, we derive a nearly matching upper bound $\tilde{O}(\sqrt{AΛ}+d_\text{elu})$ for the special case where the variance is revealed at the beginning of each round. (2) Strong adversary: The adversary sets the reward variance after observing the learner's action. We show that a regret of $Ω(\sqrt{d_\text{elu}Λ}+d_\text{elu})$ is unavoidable when $\sqrt{d_\text{elu}Λ}+d_\text{elu}\leq\sqrt{AT}$. In this setting, we provide an upper bound of order $\tilde{O}(d_\text{elu}\sqrtΛ+d_\text{elu})$. Furthermore, we examine the setting where the function class additionally provides distributional information of the reward, as studied by Wang et al. (2024). We demonstrate that the regret bound $\tilde{O}(\sqrt{d_\text{elu}Λ}+d_\text{elu})$ established in their work is unimprovable when $\sqrt{d_{\text{elu}}Λ}+d_\text{elu}\leq\sqrt{AT}$. However, with a slightly different definition of the total variance and with the assumption that the reward follows a Gaussian distribution, one can achieve a regret of $\tilde{O}(\sqrt{AΛ}+d_\text{elu})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。