Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differential Privacy

There are $K$ actions. On each round $t\leq T$, losses $\ell_{j,t}\in[0,1]$ are drawn independently from an unknown distribution $P_j$ for every action $j$, the learner selects $I_t$, incurs $\ell_{I_t,t}$, and observes all losses. Let $\mu_1<\mu_2\leq\cdots\leq\mu_K$ be the mean losses, $\Delta_j=\mu_j-\mu_1$, and $\Delta_{\min}=\Delta_2$. The entire decision transcript must be pure $\varepsilon$-differentially private with respect to changing one loss vector.

Determine matching, problem-dependent upper and lower bounds for

$$\mathbb E\sum_{t=1}^T\ell_{I_t,t}-\min_{j\in[K]}\mathbb E\sum_{t=1}^T\ell_{j,t}$$

as a function of the gaps, $K$, $T$, and $\varepsilon$. In particular, close the gap between the known bounds, either by tightening the analysis or designing an algorithm, and determine whether balancing mistakes across insufficiently sampled actions yields the optimal rate.