How to Master Online and Offline Policy Learning in Massive Action Spaces

Research Background

Contextual bandits model each interaction as a round where a context is observed, an action is chosen, and only the reward of the chosen action is revealed. When the action set grows to thousands or millions, three difficulties arise:

Statistical sparsity – many actions are rarely or never selected, leading to poor reward estimates.

Computational burden – per‑action covariance matrices or posterior parameters become infeasible to store and update.

Optimization pathology – offline importance‑sampling objectives for large‑scale softmax policies become highly non‑convex and exhibit unstable gradients.

The thesis asks two fundamental questions: how to share information among actions in online learning, and how to construct statistically sound yet optimizable objectives for offline learning.

Online Learning: Mixed‑Effect Thompson Sampling

Chapter 3 introduces a mixed‑effect bandit model in which each action’s parameter vector is generated from a small set of shared effect parameters via a weighted graph. For example, movies share latent factors such as genre, style, and actors; feedback on one movie updates these factors and benefits related movies.

The Bayesian regret bound separates the cost of learning individual action parameters from the cost of learning shared effects, showing that effective action dimensionality—not raw action count—drives regret growth. In linear‑Gaussian settings a closed‑form posterior is available; in generalized‑linear settings an approximate posterior keeps computation tractable.

Experiments on synthetic linear and logistic rewards and on the MovieLens recommendation task show that mixed‑effect Thompson sampling consistently outperforms baselines that ignore structure. The performance gap widens as the number of actions increases from 100 to 100 000, confirming that shared structure mitigates both statistical and computational difficulties.

Online Learning: Diffusion Priors (Diffusion Thompson Sampling)

Chapter 4 extends the idea by using diffusion models as priors over action parameters, capturing complex, non‑linear relationships among actions (e.g., items, molecules, images). The diffusion prior compresses information into a latent space whose dimensionality scales linearly with the number of actions, reducing memory and runtime costs.

During interaction, the agent first learns the diffusion prior offline, then updates the posterior with reward feedback to sample actions. Experiments cover linear and non‑linear diffusion priors, linear and non‑linear reward models, and action scales ranging from 10³ to 10⁵. Results show robust regret reductions even when the prior is mildly misspecified.

Offline Learning: Structured Direct Method

Chapter 6 proposes a structured direct method that assumes all action parameters share latent variables. Even if a specific action appears rarely in logs, feedback on related actions updates the shared latent variables, indirectly improving the reward estimate for the scarce action.

The method is proven to converge in a Bayesian sub‑optimality sense without requiring full coverage of the action set. Empirical results on synthetic data and real recommendation datasets (MovieLens) confirm that the advantage of the structured method grows with action‑space size.

Offline Learning: Optimization vs. Estimation

Chapter 7 argues that poor offline performance often stems from optimization difficulty rather than inaccurate reward estimation. Importance‑sampling objectives can exhibit flat regions, sharp curvature, and exploding or vanishing gradients, especially under large‑scale softmax policies.

A toy example demonstrates that a policy‑weighted log‑likelihood objective yields a smoother, more convex‑like landscape, while the importance‑sampling objective suffers from pathological gradients. Experiments on MovieLens, Amazon, and large‑scale recommendation data confirm that optimization‑friendly objectives consistently outperform statistically “more accurate” but harder‑to‑optimize estimators.

Offline Learning: Exponential Smoothing and PAC‑Bayes Pessimism

Chapter 8 replaces hard clipping of importance weights with exponential smoothing, providing a differentiable bias‑variance trade‑off. The smoothing term is embedded in a PAC‑Bayes pessimistic learning framework that penalizes policies that cannot be confidently validated by the offline data.

Experiments on MNIST, FashionMNIST, EMNIST, and CIFAR offline classification bandits show that the PAC‑Bayes pessimistic objective yields more stable policy gains across datasets, and that the choice of pessimistic objective often matters more than the specific importance‑weight regularization technique.

Experimental Conclusions

Experiments span synthetic environments, the MovieLens recommendation dataset, and several image classification datasets (MNIST, FashionMNIST, EMNIST, CIFAR). They vary action count, latent effect dimension, context dimension, reward model, prior misspecification, logging‑policy quality, and optimization hyper‑parameters. Four key takeaways emerge:

Shared action structure dramatically improves online exploration efficiency, especially when the number of actions far exceeds the latent dimension.

Deep generative priors (diffusion models) provide a practical way to encode complex action relationships for online Bayesian exploration.

In offline learning, the geometry of the optimization objective is as crucial as statistical accuracy; stable log‑likelihood‑type objectives often outperform theoretically unbiased estimators.

Pessimistic learning is essential for large‑action offline tasks, converting uncertainty about unobserved counterfactuals into a tractable, optimizable regularizer.

Future Directions

Potential extensions include richer action structures such as graphs, text, images, combinatorial actions, and dynamic action sets; tighter integration of diffusion priors with contextual encoders and non‑Gaussian rewards; combining structured direct methods with doubly robust estimation, conservative policy improvement, and uncertainty calibration; and automating hyper‑parameter selection for pessimistic objectives.

Code example

来源：专知
本文
约5000字
，建议阅读
8
分钟
围绕大动作空间下的上下文老虎机问题，系统研究了两类核心学习范式：在线学习和离线学习。