在通信受限的多臂老虎机中,反馈无法降低最坏情况下的误差阶数。
Does Feedback Help in Bandits with Arm Erasures?
- 引入反馈机制让学习者明确知道实际执行的臂
- 证明了最坏误差下界为Ω(√KT + K/(1−ε))
- 虽不提升阶数,但简化算法设计并优化常数
我们研究分布式多臂老虎机问题在臂擦除信道下的情形,该问题源于多臂老虎机算法在通信受限网络中的广泛应用。在此设定中,学习者通过擦除概率为ε∈[0,1)的信道向代理发送要选择的臂;若发生擦除,代理将延续上一次成功接收的臂;学习者始终可观察到所执行臂的奖励。以往工作考虑无反馈场景,学习者无法判断执行的是请求臂还是上次成功接收的臂。本文则假设代理可向学习者发送反馈以确认请求是否被接收,从而使学习者确切知晓实际执行的臂。令人惊讶的是,我们证明了有反馈情形下的最坏情况后悔上界阶数与无反馈情形相同。具体而言,我们建立了Ω(√KT + K/(1−ε))的后悔下界,与无反馈的上界仅差对数因子。尽管如此,反馈仍能实现更简洁的算法设计,可能获得更优常数项的后悔界;我们设计了一种此类算法,并通过数值实验评估其性能。
原文摘要 · Abstract (English)
We study a distributed multi-armed bandit (MAB) problem over arm erasure channels, motivated by the increasing adoption of MAB algorithms over communication-constrained networks. In this setup, the learner communicates the chosen arm to play to an agent over an erasure channel with probability $ε\in [0,1)$; if an erasure occurs, the agent continues pulling the last successfully received arm; the learner always observes the reward of the arm pulled. In past work, we considered the case where the agent cannot convey feedback to the learner, and thus the learner does not know whether the arm played is the requested or the last successfully received one. In this paper, we instead consider the case where the agent can send feedback to the learner on whether the arm request was received, and thus the learner exactly knows which arm was played. Surprisingly, we prove that erasure feedback does not improve the worst-case regret upper bound order over the previously studied no-feedback setting. In particular, we prove a regret lower bound of $Ω(\sqrt{KT} + K / (1 - ε))$, where $K$ is the number of arms and $T$ the time horizon, that matches no-feedback upper bounds up to logarithmic factors. We note however that the availability of feedback enables simpler algorithm designs that may achieve better constants (albeit not better order) regret bounds; we design one such algorithm and evaluate its performance numerically.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。