Online Policy Learning via a Self-Normalized Maximal Inequality
This addresses the challenge of providing valid learning guarantees for adaptive experiments in reinforcement learning and bandit settings, representing a theoretical advancement rather than an incremental improvement.
The paper tackles the problem of learning policies from adaptive experiments where data dependencies break standard i.i.d. assumptions, developing a self-normalized maximal inequality for martingale processes and a variance-regularized pessimistic off-policy learning objective that achieves fast convergence rates, improving over the usual 1/√n baseline.
Adaptive experiments produce dependent data that break i.i.d. assumptions that underlie classical concentration bounds and invalidate standard learning guarantees. In this paper, we develop a self-normalized maximal inequality for martingale empirical processes. Building on this, we first propose an adaptive sample-variance penalization procedure which balances empirical loss and sample variance, valid for general dependent data. Next, this allows us to derive a new variance-regularized pessimistic off-policy learning objective, for which we establish excess-risk guarantees. Subsequently, we show that, when combined with sequential updates and under standard complexity and margin conditions, the resulting estimator achieves fast convergence rates in both parametric and nonparametric regimes, improving over the usual $1/\sqrt{n}$ baseline. We complement our theoretical findings with numerical simulations that illustrate the practical gains of our approach.