Why d log T Particles Are Enough, and What Carries Over to Networks

The figures step through like slides. Use → or ▶, and step back with ←.

1. The particles are a random projection of the history

Each particle is the whole data history weighted by one random direction, so M particles are M random projections of it.

Write the history as $\Phi_t$ (the prior, then one column per input) and the injected noise as $\Pi_t$ (the prior draws, then one row per data point). The arrows of the cloud are their product, and its covariance is

A new data point appends one column and one row, so the product changes by a rank-one term and never grows. The injected noise is a Johnson–Lindenstrauss projection of the history from $d+t$ dimensions down to M, maintained as a stream.

2. Once the agent picks its own data, the classical lemma fails

The noise is drawn once and never redrawn, which keeps the update cheap, but it also means the old noise steers the inputs the agent chooses next.

data

particle

injected noise

Thin arrows: the update

Thick arrows: the particle picks the next input

Fixed data

• inputs fixed in advance
• injected noise never reaches them
• classical JL applies

Adaptive data

• each particle picks the next input
• old injected noise steers the history
• classical JL fails

One particle (M = 1): regret grows linearly. Thompson sampling flattens.

← ▶ → 6 / 6

With fixed data the classical lemma applies; with adaptive data it does not. With one particle the regret grows linearly, while Thompson sampling flattens.

The classical lemma needs the vectors to be fixed before the projection is drawn. Here each new column of the history is chosen after the agent has seen earlier rows of the noise. That dependence is also why the only earlier analysis (Qin et al., 2022) needed an ensemble linear in the horizon times the number of actions. Practitioners had been using 10 to 100 members for a decade without an explanation.

3. Sequential Johnson–Lindenstrauss: adaptivity costs one log T

Norms are preserved for adaptively chosen sequences, uniformly over time, with one extra logarithm of the horizon.

Let $\mathbf{z}_i$ be the rows of the injected noise and $v$ a vector of the history whose entries may depend on all earlier rows. Then, with probability at least $1-\delta$,

Independence cannot be used, so the proof runs through a stopped process and self-normalized martingale concentration. For the cloud, the result reads

With M of order d log T, the regret is comparable to exact Thompson sampling for compact or finite action sets, fixed or time-varying. Memory grows with the logarithm of the lifetime: doubling the horizon adds a number of particles proportional to d, however long the agent has already run.

4. In a network the same update is an SGD step

The exact gain of the linear model becomes a learning rate, and each particle becomes a linear head trained on its own noisy targets.

The posterior sampler is trained by the same stochastic updates as the model, on the same data stream, at the cost of a few extra linear heads. Seen from the network’s side, the model has a second input:

Neither half works alone. Without the noisy targets, a network learns to ignore the index. Without the index, the noisy targets give one perturbed model, and the next sample needs a full retraining.

Where the index should enter (the last layer, deeper layers, adapters on a large model) is a design choice that is still largely unexplored.

5. Results: less data, fewer parameters

Directed exploration buys the data efficiency, and a few linear heads keep the compute bounded.

In deep RL, HyperAgent adds the same heads to DQN:

References

• Y. Li, J. Xu, B. Wang, Z.-Q. Luo. Scalable Exploration via Ensemble++. NeurIPS 2025.
• Y. Li, J. Xu, L. Han, Z.-Q. Luo. Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent. ICML 2024.
• Y. Li. Probability Tools for Sequential Random Projection. arXiv, 2024.
• Z. Li, Y. Li, Y. Zhang, T. Zhang, Z.-Q. Luo. HyperDQN: A Randomized Exploration Method for Deep Reinforcement Learning. ICLR 2022.
• C. Qin, Z. Wen, X. Lu, B. Van Roy. An Analysis of Ensemble Sampling. NeurIPS 2022.

Citation

@inproceedings{li2024hyperagent,
  title     = {Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent},
  author    = {Li, Yingru and Xu, Jiawei and Han, Lei and Luo, Zhi-Quan},
  booktitle = {International Conference on Machine Learning},
  year      = {2024}
}