acceptodds
Under review as a conference paper at ICLR 2027

ABRL: A Source-Aligned Lean 4 Proof Atlas for Bandit and Reinforcement Learning Theory

Abstract

Understanding a new bandit or reinforcement-learning result requires identifying which arguments are inherited, which assumptions change, and which proof obligations remain unmatched. We present BanditRLlib, a source-aligned Lean 4 library organized as a proof atlas for this comparison, within the ABRL project. The library formalizes a classical bandit backbone, five end-to-end setting extensions, and a known-reward Hoeffding UCB-VI development, pairs each source-facing theorem with a plain-language proof and its exact Lean declaration, and exposes two complementary views: a compiler-derived dependency graph showing what is formally reused, and a map of conceptual correspondences across settings recorded separately from checked reuse. Two results illustrate the atlas. Heavy-tailed and causal bandits reuse the same two concentration lemmas, called by name, while sharing neither policy nor criterion. A countable-node kernel adapter for hierarchical optimistic optimization removes an extraneous measurability premise introduced by our initial formalization, without changing the source's scope, and a finite certificate shows that a printed pull-count coefficient in the heavy-tailed source fails, with an amended bound proved for the unchanged policy. Source correspondence is reviewed and recorded for every source-facing statement through source-blind reconstruction and explicit discrepancy records. The result is a checked reference frame for reading new work against classical theory: what is inherited, what is recombined, and what remains to be proved. The library, its records, and its tools are available at https://anonymous.4open.science/r/peer-review-artifact-2027.

Primary area:
reinforcement learning
Keywords:
Automatic Proof System, Lean Library, Bandit, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_9pE7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents BanditRLlib, a Lean 4 library and proof atlas for bandit and reinforcement-learning theory, together with an interface for exploring theorem statements, assumptions, proofs, and dependencies. By connecting existing results to explicit assumptions, readable proofs, exact formal declarations, and compiler-derived dependencies, it aims to help researchers distinguish inherited proof components from setting-specific arguments and identify unresolved proof obligations.

Critical strengths
  • This paper introduces BanditRLlib, a Lean 4 library that formalizes classical bandit algorithms, five additional bandit settings, and finite-horizon reinforcement learning. It connects formal proofs with their original sources, explicitly documenting assumptions, modifications, and incomplete results.

  • The paper develops a framework combining compiler-derived dependency graphs, conceptual connections between proof techniques, and an assumption-indexed theorem database. It distinguishes verified proof reuse from potential connections and unresolved proof obligations, demonstrating shared concentration lemmas across heavy-tailed and causal bandits.

  • Through formal verification, authors identifies an incorrect finite-time coefficient in a published heavy-tailed bandit regret bound and proves an amended guarantee. It also removes an unnecessary measurability assumption introduced during the formalization of hierarchical optimistic optimization (HOO), restoring the original theorem's scope.

Critical weaknesses
  • While the paper presents a technically substantial formalization effort, its novelty appears somewhat limited. The proposed framework primarily integrates existing ideas, such as Lean-based formalization, proof dependency graphs, and reusable mathematical libraries. Moreover, the demonstrated cross-setting reuse mainly involves standard foundational lemmas rather than more sophisticated algorithmic analyses. It would be helpful for the authors to clarify the key methodological advances over existing formalization frameworks and what fundamentally new capabilities ABRL provides.

  • Although the library includes a formalization of Tsallis-entropy FTRL, the paper does not demonstrate a general reusable framework for FTRL-based regret analyses, particularly those involving adaptive learning rates, time-varying regularizers, or stability-penalty decompositions. This limits the demonstrated applicability of the proposed proof atlas to a broader class of modern online learning algorithms.

  • The paper does not provide user studies or quantitative experiments demonstrating that ABRL improves researchers' understanding of mathematical proofs, facilitates theorem reuse, or reduces formalization effort compared to existing tools.

Questions for authors

The source-alignment procedure relies on author-supervised AI agents rather than independent expert verification. How can the authors ensure that the formalized statements faithfully represent the original theorems, particularly regarding implicit assumptions, quantifier order, and performance criteria?

