在反馈受限的动态环境中，首次实现无需先验知识的近优自适应学习。
Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits
- 设计无先验知识的算法，自动应对奖励分布变化
- 在有限反馈下实现近最优动态遗憾，理论性能达$ ilde{/mathcal{O}}(K^{1/3} V_T^{1/3} T / B^{1/3})$
- 适合反馈资源受限的实时决策场景，如在线广告与推荐系统
非平稳多臂赌博机通过检测和响应奖励分布变化来适应动态环境，但现有方法通常假设每轮都能获得奖励反馈，忽略了现实世界中反馈受限的情况。本文提出一种新的受限反馈模型，首次设计出无需先验知识（即不依赖非平稳程度）的算法，在该设定下实现了近似最优的动态遗憾。具体而言，算法达到动态遗憾 $ ilde{/mathcal{O}}(K^{1/3} V_T^{1/3} T / B^{1/3})$，其中 $T$ 为轮数，$K$ 为臂的数量，$B$ 为查询预算，$V_T$ 为刻画非平稳性的变差预算。
原文摘要 · Abstract (English)
Non-stationary multi-armed bandits enable agents to adapt to changing environments by incorporating mechanisms to detect and respond to shifts in reward distributions, making them well-suited for dynamic settings. However, existing approaches typically assume that reward feedback is available at every round - an assumption that overlooks many real-world scenarios where feedback is limited. In this paper, we take a significant step forward by introducing a new model of constrained feedback in non-stationary multi-armed bandits, where the availability of reward feedback is restricted. We propose the first prior-free algorithm - that is, one that does not require prior knowledge of the degree of non-stationarity - that achieves near-optimal dynamic regret in this setting. Specifically, our algorithm attains a dynamic regret of $\tilde{\mathcal{O}}({K^{1/3} V_T^{1/3} T }/{ B^{1/3}})$, where $T$ is the number of rounds, $K$ is the number of arms, $B$ is the query budget, and $V_T$ is the variation budget capturing the degree of non-stationarity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。