On-Policy and Off-Policy Learning for Large Action Spaces
Imad Aouali
cs.LG, cs.AI, math.ST, stat.ML
Submitted: 2026-07-30
Comments: PhD Thesis, 241 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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.
Sources
- Offline Contextual Bandit with Counterfactual Sample Identification
- Offline Evaluation of Reward-Optimizing Recommender Systems: The Case of Simulation
- Probabilistic Rank and Reward: A Scalable Model for Slate Recommendation
- Combining Reward and Rank Signals for Slate Recommendation
- User-friendly introduction to PAC-Bayes bounds
- Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation
- Meta Dynamic Pricing: Transfer Learning Across Experiments
- Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning
- Multi-task Representation Learning with Stochastic Linear Bandits
- Diffusion Posterior Sampling for General Noisy Inverse Problems
- VITS : Variational Inference Thompson Sampling for contextual bandits
- Handbook of Convergence Theorems for (Stochastic) Gradient Methods
- A Primer on PAC-Bayesian Learning
- A Unified Approach to Translate Classical Bandit Algorithms to the Structured Bandit Setting
- PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
- Adam: A Method for Stochastic Optimization
- Efron-Stein PAC-Bayesian Inequalities
- Local Policy Improvement for Recommender Systems
- Empirical Bernstein Bounds and Sample Variance Penalization
- AWAC: Accelerating Online Reinforcement Learning with Offline Datasets
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks