Online and Off-Policy Learning for Large Action Spaces: Structured Exploration & Optimization

Research Background: Why Large Action Spaces Are Challenging

Contextual bandits model interactive decision-making: each round the environment provides a context, the agent selects an action from a large set, and observes only the reward for that action. Unlike supervised learning, counterfactual rewards are unobserved; unlike full RL, there are no long-term state transitions. The thesis identifies three simultaneous difficulties when the action space is large: (1) statistical – many actions are rarely or never selected, leading to insufficient posterior or reward estimates; (2) computational – classic linear or Bayesian bandits maintain per-action covariance matrices, causing memory and computation to explode; (3) optimization – offline policy learning often uses importance-sampling objectives that become highly non-convex and gradient-pathological under large softmax policies.

Overall Framework: Online and Offline Learning

Online learning aims to maximize cumulative reward during real interaction, balancing exploration and exploitation. Thompson sampling draws a world from the posterior and acts optimally in it, but independent per-action parameters prevent generalization across actions. Offline learning must improve a policy using only historical logs (context, action, reward) without further interaction. The core difficulties are missing counterfactuals and support mismatch: if the logging policy never chose certain actions, standard offline methods cannot reliably evaluate them; if the new policy deviates too far, importance weights explode variance.

The thesis unifies both paradigms under the large-action-space lens: online learning needs structural priors to share information across actions; offline learning needs structure, optimizable objectives, and pessimism to control risk from unobserved counterfactuals.

Online Learning: Mixed-Effects Thompson Sampling

Chapter 3 introduces a mixed-effects bandit framework where action parameters are generated from a small set of shared "effects." For example, movies are characterized by latent factors like genre, style, actors; user feedback on one movie updates the relevant factors, benefiting other movies. Formally, each action parameter is a linear combination of shared effect parameters with a sparse mixing-weight matrix. This two-layer graphical model enables statistical sharing, especially when the number of actions far exceeds the number of latent effects.

Theoretically, the thesis provides a Bayesian regret bound for mixed-effects Thompson sampling. Regret decomposes into the cost of learning action-specific parameters and the cost of learning shared effects. With a good structural prior, the effective action scale is smaller than the raw action count, so regret grows with the effective scale. Computationally, closed-form posteriors are available for Gaussian linear rewards; for generalized linear models, approximate posteriors keep inference tractable.

Experiments on synthetic linear/logistic rewards and the MovieLens recommendation dataset show that mixed-effects Thompson sampling outperforms baselines that ignore structure. As the action count grows from 100 to 100,000, the gap widens, confirming that action-sharing structure becomes more critical in larger spaces.

Online Learning: Diffusion Priors and Deep Generative Structure

Chapter 4 proposes Diffusion Thompson Sampling. Mixed-effects models assume relatively explicit linear/hierarchical structure, but real action spaces (items, molecules, images, text) often exhibit highly nonlinear generative correlations. The thesis uses a pre-trained diffusion model as a prior over action parameters, capturing complex inter-action dependencies.

In Diffusion Thompson Sampling, action parameters are viewed as generated from latent variables via a diffusion process. The algorithm first learns a generative distribution of action parameters offline, then during online interaction updates the posterior over latents given observed rewards and samples actions. Compared to maintaining separate high-dimensional posteriors per action, the diffusion prior compresses information into a shared generative structure, reducing memory complexity to linear in latent dimension and action count, and improving runtime scalability.

Experiments cover linear/nonlinear diffusion priors combined with linear/nonlinear reward models. Results show significant exploration efficiency gains when the generative structure matches reality, and robustness even under prior misspecification. The key insight: exploration in large action spaces should leverage offline-learned action representations and generative regularities, not just per-action confidence intervals.

Offline Learning: Structured Direct Method

Chapter 6 tackles offline policy learning. Standard direct methods first estimate a reward function for every context-action pair, then choose the policy maximizing estimated reward. In large action spaces, many actions have little or no log coverage, so their reward estimates revert to priors, limiting policy improvement.

The structured direct method assumes all action parameters are generated from shared latent variables, inducing natural correlations. Even if an action rarely appears in logs, feedback on related actions updates the shared latents, indirectly improving its reward estimate. This structural prior relaxes the requirement for full action coverage in the logging policy.

Theoretically, the thesis proves convergence in terms of Bayesian suboptimality without requiring the logging policy to cover all actions. Empirically, the advantage over standard direct methods grows with action space size.

