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

arXiv:2607.28408v1 Announce Type: new 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.

Related

• Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation
• Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions
• Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces
• Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning

Source: arXiv cs.LG | 2026-07-31