Alphabeta MathAverage-reward regret and UCRL2
About this page
Pipeline-generated
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
✓ 1 result · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
- Binary Operations, Monoids, Groups and Subgroups
- Cosets, Index and Lagrange's Theorem
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Normal Subgroups and Quotient Groups
- Polynomial Rings, the Division Algorithm and Roots
- Rings, Subrings, Integral Domains and Fields
- Simple Field Extensions and the Construction of the Complex Numbers
Bayesian Computational Statistics
Linear Algebra
Machine Learning Algorithms
Mathematical Statistics
Measure Theory
- Measurable Functions and Simple Approximation
- Measures and Their Basic Properties
- Outer Measure and the Caratheodory Extension Theorem
- Pointwise Extended-Real Function Products
- Product Measures and the Fubini Tonelli Theorems
- Sigma Algebras and Borel Sets
- Signed and Complex Measures Hahn and Jordan
- The Lebesgue Integral and the Convergence Theorems
- The Lᵖ Spaces Holder Minkowski and Riesz Fischer
- The Radon Nikodym Theorem and Lebesgue Decomposition
Probability
- Conditional Distributions and Regular Conditional Probability
- Conditional Expectation
- Discrete Time Martingales
- Infinite Product Measures and Kolmogorov Extension
- Markov Kernels and Markov Chains
- Martingale Inequalities and Convergence
- Probability Spaces Random Variables and Expectation
- Stationary Markov Chains and Ergodic Limits
Real Analysis
- Absolute and Conditional Convergence; Rearrangement; Products
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Convexity
- Countability and Uncountability
- Darboux, L'Hôpital, and Taylor's Theorem
- Foundations of the Real Numbers for Analysis
- Limits of Real Functions
- limsup, liminf, and Subsequential Limits
- Monotone Functions, Discontinuities, and Continuity Sets
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- Power Series and Real-Analytic Functions
- Properties of the Integral and the Working FTC
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sequences and Series of Functions; Uniform Convergence
- Series: Convergence and the Nonnegative Tests
- Suprema and Infima
- The Derivative and the Mean Value Theorems
- The Exponential Function
- The Integral Logarithm and the Equivalence of Its Characterisations
- The Logarithm and General Powers
- The Riemann Integral: Definition and Integrability
- Topology of ℝ
Set Theory
2 · Logical flowchart
3 · Items
Lemma
Almost-additive sequences have a normalized limit
Definition
Finite MDP with bounded real rewards
Algorithm
Extended value iteration for a confidence set
Definition
Communicating MDP and diameter
Lemma
Adaptive MDP visits admit fixed sample tapes
Lemma
Termination of extended value iteration under communicating assumptions
Lemma
Uniform empirical reward and transition confidence bounds
Theorem
Communicating MDPs have a common optimal average reward
Algorithm
UCRL2 for finite communicating MDPs
Definition
Average reward and pathwise regret
Theorem
UCRL2 high-probability pathwise regret bound
Theorem
Expected regret lower bound for communicating MDPs
Sources
- Sébastien Gouëzel, Theory Fekete, Archive of Formal Proofs, lemma almost_additive_converges
- Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences
- Sacha Friedli and Yvan Velenik, Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction
- Thomas Jaksch, Ronald Ortner, and Peter Auer, Near-optimal Regret Bounds for Reinforcement Learning
- Christos Dimitrakakis and Ronald Ortner, Decision Making Under Uncertainty and Reinforcement Learning: Theory and Algorithms
- Martin L. Puterman and Timothy C. Y. Chan, Markov Decision Processes and Reinforcement Learning, Chapter 7: Average Reward Models