Offline Learning: Optimization Geometry Matters More Than Estimation Accuracy

Chapter 7 presents a pivotal insight: in large-action-space offline learning, poor final performance often stems not from inaccurate reward estimation but from the optimization objective itself being hard to solve. Classic importance-sampling objectives are unbiased or low-bias in theory, but under large softmax policies they exhibit flat regions, sharp curvatures, and numerous local pathologies.

A toy example illustrates the difference: the policy-weighted log-likelihood objective yields a smoother, near-convex geometry, while the importance-sampling objective suffers from vanishing and exploding gradients simultaneously. At million-action scale, this optimization pathology amplifies, making "more sophisticated estimators" unreliable.

The thesis advocates policy-weighted log-likelihood objectives, which reweight the log-likelihood of logged actions by reward and logging probability, resembling weighted cross-entropy. Though they sacrifice some direct counterfactual interpretation, they dramatically improve optimizability. Experiments on MovieLens, Amazon, and large-scale recommendation data confirm that optimization-friendly objectives often outperform complex but hard-to-optimize estimators.

This has major engineering implications: large-action systems ultimately rely on stochastic optimizers; if the objective geometry is pathological, even statistically elegant properties may not translate into deployable policies. The thesis shifts evaluation focus from "is the estimator more accurate?" to "can the objective be stably optimized?"

Offline Learning: Exponential Smoothing and Pessimism

Chapter 8 addresses variance control in importance sampling. Traditional hard clipping truncates large importance weights, reducing variance but introducing bias with a hard-to-choose threshold. The thesis proposes exponential smoothing as a continuous, differentiable regularization that trades off bias and variance in an optimizable way.

Further, exponential smoothing is embedded in a PAC-Bayes pessimistic learning framework. The pessimistic principle: policies insufficiently validated by offline data should not be optimistically selected. Instead of maximizing empirical estimated reward, the algorithm maximizes a lower confidence bound that incorporates empirical gain, model complexity, importance-weight fluctuations, and generalization risk.

Experiments on MNIST, FashionMNIST, EMNIST, and CIFAR (treated as offline contextual bandits) show the PAC-Bayes pessimistic objective outperforms multiple baselines across varying logging policy qualities. Notably, the choice of pessimistic learning objective matters more than the choice of importance-weight regularization technique, echoing Chapter 7: large-action offline learning is not merely an estimation problem but a joint challenge of estimation, optimization, and risk control.

Experimental Conclusions and Practical Implications

The thesis evaluates across synthetic environments, MovieLens, and multiple classification datasets, varying action count, latent effect dimension, context dimension, reward model, generative prior mismatch, logging policy quality, and optimization hyperparameters. Four main conclusions emerge:

Action-sharing structure significantly boosts online exploration efficiency. Whether via mixed-effects or diffusion priors, exploiting inter-action correlations allows generalization from few feedbacks, with greatest gains when actions far outnumber latent dimensions.

Deep generative models serve as scalable priors for large action spaces. Diffusion Thompson Sampling demonstrates a viable pipeline: learn a generative distribution from offline action representations, then use it for online Bayesian exploration. This provides a template for recommendation, molecular design, content generation, and combinatorial action spaces.

Offline policy learning must prioritize optimization geometry. Importance-sampling estimators' statistical properties do not guarantee learnable policies; under large softmax policies, stable log-likelihood-style objectives can be more reliable than theoretically more direct estimation targets.

Pessimism is a necessary safeguard in offline learning. The more biased the logs and the larger the action space, the more unobserved counterfactuals exist, requiring conservatism toward high-variance, low-coverage regions. PAC-Bayes lower bounds turn this conservatism into an optimizable objective.

Future Directions

The thesis outlines open avenues: richer action structures (graphs, text/image representations, combinatorial actions, dynamic action sets) for online learning; integrating diffusion priors with deep context encoders, non-Gaussian rewards, and real-system feedback. For offline learning, combining structured direct methods with doubly robust estimation, conservative policy improvement, and uncertainty calibration; automating hyperparameter selection for pessimistic learning to reduce engineering tuning burden. More broadly, the thesis reframes the classic recommender-system problem: when actions are vast, feedback sparse, and logs biased, learning algorithms must simultaneously answer "which actions are similar," "which objectives are optimizable," and "which gains are trustworthy" – all three are indispensable.

Code example

来源：专知
本文
约5000字
，建议阅读
8
分钟
这篇博士论文围绕大动作空间上下文老虎机，系统推进了在线与离线学习两条路线。