在近似算法约束下，仍可高效实现向量博弈的可达目标。
Blackwell's Approachability with Approximation Algorithms
- 用近似算法处理难优化的行动集，保持可达性。
- 目标集经缩放后，可被以最优速率逼近。
- 适合研究在线学习与近似优化交叉问题者。
我们重新审视了著名的黑威尔可达性问题，该问题涉及玩家与对手之间的重复向量值博弈。当玩家或对手（或两者）的行动集难以优化时（例如对应于某个NP难优化问题的所有可能解集），我们探讨玩家在仅能通过近似算法访问这些集合的情况下，能够高效保证什么。假设玩家具有单调偏好，即若损失向量ℓ₂ ≤ ℓ₁，玩家不偏好ℓ₁胜过ℓ₂，我们证明：对于具有可达目标集S的黑威尔实例，经适当缩放后的集合αₘᵡαₘᵧ⁻¹S的向下闭包是可高效逼近的，且达到最优速率。当仅玩家或对手的集合配备近似算法时，我们给出更简单、更高效的算法。
原文摘要 · Abstract (English)
We revisit Blackwell's celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee \textit{efficiently}, when only having access to these sets via approximation algorithms with ratios $α_{\mX} \geq 1$ and $ 1 \geq α_{\mY} > 0$, respectively. Assuming the player has monotone preferences, in the sense that he does not prefer a vector-valued loss $\ell_1$ over $\ell_2$ if $\ell_2 \leq \ell_1$, we establish that given a Blackwell instance with an approachable target set $S$, the downward closure of the appropriately-scaled set $α_{\mX}α_{\mY}^{-1}S$ is \textit{efficiently} approachable with optimal rate. In case only the player's or adversary's set is equipped with an approximation algorithm, we give simpler and more efficient algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。