在随机观测损失的老虎机问题中，提出两种算法实现近最优后悔界。
Online learning with Erdős-Rényi side-observation graphs
- 基于独立随机观测机制设计自适应算法
- 当观测概率r≥logT/(2N)时，后悔上界为O(√(T/r logN))
- 适用于观测概率未知且低的情况，适合在线学习研究者
我们研究对抗性多臂老虎机问题，其中学习者在选择一个动作后，可随机观测未选中动作的损失。所有非选中臂以固定但未知的概率 $r$ 独立揭示其损失。针对不同 $r$ 范围，提出两种算法：第一种在 $r \geq \log T / (2N)$ 时，$T$ 轮内期望后悔为 $O(\sqrt{(T / r) \log N})$；第二种在更小 $r$ 下，达到 $O(\sqrt{(T / r) \log (N + T)})$。还提供快速估计 $r$ 范围的方法。所有界均与已知 $r$ 的最优算法仅差对数因子。
原文摘要 · Abstract (English)
We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with a fixed but unknown probability $r$, independently of each other and the action of the learner. We propose two algorithms that work for different ranges of $r$. We show that after $T$ rounds in a bandit problem with $N$ arms, the expected regret of our first algorithm is $O(\sqrt{(T /r) \log N })$ whenever $r\ge(\log T)/(2N)$, while our second algorithm achieves a regret of $O(\sqrt{(T/r) \log (N+T)})$ for smaller values of $r$. We also give a quick estimation procedure that decides the range of~$r$. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know~$r$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。