# Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees

arXiv: https://arxiv.org/abs/2610.14790 · HTML: https://mlsanity.com/paper/2610.14790/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 25 references that are in the map.
- First posted on arXiv 10 Oct 2026.

## Builds on (most cited first, 14 of 14)

- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Do LLM Agents Have Regret? A Case Study in Online Learning and Games](https://mlsanity.com/paper/2403.16843/) (2024)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards](https://mlsanity.com/paper/2004.06248/) (2020)
- [Efficient tracking of a growing number of experts](https://mlsanity.com/paper/1708.09811/) (2017)
- [Ballooning Multi-Armed Bandits](https://mlsanity.com/paper/2001.10055/) (2020)
- [Understanding the Role of Feedback in Online Learning with Switching Costs](https://mlsanity.com/paper/2306.09588/) (2023)
- [Near-optimal Per-Action Regret Bounds for Sleeping Bandits](https://mlsanity.com/paper/2403.01315/) (2024)
- [Online Decision Making with Generative Action Sets](https://mlsanity.com/paper/2509.25777/) (2025)

## Abstract (arXiv)

Reflective language agents reuse feedback and memory to adapt across tasks without updating model weights. However, existing guarantees for policy selection and action generation do not by themselves establish when local reflection yields long-term performance guarantees for the complete agent under resource constraints. In this paper, we address this gap by deriving sufficient conditions for sublinear counterfactual regret from local generation and deployment guarantees, while retaining the native controller. Specifically, we establish a resource-sensitive transfer that bounds full-state deployment discrepancies along actual execution paths and preserves the own-history laws of both learner and comparator. Besides, local generation reliability yields a cumulative generation opportunity bound, linking policy acquisition to long-term performance through an explicit quality, coverage, and hard-budget tradeoff. To verify these guarantees, we formalize the conditional proof chain for all thirteen numbered theoretical results in Lean, including a native instance with repeated policy growth and imperfect validation.