Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning

We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. A COLT open problem of Hu and Mehta asks to determine the optimal gap-dependent regret rate for stochastic decision-theoretic online learning under pure event-level differential privacy. For $K$ actions, losses in $[0,1]$, and a unique best action separated from the second-best action by gap ${\mathrm{\Delta }}_{\min }$, the known lower bound is of order $\frac{\log K}{\min \{{\mathrm{\Delta }}_{\min },\epsilon \}},$ or equivalently, up to universal constants, of order $$\frac{\log K}{{\mathrm{\Delta }}_{\min }}+\frac{\log K}{\epsilon }\mathrm{.}$$ We give a horizon-free pure-DP algorithm and prove the explicit regret bound $${\mathrm{Reg}}_T\le 1000\cdot (\frac{\log K}{{\mathrm{\Delta }}_{\min }}+\frac{\log K}{\epsilon })$$ for every horizon $T$. The numerical constant is not optimized. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data-independent random prefix of the previous block. The random prefix converts block regret into a sum, over all prefix lengths, of softmax selection errors. A single entropy-potential argument controls all privacy-dominated large-gap actions at cost $\log K\mathrm{/}\epsilon$.