新算法在噪声反馈下实现高效在线学习，无需预先知道参数。
Online learning with noisy side observations
- 用加权有向图建模动作间反馈关系，利用图结构提升学习效率。
- 理论证明在T轮后后悔值为$ ilde{O}(\ oot\of{α^* T})$，α*为新定义的图属性。
- 完全免调参，适用于带噪声反馈的多臂老虎机等场景。
我们提出一种新的部分可观测在线学习模型，其中学习者除了自身损失外，还能根据问题结构获得其他动作的噪声反馈。该结构通过加权有向图表示，边权重反映相邻节点间反馈质量。主要贡献是一种高效算法，保证在T轮后达到$ ilde{O}( oot\of{α^* T})$的后悔值，其中$α^*$是本文提出的有效独立数（effective independence number）。算法完全免参数，无需事先知晓或估计$α^*$。在边权为二值的特例下，本设置退化为Mannor和Shamir（2011）及Alon等人（2013）的模型，且算法恢复了近似最优的后悔界。
原文摘要 · Abstract (English)
We propose a new partial-observability model for online learning problems where the learner, besides its own loss, also observes some noisy feedback about the other actions, depending on the underlying structure of the problem. We represent this structure by a weighted directed graph, where the edge weights are related to the quality of the feedback shared by the connected nodes. Our main contribution is an efficient algorithm that guarantees a regret of $\widetilde{O}(\sqrt{α^* T})$ after $T$ rounds, where $α^*$ is a novel graph property that we call the effective independence number. Our algorithm is completely parameter-free and does not require knowledge (or even estimation) of $α^*$. For the special case of binary edge weights, our setting reduces to the partial-observability models of Mannor and Shamir (2011) and Alon et al. (2013) and our algorithm recovers the near-optimal regret bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。