A Finite-Time Error Question behind a Convergence Rate

Authors

  • James Graham Author
  • Connor Reynolds Author
  • Bruce Powell Author

Abstract

Finite-time knowledge-gradient analysis and rate analysis need compatible objectives and observation assumptions before their results are compared. A practical test should include the budgets actually available and retain complete-run uncertainty. A favorable limit does not establish early stopping reliability, while a finite observation need not contradict a theorem formulated for a different regime. This focused synthesis develops an empirical comparison that preserves the terminal action, observation process, and total verification cost. Its proposed tests are prospective; no new simulation run, model-training result, or intervention effect is reported.

References

  1. Y. Li and S. Gao, “Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms,” Automatica, vol. 153, 111042, 2023.
  2. Y. Li and S. Gao, “On the Finite-Time Performance of the Knowledge Gradient Algorithm,” Proceedings of the 39th International Conference on Machine Learning, pp. 12741–12764, 2022.
  3. Li, Y., Wang, H., Shang, X., Tang, X., Cao, Y., & Chen, X. (2026). BoostAPR: Boosting Automated Program Repair via Execution-Grounded Reinforcement Learning with Dual Reward Models. arXiv preprint arXiv:2605.09134.
  4. Kim, Seong-Hee, and Barry L. Nelson. “A Fully Sequential Procedure for Indifference-Zone Selection in Simulation.” ACM Transactions on Modeling and Computer Simulation, vol. 11, no. 3, 2001, pp. 251–273. https://doi.org/10.1145/502109.502111.
  5. Chick, Stephen E., and Koichiro Inoue. “New Two-Stage and Sequential Procedures for Selecting the Best Simulated System.” Operations Research, vol. 49, no. 5, 2001, pp. 732–743. https://doi.org/10.1287/opre.49.5.732.10615.
  6. Frazier, Peter I., Warren B. Powell, and Savas Dayanik. “A Knowledge-Gradient Policy for Sequential Information Collection.” SIAM Journal on Control and Optimization, vol. 47, no. 5, 2008, pp. 2410–2439. https://doi.org/10.1137/070693424.
  7. Rasmussen, Carl Edward, and Christopher K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006. https://gaussianprocess.org/gpml/.
  8. Sacks, Jerome, William J. Welch, Toby J. Mitchell, and Henry P. Wynn. “Design and Analysis of Computer Experiments.” Statistical Science, vol. 4, no. 4, 1989, pp. 409–423. https://doi.org/10.1214/ss/1177012413.
  9. Bertsimas, Dimitris, and Melvyn Sim. “The Price of Robustness.” Operations Research, vol. 52, no. 1, 2004, pp. 35–53. https://doi.org/10.1287/opre.1030.0065.
  10. Campi, Marco C., and Simone Garatti. “The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs.” SIAM Journal on Optimization, vol. 19, no. 3, 2008, pp. 1211–1230. https://doi.org/10.1137/07069821X.
  11. Glasserman, Paul. Monte Carlo Methods in Financial Engineering. Springer, 2004. https://doi.org/10.1007/978-0-387-21617-1.

Downloads

Published

2026-08-26

Versions

Issue

Vol. 2 No. 8 (2026): August 2026

Section

Articles