Unverified

Finite-Time Instance-Dependent Optimality for Online Learning with Feedback Graphs

Let $\mathcal G$ be the family of undirected $K$ -vertex graphs with self-loops and let $\mathcal D=[0,1]^{K-1}$ be the family of positive gap vectors for instances with a unique best arm.

Problem 1.

Characterize the functions $d\colon\mathcal D\times\mathcal G\to\mathbb R$ for which the following holds: for every $G\in\mathcal G$ , $\Delta\in\mathcal D$ , and algorithm $\mathcal A$ , there is an instance with feedback graph $G$ and means consistent with $\Delta$ such that, for every $\alpha>0$ and $T\in\mathbb N$ ,

\frac{\operatorname{Reg}(T)}{c^*(\Delta,G)\log T+1/\Delta_{\min}} \geq \min\{d(\Delta,G),T^\alpha\}.

At the same time, seek algorithms satisfying $\operatorname{Reg}(T)=O(c^*(\Delta,G)\log T+d(\Delta,G)).$

Problem 2.

What is a necessary and sufficient condition on $G$ under which one can guarantee

d(\Delta,G)=O(c^*(\Delta,G)) \qquad\text{for every gap vector }\Delta?

Download

Abstract

Asymptotically optimal instance-dependent regret is known for stochastic online learning with fixed feedback graphs, but the finite-time component may dominate for exponentially many rounds in the number of actions. There are feedback graphs on which every algorithm fails to match the asymptotically optimal rate in finite time for a large class of instances. The open problems ask for a characterization of finite-time instance-dependent rates and for graph conditions under which the finite-time term is controlled by the asymptotic complexity.

Background and progress

Consider a fixed undirected feedback graph $G$ on $[K]$ , with a self-loop at every arm. Arm $i$ has a Gaussian reward of mean $\mu_i\in[0,1]$ and variance $1/2$ . There is a unique optimal arm $i^*$ , with $\mu^*=\max_i\mu_i$ , gaps $\Delta_i=\mu^*-\mu_i$ , and minimum positive gap $\Delta_{\min}$ . On round $t$ , selecting $i_t$ reveals rewards for $i_t$ and every neighbor of $i_t$ . The regret is

\operatorname{Reg}(T)=\mu^*T-\mathbb E\!\left[\sum_{t=1}^T r_{t,i_t}\right].

The asymptotic lower-bound coefficient is the linear-program value

c^*(\Delta,G)=\min_{x\in\mathbb R_+^K}\langle x,\Delta\rangle \quad\text{subject to}\quad \sum_{j\in N_i}x_j\geq\frac1{\Delta_i^2} \quad(i\neq i^*).

Every algorithm satisfies $\lim_{T\to\infty}\operatorname{Reg}(T)/\log T\geq c^*(\Delta,G)$ . Known asymptotically tight algorithms can nevertheless have a finite component of order $\Omega(K/\Delta_{\min}^2)$ , dominating $O(\log T/\Delta_{\min})$ for reasonable horizons. Marinov, Mohri, and Zimmert exhibit graph families for which this separation is unavoidable and give preliminary min--max characterizations, but not a purely instance-dependent quantity [Marinov et al., 2022]. The open problems are posed directly in [Marinov et al., 2022].

Reference papers

Open Problem: Finite-Time Instance Dependent Optimality for Stochastic Online Learning with Feedback GraphsTeodor Vanislavov Marinov, Mehryar Mohri, Julian ZimmertProceedings of Thirty Fifth Conference on Learning Theory · 2022 ↗
Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic OptimalityTeodor V. Marinov, Mehryar Mohri, Julian ZimmertarXiv preprint · 2022

Finite-Time Instance-Dependent Optimality for Online Learning with Feedback Graphs

Problem 1.

Problem 2.

Coming soon

Organizer