提出新型非随机线性部分监控的后悔界，能自适应难易程度。
Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
- 用优化驱动探索法，简化实现且可分析。
- 简单游戏达√T后悔率，复杂游戏达T²⁄³，与结构相关。
- 适用于多种信息受限场景，理论界限可紧致。
与经典部分监控不同，线性部分监控可建模无限结果空间，并在损失与观测上施加线性结构。该设定可视为线性老虎机的推广，其中损失与反馈以灵活方式解耦。本文针对非随机（对抗性）且有限动作的情形，采用一种简洁的探索-优化方法，实现高效计算。我们推导出依赖于博弈结构的后悔界，相比以往理论结果更清晰透明。这些边界引入了反映观测与损失对齐程度的实例特定量，类似于随机设定中的已知保证。值得注意的是，其在简单（局部可观测）游戏中达到标准√T后悔率，在困难（全局可观测）游戏中达到T²⁄³。我们在若干旧有及新设的部分信息场景中实例化这些边界，证明所获结构依赖关系在有趣情况下可达到紧致性。
原文摘要 · Abstract (English)
In contrast to the classic formulation of partial monitoring, linear partial monitoring can model infinite outcome spaces, while imposing a linear structure on both the losses and the observations. This setting can be viewed as a generalization of linear bandits where loss and feedback are decoupled in a flexible manner. In this work, we address a nonstochastic (adversarial), finite-actions version of the problem through a simple instance of the exploration-by-optimization method that is amenable to efficient implementation. We derive regret bounds that depend on the game structure in a more transparent manner than previous theoretical guarantees for this paradigm. Our bounds feature instance-specific quantities that reflect the degree of alignment between observations and losses, and resemble known guarantees in the stochastic setting. Notably, they achieve the standard $\sqrt{T}$ rate in easy (locally observable) games and $T^{2/3}$ in hard (globally observable) games, where $T$ is the time horizon. We instantiate these bounds in a selection of old and new partial information settings subsumed by this model, and illustrate that the achieved dependence on the game structure can be tight in interesting cases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。