Black-Box Rare-Event Simulation for Safety Testing of AI Agents: An Overview

doi:10.1007/s40305-025-00585-0

Abstract

Abstract: This paper provides an overview of black-box rare-event simulation methods applicable to the safety testing of artificial intelligence agents. We explore the challenges and efficiency criteria in black-box simulation, especially emphasizing the subtle occurrence and control of underestimation errors. The paper reviews various adaptive methods, such as the cross-entropy method and adaptive multilevel splitting, highlighting both their empirical effectiveness and theoretical limitations. Additionally, it offers a comparative analysis of different confidence interval constructions for crude Monte Carlo methods, aiming to mitigate underestimation errors through effective uncertainty quantification. The paper concludes with a certifiable deep importance sampling approach, using deep neural networks to develop conservative estimators that address underestimation issues.

Key words: Rare-event simulation, Black-box systems, AI system safety, Underestimation

CLC Number:

65C05

Yuan-Lu Bai, Zhi-Yuan Huang, Henry Lam, Ding Zhao. Black-Box Rare-Event Simulation for Safety Testing of AI Agents: An Overview[J]. Journal of the Operations Research Society of China, 2025, 13(3): 750-774.

TrendMD

References

[1] Arief, M., Bai, Y., Ding, W., He, S., Huang, Z., Lam, H., Zhao, D.: Certifiable deep importance sampling for rare-event simulation of black-box systems (2021). arXiv:2111.02204
[2] Arief, M., Glynn, P., Zhao, D.: An accelerated approach to safely and efficiently test pre-production autonomous vehicles on public streets. In: 201821st International Conference on Intelligent Transportation Systems, pp. 2006-2011. IEEE (2018)
[3] Arief, M., Huang, Z., Kumar, G.K.S., Bai, Y., He, S., Ding,W., Lam, H., Zhao, D.: Deep probabilistic accelerated evaluation: A robust certifiable rare-event simulation methodology for black-box safetycritical systems. In: International Conference on Artificial Intelligence and Statistics, pp. 595-603. PMLR (2021)
[4] Asmussen, S., Glynn, P.W.: Stochastic Simulation: Algorithms and Analysis, vol. 57. Springer, New York (2007)
[5] Au, S.K., Beck, J.L.: Estimation of small failure probabilities in high dimensions by subset simulation. Probab. Eng. Mech. 16(4), 263-277(2001)
[6] Bai, Y., Huang, Z., Lam, H., Zhao, D.: Rare-event simulation for neural network and random forest predictors. ACM Trans. Model. Comput. Simul. 32(3), 1-33(2022)
[7] Bai, Y., Huang, Z., Lam, H., Zhao, D.: Overconservativeness of variance-based efficiency criteria and probabilistic efficiency in rare-event simulation. Manag, Sci 70(10), 6852-6873(2024)
[8] Bai, Y., Lam, H.: Uncertainty quantification and confidence intervals for naive rare-event estimators. J. Appl. Probab. 62(1), 84-110(2025)
[9] Blanchet, J., Lam, H.: State-dependent importance sampling for rare-event simulation: an overview and recent advances. Surv. Oper. Res. Manag. Sci. 17(1), 38-59(2012)
[10] Botev, Z.I., Ridder, A., Rojas-Nandayapa, L.: Semiparametric cross entropy for rare-event simulation. J. Appl. Probab. 53(3), 633-649(2016)
[11] Bucklew, J.: Introduction to Rare Event Simulation. Springer (2013)
[12] Cérou, F., Guyader, A.: Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25(2), 417-443(2007)
[13] Cérou, F., Guyader, A.: Fluctuation analysis of adaptive multilevel splitting. Ann. Appl. Probab. 26(6), 3319-3380(2016)
[14] Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R.: Handbook of Model Checking. vol. 10, Springer (2018)
[15] Claybrook, J., Kildare, S.: Autonomous vehicles: No driver... no regulation? Science 361(6397), 36-37(2018)
[16] Corso, A., Lee, R., Kochenderfer, M.J.: Scalable autonomous vehicle safety validation through dynamic programming and scene decomposition. In: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems, pp. 1-6. IEEE (2020)
[17] Corso, A., Moss, R.J., Koren, M., Lee, R., Kochenderfer, M.J.: A survey of algorithms for black-box safety validation (2020). arXiv:2005.02979
[18] De Boer, P.T., Kroese, D.P., Mannor, S., Rubinstein, R.Y.: A tutorial on the cross-entropy method. Ann. Oper. Res. 134(1), 19-67(2005)
[19] Dembo, A., Zeitouni, O.: Large Deviations Techniques and Applications. Springer (2010)
[20] Deo, A., Murthy, K.: Achieving efficiency in black-box simulation of distribution tails with selfstructuring importance samplers. Oper. Res. (2023)
[21] Dieker, A., Mandjes, M.: On asymptotically efficient simulation of large deviation probabilities. Adv. Appl. Probab. 37(2), 539-552(2005)
[22] Dupuis, P., Ellis, R.S.: A Weak Convergence Approach to the Theory of Large Deviations, vol. 902. Wiley (2011)
[23] Evan, A.: Fatal Tesla self-driving car crash reminds us that robots aren’t perfect. IEEE Spectrum (2016)
[24] Glasserman, P.: Monte Carlo Methods in Financial Engineering. Springer (2004)
[25] Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: Multilevel splitting for estimating rare event probabilities. Oper. Res. 47(4), 585-600(1999)
[26] Glasserman, P., Kang, W., Shahabuddin, P.: Fast simulation of multifactor portfolio credit risk. Oper. Res. 56(5), 1200-1217(2008)
[27] Glasserman, P., Li, J.: Importance sampling for portfolio credit risk. Manage. Sci. 51(11), 1643-1656(2005)
[28] Glasserman, P., Wang, Y.: Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7(3), 731-746(1997)
[29] Glynn, P.W., Iglehart, D.L.: Importance sampling for stochastic simulations. Manage. Sci. 35(11), 1367-1392(1989)
[30] Gurobi Optimization, L.: Gurobi optimizer reference manual, version 10.0. (2023). https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/10.0/refman.pdf
[31] Guyader, A., Hengartner, N., Matzner-Løber, E.: Simulation and estimation of extreme quantiles and extreme probabilities. Appl. Math. Optim. 64(2), 171-196(2011)
[32] He, S., Jiang, G., Lam, H., Fu, M.C.: Adaptive importance sampling for efficient stochastic root finding and quantile estimation. Oper. Res. 72(6), 2612-2630(2024)
[33] Heidelberger, P.: Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul. 5, 43-85(1995)
[34] Juneja, S., Shahabuddin, P.: Rare-event simulation techniques: an introduction and recent advances. Handb. Oper. Res. Manag. Sci. 13, 291-350(2006)
[35] Kalra, N., Paddock, S.M.: Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability? Transp. Res. Part A: Policy Pract. 94, 182-193(2016)
[36] Koopman, P., Wagner, M.: Autonomous vehicle safety: an interdisciplinary challenge. IEEE Intell. Transp. Syst. Mag. 9(1), 90-96(2017)
[37] Koopman, P., Wagner, M.: Toward a framework for highly automated vehicle safety validation. Technical report, SAE Technical Paper (2018)
[38] Koren, M., Alsaif, S., Lee, R., Kochenderfer, M.J.: Adaptive stress testing for autonomous vehicles. In: 2018 IEEE Intelligent Vehicles Symposium (IV), pp. 1-7. IEEE (2018)
[39] L’ecuyer, P., Blanchet, J.H., Tuffin, B., Glynn, P.W.: Asymptotic robustness of estimators in rare-event simulation. ACM Trans. Model. Comput. Simul. 20(1), 1-41(2010)
[40] Nicola, V.F., Nakayama, M.K., Heidelberger, P., Goyal, A.: Fast simulation of highly dependable systems with general failure and repair processes. IEEE Trans. Comput. 42(12), 1440-1452(1993)
[41] Nicola, V.F., Shahabuddin, P., Nakayama, M.K.: Techniques for fast simulation of models of highly dependable systems. IEEE Trans. Reliab. 50(3), 246-264(2001)
[42] NTSB.: Preliminary Report, Highway HWY16FH018(2016)
[43] Nyquist, P.: Moderate deviation principles for importance sampling estimators of risk measures. J. Appl. Probab. 54(2), 490-506(2017)
[44] O’Kelly, M., Sinha, A., Namkoong, H., Tedrake, R., Duchi, J.C.: Scalable end-to-end autonomous vehicle testing via rare-event simulation. In: Advances in Neural Information Processing Systems, pp. 9827-9838(2018)
[45] Rubino, G., Tuffin, B.: Markovian models for dependability analysis, Rare Event Simulation Using Monte Carlo Methods (2009), 125-144
[46] Rubinstein, R.Y., Kroese, D.P.: The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, vol. 133. Springer (2004)
[47] Sadowsky, J.S., Bucklew, J.A.: On large deviations theory and asymptotically efficient monte carlo estimation. IEEE Trans. Inf. Theory 36(3), 579-588(1990)
[48] Tuffin, B. On numerical problems in simulation of highly reliable Markovian systems. In: Proceedings of the 1st International Conference on Quantitative Evaluation of Systems, pp. 156-164. IEEE Computer Society Press (2004)
[49] Tuffin, B., Ridder, A.: Probabilistic bounded relative error for rare event simulation learning techniques. In: Proceedings of the 2012 Winter Simulation Conference, pp. 1-12. IEEE (2012)
[50] Uesato, J., Kumar, A., Szepesvari, C., Erez, T., Ruderman, A., Anderson, K., Heess, N., Kohli, P.: Rigorous agent evaluation: An adversarial approach to uncover catastrophic failures (2018). arXiv:1812.01647
[51] Villén-Altamirano, M., Villén-Altamirano, J.: Restart: a straightforward method for fast simulation of rare events. In: Proceedings of Winter Simulation Conference, pp. 282-289. IEEE (1994)
[52] Webb, S., Rainforth, T., Teh, Y., Mudigonda, P.: A statistical approach to assessing neural network robustness. In: Seventh International Conference on Learning Representations (2019)
[53] Wegener, J., Bühler, O.: Evaluation of different fitness functions for the evolutionary testing of an autonomous parking system. In: Genetic and Evolutionary Computation Conference, pp. 1400-1412. Springer (2004)
[54] Zhang, S., Peng, H., Zhao, D., Tseng, H.E.: Accelerated evaluation of autonomous vehicles in the lane change scenario based on subset simulation technique. In: 201821st International Conference on Intelligent Transportation Systems, pp. 3935-3940. IEEE (2018)
[55] Zhao, D., Huang, X., Peng, H., Lam, H., LeBlanc, D.J.: Accelerated evaluation of automated vehicles in car-following maneuvers. IEEE Trans. Intell. Transp. Syst. 19(3), 733-744(2017)
[56] Zhao, D., Lam, H., Peng, H., Bao, S., LeBlanc, D.J., Nobukawa, K., Pan, C.S.: Accelerated evaluation of automated vehicles safety in lane-change scenarios based on importance sampling techniques. IEEE Trans. Intell. Transp. Syst. 18(3), 595-607(2016)
[57] Zhao, D., Lam, H., Peng, H., Bao, S., LeBlanc, D.J., Nobukawa, K., Pan, C.S.: Accelerated evaluation of automated vehicles safety in lane-change scenarios based on importance sampling techniques. IEEE Trans. Intell. Transp. Syst. 18(3), 595-607(2017)