提出高效算法实现更快的对手可逼近性，无需复杂校准。
Efficient Opportunistic Approachability
- 设计新算法避免在线校准，提升计算效率
- 实现 $O(T^{-1/4})$ 的逼近速率，优于旧方法
- 二维情况下可达最优 $O(T^{-1/2})$，适合高维场景
我们研究机会性可逼近性问题：这是黑威尔可逼近性的推广，其中学习者希望在对手限制自身行动空间时获得更强的保证（即逼近更小的目标集）。伯恩斯坦等人（2014）首次提出该问题，并给出一种保证次线性逼近率的算法。然而该算法需生成对手行为的校准在线预测，其标准实现时间复杂度随环境维度指数增长，导致逼近率仅为 $T^{-O(1/d)}$。本文提出一种高效算法，实现 $O(T^{-1/4})$ 的逼近率（另有一低效算法达 $O(T^{-1/3})$），无需在线校准子程序。此外，当对手行动集维度不超过2时，可实现最优 $O(T^{-1/2})$ 的逼近率。
原文摘要 · Abstract (English)
We study the problem of opportunistic approachability: a generalization of Blackwell approachability where the learner would like to obtain stronger guarantees (i.e., approach a smaller set) when their adversary limits themselves to a subset of their possible action space. Bernstein et al. (2014) introduced this problem in 2014 and presented an algorithm that guarantees sublinear approachability rates for opportunistic approachability. However, this algorithm requires the ability to produce calibrated online predictions of the adversary's actions, a problem whose standard implementations require time exponential in the ambient dimension and result in approachability rates that scale as $T^{-O(1/d)}$. In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of $O(T^{-1/4})$ (and an inefficient one that achieves a rate of $O(T^{-1/3})$), bypassing the need for an online calibration subroutine. Moreover, in the case where the dimension of the adversary's action set is at most two, we show it is possible to obtain the optimal rate of $O(T^{-1/2})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。