On-Policy and Off-Policy Learning for Large Action Spaces

2026-07-30 · 15:56 UTC ·Imad Aouali ·1 min read

Brief

The thesis by Imad Aouali (PhD, 241 pages; arXiv:2607.28408v1, 2026-07-30) studies contextual-bandit policy learning with very large action sets. It develops structured Bayesian on-policy algorithms (meTS, dTS) with regret bounds based on an effective action count, and off-policy solutions (sDM, concave policy-weighted likelihoods, differentiable pessimism using exponential smoothing and PAC-Bayes) that address high-variance importance weights, sparse coverage, extrapolation bias, and optimization-dominated error.

Why it matters

Introduces two structured Bayesian on-policy methods: meTS (a mixed-effect extension of Thompson Sampling) and dTS (using diffusion-inspired priors). Both share information across actions and deliver regret guarantees that scale with an effective number of actions rather than the raw action set size.

Key details

For off-policy learning, proposes sDM (a structured direct method with latent variables), proves that optimization error can dominate estimation error in very large action spaces, and introduces concave, efficiently optimizable policy-weighted log-likelihoods plus differentiable pessimistic estimators (exponential smoothing with PAC-Bayesian bounds) to control bias–variance of regularized importance-sampling.

Abstract

This thesis studies policy learning in interactive systems where an agent observes a context, selects an action from a very large set, and receives partial feedback. The main framework is contextual bandits, with two paradigms: on-policy learning, where the agent interacts sequentially with the environment and minimizes regret, and off-policy learning, where it learns from logged data collected by a logging policy. In large action spaces, both settings face major challenges: inefficient exploration, sparse data coverage, high-variance importance weights, extrapolation bias, and difficult optimization landscapes. The first part develops structured Bayesian methods for on-policy learning. We introduce meTS, a mixed-effect extension of Thompson sampling, and dTS, which leverages diffusion-inspired priors to model dependencies between actions. These methods share information across actions and yield regret guarantees depending on an effective number of actions. The second part addresses off-policy learning. We propose sDM, a structured direct method based on latent variables, show that optimization error can dominate estimation error in large action spaces, and introduce concave, efficiently optimizable policy-weighted log-likelihood objectives. Finally, we develop differentiable pessimistic methods based on exponential smoothing and PAC-Bayesian bounds to control the bias-variance trade-off of regularized importance-sampling estimators.

Comment: PhD Thesis, 241 pages