Reviewer_QWHROpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this work, the authors propose ABRL which is a Lean 4 proof library for bandit and RL theory where the goal is to make existing results easier to verify and compare to. The main contributions are the BanditRLlib which formalizes bandit algorithms and their lower bounds (in addition to finite horizon UCB-VI regret analysis), and a method for combining proof dependencies from compilers. Finally, the authors also introduce comparing statements against sources. They also validated their method on Lean proofs that are machine checked, documented source comparisons and examples across different bandit settings.

Critical strengths

The paper is well written and in particular the authors focus on giving a very concrete formalization of results across bandit and RL theory. For example, they also give discrepancies in published arguments and give a counterexample to the heavy tailed bandit coefficient etc. Moreover, the authors properly show how the atlas is useful for understanding similarities and relatedness in results across settings (and one example of this is the concentration lemmas being reused in heavy tailed and causal bandit settings.

Critical weaknesses

One weakness is that the authors did not (or just minimally) comment and evaluate whether the researchers can use the system to better understand proofs more efficiently, especially since the initial motivation of the atlas is to make results easier to understand and compare. Given that the atlas is supposed to be a contribution in the Lean library, I believe that having some sort of evaluation is very important for understanding the impact of the work Moreover, the reuse across settings was just done on a very small and selected number of results, and that there are many conceptual connections that are still unverified. It is unclear to me how reliable the proposed framework will be able to generalize to new results with quite different proof structures.

Questions for authors
  • Can the authors comment on or perform some evaluation that shows that the atlas is actually improving the users’ ability to understand and extend the proofs relative to the existing Lean environments? This is one of the weaknesses I mentioned before.
  • How generalizable is the source alignment procedure when we apply it to new results/settings?
Reviewer_QxSbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces BanditRLlib, a source-aligned Lean 4 formal library and navigable proof atlas for MABs and RL theory built on Mathlib. Rather than treating formalization solely as isolated theorem verification, the library organizes results around a four-part reusable mathematical spine and pairs each source-facing theorem with a plain-language proof, explicit assumption comparisons, and its Lean 4 declaration. The library covers a textbook bandit backbone, five complete research extensions, a known-reward Hoeffding UCB-VI development for tabular finite-horizon MDPs, and three partial frontier routes. It exposes a compiler-derived Lean Graph of actual declaration reuse alongside a separate dashed Mechanism Hypergraph of conceptual analogies with explicit failure boundaries and an assumption-indexed BanditRLwiki/Frontier. Statement fidelity to original sources is audited via a blind semantic round-trip protocol and recorded through categorized discrepancy records, highlighted by a machine-checked counterexample refuting the printed 32log⁡T+532\log T + 5 pull-count coefficient and a countable-node discrete-σ\sigma-algebra kernel adapter removing an extraneous global measurability assumption from HOO.

Critical strengths
  • This is the first systematic initiative to build a source-aligned formal proof atlas specifically tailored to RL theory. The library turns informal claims of "following standard techniques" into exact compiler-checked dependency edges.
  • Formalizing a paper is only scientifically meaningful if the formal theorem faithfully matches the informal source's model, quantifier order, and algorithm. The paper enforces this through blind reconstruction and a transparent five-way taxonomy of source discrepancies.
Critical weaknesses
  • Lean verifies that a formal proof establishes its formal statement; correspondence with the cited source is assessed separately. The semantic round-trip roles were filled by isolated AI instances under author supervision, and the paper reports no independent expert reassessment.
  • The graph and atlas are implemented, but their effects on reader understanding and development effort have not been evaluated.
Questions for authors

The paper records (a) a confidence width used against its displayed monotonicity in the delayed-bandit route of Schlisselberg et al. (2025); (b) unboundedness of the dual supremum R(X)R(X) when XX has a nonzero component orthogonal to the atom span in Zeng & Honorio (2025); and (c) inconsistent conditioning between q≥cq\ge c and q<cq<c in an appendix step of Theorem 4 of Baudry et al. (2025). What progress has been made toward resolving these obligations? For any proposed repair, which theorem assumptions or conclusions would change, and which could remain unchanged?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.