REVIEW 3 major objections 6 minor 1 cited by
Optimization of Epsilon-Greedy Exploration
T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper turns epsilon-greedy exploration-rate selection into a differentiable Bayesian-regret minimization problem, solved by SGD and re-solved with model-predictive control after every batch.
desk verdict Useful framework for tuning epsilon-greedy under batching, but Algorithm 1's shared Gaussian draw across items is a real theory-implementation gap that needs fixing before the claims stand. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the differentiable approximation $\bar{J}_1(\varepsilon_{1:T}, \beta_1, \Sigma_1)$ of Bayesian cumulative regret. It is built from Lemma 4.1's closed-form posterior evolution: given the current posterior, the distribution of any future posterior is $\Sigma_{s,a} = (\Sigma_{t,a}^{-1} + \sum_{l=t}^{s-1} \varepsilon_l n_l \bar{I})^{-1}$ and $\beta_{s,a} = \beta_{t,a} + (\Sigma_{t,a} - \Sigma_{s,a})^{1/2}Z_s$, with $\bar{I}$ the population design matrix. This makes the objective a smooth function of the exploration rates, estimated by Monte Carlo over standard normals and user embeddings, and minimized by projected SGD; the same surrogate is re-optimized at each period in the MPC loop.
What would settle it
Run the proposed SGD planner and a dense grid search over epsilon schedules on a specific $N=500$, $K=5$, spike-arrival bandit instance with $d=128$ where the optimum drives $\varepsilon_t$ to zero; if the schedule from the large-batch approximation has regret noticeably above the grid-search optimum beyond Monte Carlo error, the finite-sample fidelity of the approximation is refuted.
Extended reading notes
Core claim
The paper claims that for batched, short-horizon cold-start problems, the right epsilon-greedy schedule can be obtained by solving $\min_{\varepsilon_{1:T}} \mathbb{E}_{\theta \sim \mathcal{N}(\beta_1,\Sigma_1)}[\mathrm{Regret}_T(\varepsilon_{1:T})]$ through SGD. Under Gaussian noise, a Gaussian prior, and posterior updates using only explore-group data, the future posterior has a closed-form distribution: $\Sigma_{s,a} = (\Sigma_{t,a}^{-1} + \sum_{l=t}^{s-1} I_{l,a}(\varepsilon_l))^{-1}$ and $\beta_{s,a} = \beta_{t,a} + (\Sigma_{t,a} - \Sigma_{s,a})^{1/2} Z_s$. Replacing the empirical design matrix with the population design matrix $I = s^{-2}K^{-1}\mathbb{E}[XX^\top]$ makes the covariance update linear in $\varepsilon_t$ and the whole regret estimate differentiable, so gradient descent applies. The paper further claims that re-solving this optimization after every batch (MPC) adapts the exploration rate and that the resulting schedules match or beat the best heuristic in each setting, including beating batched Thompson Sampling in these short-horizon batched regimes.
Load-bearing premise
The load-bearing premise is that the large-batch approximation to Bayesian regret, in which the empirical design matrix is replaced by its expectation, stays accurate at the modest sample sizes and zero-exploration rates used in practice, even though the theorem proving accuracy only covers strictly positive exploration rates and $n$ going to infinity.
Editorial extensions
If this is right
- A platform can replace hand-tuned epsilon constants with an SGD-computed schedule: the inputs are the prior, samples of user embeddings, and batch-size estimates, with no per-setting constant tuning.
- Optimal exploration depends on the arrival pattern: for spike arrivals, exploring heavily in the first large batch and then going greedy is often best, while for increasing arrivals spreading exploration is better, so no fixed rule of thumb wins everywhere.
- Because re-solving after each batch adapts to realized learning progress, MPC typically beats a static planner computed once under the prior.
- Constraints such as a minimum exploration floor for inference or off-policy evaluation can be incorporated directly into the optimization, changing the schedule appropriately.
- In the short horizons and batched settings tested, tuned uniform exploration can outperform batched Thompson Sampling, which over-explores.
Reading between the lines
- The authors leave implicit that the same surrogate-objective machinery extends to any differentiable function of the posterior, so objectives like top-K regret, slate decisions, or constraints on traffic allocation could be optimized in the same loop; the paper only sketches these.
- A testable extension suggested by the theory is that performance should degrade gracefully but measurably as batch sizes shrink or as the optimal schedule drives $\varepsilon_t$ to zero, because the large-batch approximation error is only controlled for strictly positive rates and $n \to \infty$; probing small $N$ and zero rates would map the method's practical envelope.
- The experiments assume a misspecified isotropic prior; a natural next test is whether calibrating the prior to existing item embeddings, which the authors suggest, widens or narrows the gap between Planner and MPC and the best heuristic, especially for smaller $N$.
- The framework could be inverted to choose the arrival and batch allocation $\lambda_t$ jointly with exploration, a decision the authors name as future work; if batch sizes are partly controllable, optimizing both could yield further regret gains.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses the practical problem of tuning epsilon-greedy exploration schedules in batched contextual bandit settings typical of recommender-system cold start. The authors derive a differentiable expression for Bayesian cumulative regret under a linear reward model (Proposition 4.2), introduce a large-batch approximation with an asymptotic accuracy guarantee (Theorem 4.4), and propose SGD-based Planner and Model-Predictive Control (MPC) algorithms to optimize the exploration rates. Experiments on MovieLens and Netflix data show that the optimized schedules match or outperform tuned heuristics (including oracle-tuned epsilon-greedy and explore-then-commit) and, in some short-horizon batched settings, outperform batched Thompson Sampling.
Significance. If the central claims hold, this is a valuable framework for production recommendation systems: it provides a principled, differentiable objective for exploration scheduling, handles practical constraints such as minimum exploration rates, and demonstrates robustness to noisy arrival-rate estimates. The paper's strengths include the exact closed-form Bayesian regret expression, the asymptotic approximation theorem, extensive benchmarking against strong baselines, and a thought-provoking finding that optimized uniform exploration can beat batched Thompson Sampling in short-horizon settings. However, the central algorithmic claim is currently undermined by a mismatch between the pseudocode's shared noise draws and the independent draws needed by the theory, and the theoretical guarantee does not cover the actual search domain or the diagonal approximation used in the experiments.
major comments (3)
- [§5, Algorithm 1] The pseudocode draws one standard normal vector Z_s per period and reuses it for every item in the update beta_{s,a} = beta_{t,a} + (Sigma_{t,a} - Sigma_{s,a})^{1/2} Z_s. Under Assumption 3, the posterior means of different items are conditionally independent, so the correct simulation (as used in the proof of Theorem 4.4, where z_a are i.i.d. across items) requires independent draws Z_{s,a} for each item. Reusing Z_s induces positive correlation across items, which lowers E[max_a X_i^T beta_{s,a}] relative to the independent case; consequently the gradients computed in Algorithm 1 are not the gradients of the Jbar defined in Proposition 4.2, and the central claim that the algorithm directly minimizes Bayesian regret is not supported by the pseudocode. Please correct the pseudocode to sample item-specific noise, and clarify whether the reported experiments used item-specific draws.
- [§4, Theorem 4.4; §5, Eq. (27)] Theorem 4.4 assumes epsilon_t > 0 for all t and n_t = lambda_t n with n tending to infinity, but the optimization domain in Eq. (27) allows epsilon_t = 0, and the schedules shown in Figure 2 reach zero. The approximation guarantee therefore does not cover the schedules that Algorithm 2 actually outputs. Moreover, the experiments use N = 500 or 5000 with d = 128, which is far from the asymptotic regime. Please either restrict the feasible domain to epsilon_t >= delta > 0 in the theoretical statement, extend the analysis to boundary points (where the limiting design matrix can be degenerate), or clearly indicate that the theorem applies only to an interior relaxation of the implemented problem.
- [§6, Implementation Details] The experiments replace the posterior covariance and the population design matrix with diagonal approximations, while Proposition 4.2 and Theorem 4.4 are stated for full covariance matrices. The objective actually optimized in the experiments is therefore not the Jbar analyzed in the theory. Please add an analysis or at least a discussion of how the diagonal approximation affects the regret-minimizing schedule, or formally treat the diagonal approximation as a separate approximate objective with its own justification.
minor comments (6)
- [§3] The word 'horison' should be 'horizon'.
- [§4, Lemma 4.3] The summation indices in the statement of Lemma 4.3 are inconsistent: I_{t,a}(epsilon_t) appears inside a sum over l, and the statement mixes epsilon_t and epsilon_l. Please correct the notation to I_{l,a}(epsilon_l).
- [§5, Algorithm 1] The covariance update line reads 'Sigma^{-1}_s = Sigma^{-1}_{t,a} + sum_{l=1}^{s-1} epsilon^{(k)}_l n_l I' without an item subscript on Sigma_s and with an ill-formed summation symbol; please typeset it as 'Sigma^{-1}_{s,a} = Sigma^{-1}_{t,a} + sum_{l=t}^{s-1} epsilon^{(k)}_l n_l I'.
- [§6] The grid for EpsGreedy* is listed as [0.05, 0.01, 0.1, 0.5, 1.0], which is not in increasing order; if 0.01 is intended, please reorder, and if 0.05 was intended to be included, note that it duplicates the first entry.
- [§6, Figure 2] The caption says 'each line corresponds to one of 100 problem instances' while the experiments average over 1000 bandit problems; please reconcile the numbers.
- [§4, Lemma 4.1] Lemma 4.1 is imported from the authors' prior work [4] and is the key tool for the posterior evolution; for self-containment, please include a brief derivation in the appendix or at least a precise reference to the lemma's proof.
Circularity Check
No significant circularity: the Bayesian-regret derivation is direct, the cited prior-work lemma is an independent parameter-free result, and optimized schedules are evaluated on separate bandit instances.
full rationale
The paper does not exhibit circular reasoning. The central objective (18)-(21) is a direct Bayesian-regret computation: after invoking Lemma 4.1 (quoted from the authors' prior work [4]) for the closed-form distribution of future posterior means, Proposition 4.2 derives the regret expression by the tower property of expectation. The cited lemma is a parameter-free Gaussian-posterior evolution result whose stated assumptions do not include the target regret and is therefore independent support rather than a self-citation loop. The large-batch surrogate Jbar is obtained by replacing empirical design matrices with population quantities via matrix concentration (Lemma 4.3), and Theorem 4.4 bounds the approximation error; this is a mathematical approximation, not a fitted parameter renamed as a prediction. Exploration rates are optimized on a misspecified prior (beta1=0, Sigma1=I) and evaluated on separate bandit instances, so the reported regret is not an in-sample fit. The only flagged concern, that Algorithm 1 reuses one Gaussian draw Z_s across all items in the simulated posterior, is an implementation/theory mismatch that is a correctness risk, not a reduction of the output to the input. No step in the derivation chain is equivalent by construction to its own assumptions.
Assumptions & free parameters
free parameters (4)
- Prior mean beta_1 and covariance Sigma_1 =
0 and I_dK
- SGD step size alpha and number of gradient steps L =
not specified
- Ridge regularization nu =
1
- Diagonal approximation of Sigma_t,a =
not specified
assumptions (6)
- standard math Lemma 4.1 (from [4]): The distribution of future posterior (beta_s,a, Sigma_s,a) conditional on current posterior follows the given recursive form.
- domain assumption Assumption 1: reward noise is iid Gaussian N(0,s^2).
- domain assumption Assumption 2: posterior is updated using only explore-group data.
- domain assumption Assumption 3: prior covariance is block-diagonal across items.
- domain assumption Assumption 4: user embeddings are bounded, ||X_i||^2 <= C a.s.
- domain assumption Reward is exactly linear: r(x,a) = x^T theta_a.
Cite this review
Pith. "Pith review of Optimization of Epsilon-Greedy Exploration." pith.science (2026). https://pith.science/paper/LFDM5MZV
@misc{pith2026250603324,
author = {Pith},
title = {Pith review of: Optimization of Epsilon-Greedy Exploration},
year = {2026},
howpublished = {\url{https://pith.science/paper/LFDM5MZV}},
note = {Machine review of arXiv:2506.03324}
}
read the original abstract
Modern recommendation systems rely on exploration to learn user preferences for new items, typically implementing uniform exploration policies (e.g., epsilon-greedy) due to their simplicity and compatibility with machine learning (ML) personalization models. Within these systems, a crucial consideration is the rate of exploration - what fraction of user traffic should receive random item recommendations and how this should evolve over time. While various heuristics exist for navigating the resulting exploration-exploitation tradeoff, selecting optimal exploration rates is complicated by practical constraints including batched updates, time-varying user traffic, short time horizons, and minimum exploration requirements. In this work, we propose a principled framework for determining the exploration schedule based on directly minimizing Bayesian regret through stochastic gradient descent (SGD), allowing for dynamic exploration rate adjustment via Model-Predictive Control (MPC). Through extensive experiments with recommendation datasets, we demonstrate that variations in the batch size across periods significantly influence the optimal exploration strategy. Our optimization methods automatically calibrate exploration to the specific problem setting, consistently matching or outperforming the best heuristic for each setting.
Figures
Forward citations
Cited by 1 Pith paper
-
Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
A Pareto-perturbed follow-the-perturbed-leader policy achieves best-of-both-worlds regret for decoupled bandits with O(K log K) per-step cost and no resampling.
Reference graph
Works this paper leans on
-
[1]
A. Barraza-Urbina. The exploration-exploitation trade-off in interactive recom- mender systems. In Proceedings of the Eleventh ACM Conference on Recommender Systems, pages 431–435, 2017
work page 2017
-
[2]
J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/jax-ml/jax
work page 2018
- [3]
-
[4]
E. Che, D. R. Jiang, H. Namkoong, and J. Wang. Optimization-driven adaptive experimentation. arXiv preprint arXiv:2408.04570, 2024
work page Pith review arXiv 2024
-
[5]
M. Chen. Exploration in recommender systems. In Proceedings of the 15th ACM Conference on Recommender Systems , pages 551–553, 2021
work page 2021
-
[6]
W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the fourteenth international conference on artifi- cial intelligence and statistics , pages 208–214. JMLR Workshop and Conference Proceedings, 2011
work page 2011
-
[7]
B. Do, T. Adebiyi, and R. Zhang. Epsilon-greedy thompson sampling to bayesian optimization. Journal of Computing and Information Science in Engineering , 24 (12), 2024
work page 2024
-
[8]
H. Esfandiari, A. Karbasi, A. Mehrabian, and V. Mirrokni. Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 35, pages 7340–7348, 2021
work page 2021
Show all 37 references
-
[9]
Foster, D
A. Foster, D. R. Ivanova, I. Malik, and T. Rainforth. Deep adaptive design: Amor- tizing sequential bayesian experimental design. In International conference on machine learning, pages 3384–3395. PMLR, 2021
2021
-
[10]
Z. Gao, Y. Han, Z. Ren, and Z. Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems , 32, 2019
2019
-
[11]
Garivier, T
A. Garivier, T. Lattimore, and E. Kaufmann. On explore-then-commit strategies. Advances in Neural Information Processing Systems , 29, 2016
2016
-
[12]
Glowacka
D. Glowacka. Bandit algorithms in recommender systems. In Proceedings of the 13th ACM conference on recommender systems , pages 574–575, 2019
2019
-
[13]
B. Hao, T. Lattimore, and M. Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems , 33:10753–10763, 2020
2020
-
[14]
T. Jin, X. Yang, X. Xiao, and P. Xu. Thompson sampling with less exploration is fast and optimal. In International Conference on Machine Learning , pages 15239–15261. PMLR, 2023
2023
-
[15]
Kalkanli and A
C. Kalkanli and A. Ozgur. Batched thompson sampling. Advances in Neural Information Processing Systems, 34:29984–29994, 2021
2021
-
[16]
Karbasi, V
A. Karbasi, V. Mirrokni, and M. Shadravan. Parallelizing thompson sampling. Advances in Neural Information Processing Systems , 34:10535–10548, 2021
2021
-
[17]
Koren, R
Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30–37, 2009
2009
-
[18]
Langford and T
J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi- armed bandits. Advances in neural information processing systems , 20(1):96–1, 2007
2007
-
[19]
Lattimore and C
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020
2020
-
[20]
L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to per- sonalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010
2010
-
[21]
W. Li, A. Barik, and J. Honorio. A simple unified framework for high dimensional bandit problems. In International Conference on Machine Learning , pages 12619– 12655. PMLR, 2022
2022
-
[22]
Liang and N
D. Liang and N. Vlassis. Local policy improvement for recommender systems. arXiv preprint arXiv:2212.11431, 2022
2022 arXiv
-
[23]
J. Mary, R. Gaudel, and P. Philippe. Bandits warm-up cold recommender systems. arXiv preprint arXiv:1407.2806, 2014
2014 arXiv
-
[24]
McInerney, B
J. McInerney, B. Lacker, S. Hansen, K. Higley, H. Bouchard, A. Gruson, and R. Mehrotra. Explore, exploit, and explain: personalizing explainable recommen- dations with bandits. In Proceedings of the 12th ACM conference on recommender systems, pages 31–39, 2018
2018
-
[25]
H. T. Nguyen, J. Mary, and P. Preux. Cold-start problems in recommendation systems via contextual-bandit algorithms. arXiv preprint arXiv:1405.7544, 2014
2014 arXiv
-
[26]
Paszke, S
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Des- maison, L. Antiga, and A. Lerer. Automatic differentiation in pytorch. 2017
2017
-
[27]
Perchet, P
V. Perchet, P. Rigollet, S. Chassang, and E. Snowberg. Batched bandit problems. 2016
2016
-
[28]
Rainforth, A
T. Rainforth, A. Foster, D. R. Ivanova, and F. Bickford Smith. Modern bayesian experimental design. Statistical Science, 39(1):100–114, 2024
2024
-
[29]
D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial on thompson sampling. Foundations and Trends® in Machine Learning, 11(1):1–96, 2018
2018
-
[30]
A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock. Methods and metrics for cold-start recommendations. In Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, pages 253–260, 2002
2002
-
[31]
Silva, T
N. Silva, T. Silva, H. Werneck, L. Rocha, and A. Pereira. User cold-start prob- lem in multi-armed bandits: when the first recommendations guide the user’s experience. ACM Transactions on Recommender Systems , 1(1):1–24, 2023
2023
-
[32]
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018
2018
-
[33]
Swaminathan, A
A. Swaminathan, A. Krishnamurthy, A. Agarwal, M. Dudik, J. Langford, D. Jose, and I. Zitouni. Off-policy evaluation for slate recommendation. Advances in Neural Information Processing Systems , 30, 2017
2017
-
[34]
L. Tang, Y. Jiang, L. Li, and T. Li. Ensemble contextual bandits for personalized recommendation. In Proceedings of the 8th ACM Conference on Recommender Systems, pages 73–80, 2014
2014
-
[35]
van den Akker, O
B. van den Akker, O. Jeunen, Y. Li, B. London, Z. Nazari, and D. Parekh. Practical bandits: An industry perspective. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining , pages 1132–1135, 2024
2024
-
[36]
Vermorel and M
J. Vermorel and M. Mohri. Multi-armed bandit algorithms and empirical eval- uation. In European conference on machine learning , pages 437–448. Springer, 2005
2005
-
[37]
X. Wang, Y. Wang, D. Hsu, and Y. Wang. Exploration in interactive personalized music recommendation: a reinforcement learning approach. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM) , 11(1): 1–22, 2014
2014
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.