Efficient Opportunistic Approachability

Teodor Vanislavov Marinov, Mehryar Mohri, Princewill Okoroafor, Jon Schneider, Julian Zimmert
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-23, 2026.

Abstract

We study the problem of \emph{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. \cite{bernstein15a} 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 $O(T^{-1/d})$. In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of $O(T^{-1/3})$ that bypasses 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})$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-marinov26a, title = {Efficient Opportunistic Approachability}, author = {Marinov, Teodor Vanislavov and Mohri, Mehryar and Okoroafor, Princewill and Schneider, Jon and Zimmert, Julian}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--23}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/marinov26a/marinov26a.pdf}, url = {https://proceedings.mlr.press/v313/marinov26a.html}, abstract = {We study the problem of \emph{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. \cite{bernstein15a} 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 $O(T^{-1/d})$. In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of $O(T^{-1/3})$ that bypasses 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})$.} }
Endnote
%0 Conference Paper %T Efficient Opportunistic Approachability %A Teodor Vanislavov Marinov %A Mehryar Mohri %A Princewill Okoroafor %A Jon Schneider %A Julian Zimmert %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-marinov26a %I PMLR %P 1--23 %U https://proceedings.mlr.press/v313/marinov26a.html %V 313 %X We study the problem of \emph{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. \cite{bernstein15a} 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 $O(T^{-1/d})$. In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of $O(T^{-1/3})$ that bypasses 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})$.
APA
Marinov, T.V., Mohri, M., Okoroafor, P., Schneider, J. & Zimmert, J.. (2026). Efficient Opportunistic Approachability. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-23 Available from https://proceedings.mlr.press/v313/marinov26a.html.

Related Material