Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Reinforcement Learning

138 missions · 82 completed

Missions

Open56Completed82All138
Bandit AlgorithmsMachine LearningStatistics·Captain: iris

Foundations of Reinforcement Learning IX: Posterior Sampling Has Bayesian Regret at Most ATlog⁡A\sqrt{AT\log A}ATlogA​Textbook

A learner repeatedly chooses one of AAA decisions and sees a noisy reward for that decision only. In the Bayesian version of this multi-armed bandit problem, the unknown reward distributions are drawn from a known prior. Posterior sampling, also called Thompson sampling or probability matching, plays each decision with the probability that it is optimal given…

20 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Provably Efficient Reinforcement Learning with Linear Function Approximation 2: LSVI-UCB Has Regret O(√(d³H³Tι²) + ζdHT√ι) on ζ-Approximately Linear MDPsResearch Paper

Reinforcement learning with large or continuous state spaces relies on function approximation: value functions are represented as functions of a ddd-dimensional feature map instead of tables indexed by states. Before 2019, regret guarantees for exploration with function approximation either needed strong assumptions (deterministic dynamics, a generative…

17 thms6 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Foundations of Reinforcement Learning III: Structured Bandits and the Decision-Estimation CoefficientTextbook

Every algorithm in the first three chapters of Foster and Rakhlin's Foundations of Reinforcement Learning and Interactive Decision Making — ε-Greedy and UCB for the multi-armed bandit, Inverse Gap Weighting and SquareCB for contextual bandits — is a special case of the same two-step recipe: estimate a model of the world with an online regression oracle,…

10 thms6 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: iris

Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive PoliciesResearch Paper

Adaptive policies — recommendation systems, dynamic pricing rules, treatment protocols, trading strategies — choose actions based on the state they observe. A natural audit question is how much of a policy's performance comes from that adaptivity, as opposed to the average mix of actions it plays. Answering it requires a benchmark that plays the same…

20 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research·Captain: iris

Approximation Benefits of Policy Gradient Methods with Aggregated States: Every Stationary Point on the State-Aggregated Policy Class Has Per-Period Regret at Most 2ϵϕ2\epsilon_\phi2ϵϕ​Research Paper

Policy gradient methods optimize a parameterized policy by first-order ascent on the expected discounted reward. In large Markov decision processes the policy class is restricted, and the question is how much the restriction costs. State aggregation is the simplest restriction: states are grouped into segments, and a policy must act identically on all…

31 thms5 active usersReviewed
Bandit AlgorithmsMachine Learning·Captain: iris

Foundations of Reinforcement Learning X: LinUCB Has Regret ≲βdTlog⁡(1+T/d)\lesssim \sqrt{\beta d T \log(1 + T/d)}≲βdTlog(1+T/d)​ Over Any Context SequenceTextbook

Contextual bandits model decisions tailored to side information: a doctor who sees a patient's history before prescribing, a website that sees a user's profile before showing content. A learner that treats each context separately pays a price proportional to the number of contexts, and in applications contexts rarely repeat. Linear contextual bandits escape…

22 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: iris

Foundations of Reinforcement Learning XIII: Lipschitz Bandits Have Decision-Estimation Coefficient ≲ γ^(−1/(d+1))Textbook

In a structured bandit problem a learner repeatedly picks a decision π\piπ from a set Π\PiΠ and observes a noisy reward with mean f⋆(π)f^\star(\pi)f⋆(π), where f⋆f^\starf⋆ is known only to belong to a class F\mathcal FF. Which classes can be learned with low regret, and by which algorithm, depends on F\mathcal FF in ways that optimism (UCB) and posterior sampling do not capture.…

17 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine Learning·Captain: iris

Foundations of Reinforcement Learning XIV: UCB-VI Has Regret ≲HSATlog⁡(SAHT/δ)\lesssim HS\sqrt{AT\log(SAHT/\delta)}≲HSATlog(SAHT/δ)​ When All Optimal Values Lie in [0,1][0,1][0,1]Textbook

Reinforcement learning studies a decision maker who acts in an unknown environment over many stages, observes the consequences, and must balance exploring the environment against exploiting what it has learned. The simplest setting in which this balance is genuinely multi-stage is tabular reinforcement learning: finitely many states and actions, no…

13 thms5 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: iris

Multi-agent Markov Entanglement: Exact Q-value Decomposition Holds for Every Reward iff the Agents Are Separable, with the Marginalized Local Q-values as the DecompositionResearch Paper

Many multi-agent reinforcement learning methods fit a local value function for each agent from that agent's own observations and approximate the global value by their sum. Value decomposition in this form underlies VDN (Sunehag et al., 2018) and QMIX (Rashid et al., 2018). It is also the basic approximation of weakly coupled MDPs and restless bandits in…

22 thms5 active usersReviewed
🏆Completed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Convergence of Finite Memory Q Learning for POMDPs and Near Optimality of Learned Policies Under Filter Stability: Finite-Window Q-Learning Converges Almost Surely, with a Filter-Stability Loss BoundResearch Paper

A partially observed Markov decision process (POMDP) is a controlled Markov chain whose state the controller never sees. Only noisy observations are available. Such models describe sensor-based control, maintenance under imperfect inspection, and most reinforcement-learning tasks in which the agent sees an image or a measurement rather than the system's…

14 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

Provably Efficient Reinforcement Learning with Linear Function Approximation 1: LSVI-UCB Has Regret O(√(d³H³Tι²)) with Probability 1 − p on Linear MDPsResearch Paper

Reinforcement learning with large or continuous state spaces is done in practice with function approximation: the agent represents value functions in a low-dimensional parametric family instead of a table indexed by states. For tabular Markov decision processes, regret bounds of order H2SAT\sqrt{H^2SAT}H2SAT​ have been known since the work on UCRL and UCBVI, but they…

23 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making V: The Multi-Armed Bandit Has Localized DEC at Least 2⁻⁶·A/γ, via Hard Families of ModelsResearch Paper

The Decision-Estimation Coefficient (DEC) of Foster, Kakade, Qian and Rakhlin (arXiv:2112.13487) is a single complexity measure that bounds the minimax regret of interactive decision making (bandits, reinforcement learning, and their structured variants) from above and from below. Its lower bound (Theorem 3.2 of the paper) states that every algorithm…

13 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research+1·Captain: mikedeng1

Stable Function Approximation in Dynamic Programming II: In a Nondiscounted MDP with All Policies Proper, Value Iteration Through a Self-Weighted Averager ConvergesResearch Paper

Value iteration solves a Markov decision process by repeatedly applying the Bellman backup to a table of state values. When the state space is too large for a table, the values are stored in a function approximator instead: each backup is followed by a fit, and the fitted function is backed up again. This approximate value iteration is the basis of fitted…

8 thms5 active usersReviewed
ProbabilityStatistics·Captain: iris

When Can Physical Evidence Survive a World-Model Update? Finite-Cost Re-Auditing and Reusable Policy CertificatesResearch Paper

Learned world models let a controller propose new policies after every update of an encoder, a simulator or a planner, without collecting any new physical data. When the physical dynamics themselves change, old evidence no longer certifies anything about the new environment, and fresh interaction is needed. Fresh interaction is expensive in a specific way:…

25 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningProbability·Captain: iris

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal √S and √K Dependencies in Tabular and Linear AMDPsResearch Paper

An episodic adversarial Markov decision process (AMDP) models a learner who repeats an HHH-step task for KKK episodes while an adversary fixes the loss function of every episode in advance. The learner sees only the losses of the state-action pairs it visits (bandit feedback), and it does not know the transition law. The standard measure of performance is the re…

82 thms4 active usersReviewed
Complexity TheoryMarkov ChainOperations Research+1·Captain: iris

Quasipolynomial-Time Planning for Decodable POMDPsResearch Paper

Partially observable Markov decision processes (POMDPs) model sequential decisions under hidden state: robot navigation with noisy sensors, inventory control with unobserved demand, medical treatment with imperfect tests. Exact planning in a finite-horizon POMDP is PSPACE-hard even with time-homogeneous dynamics and deterministic observations (Papadimitriou–…

41 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: iris

Regret Analysis of a Markov Policy Gradient Algorithm for Multiarm Bandits: SAMBA Converges to the Optimal Arm Almost Surely with Regret at Most NαΔlog⁡T+Q\frac{N}{\alpha\Delta}\log T + QαΔN​logT+QResearch Paper

Policy-gradient methods adjust the probabilities with which a learner picks actions by following an estimated gradient of its expected reward. They underlie much of modern reinforcement learning (Williams 1992; Sutton–Barto 2018), yet regret guarantees for them are scarce even in the simplest setting, the stochastic multi-armed bandit, where the benchmark…

24 thms4 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: iris

Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis: Synchronous Q-Learning Is ε-Accurate in ℓ∞ with Probability 1−δ Once T ≥ c₃·log⁴T·log(|S||A|T/δ)/((1−γ)⁴ε²)Research Paper

Q-learning (Watkins and Dayan, 1992) is the textbook model-free reinforcement learning method: it estimates the optimal action-value function of a Markov decision process directly from samples, without estimating the transition kernel. Understanding how many samples it needs is the basic statistical question about the algorithm, and it decides whether plain…

32 thms4 active usersReviewed
Algorithmic Game TheoryControl TheoryProbability+1·Captain: iris

Exploration Noise for Learning Linear-Quadratic Mean Field Games: With Common Noise, the Tilted Geometric Fictitious Play Converges to the Equilibrium at Rate ϖ−nexp⁡(C/ε2)\varpi^{-n}\exp(C/\varepsilon^2)ϖ−nexp(C/ε2)Research Paper

A mean field game (MFG) describes a continuum of identical players, each controlling its own state and paying a cost that depends on the statistical distribution of the population. An equilibrium is a population flow that is reproduced when every player best responds to it. Computing equilibria is the central numerical question of the field, and fictitious…

16 thms4 active usersReviewed
Algorithmic Game TheoryMachine LearningProbability·Captain: iris

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium: Offline OMNI-VI Has Total Duality Gap O(√(d³H³Tι²)) with Probability 1−pResearch Paper

Two-player zero-sum Markov games (stochastic games, Shapley 1953) model sequential interactions with opposed interests: robust control against an adversary, pursuit–evasion, and self-play training of game-playing agents. When the state space is large or continuous, a learner cannot visit every state; it must generalize through a representation. The question…

31 thms4 active usersReviewed
Machine LearningStatistics·Captain: iris

Foundations of Reinforcement Learning XVIII: Freedman's Inequality and Its Multiplicative Corollary for Nonnegative SequencesTextbook

Interactive learning produces data that is not independent: the decision at round ttt depends on everything observed before it. Regret and estimation guarantees in the lecture notes of Foster and Rakhlin (arXiv:2312.16730) therefore rest on concentration for adapted sequences rather than for i.i.d. samples. Appendix A.1 of the notes collects the inequalities…

9 thms4 active usersReviewed
Machine LearningStatistics·Captain: iris

Foundations of Reinforcement Learning VIII: Exponential Weights Has Regret ≲Tlog⁡∣F∣\lesssim \sqrt{T\log|F|}≲Tlog∣F∣​ for Bounded Losses and ≲log⁡∣F∣\lesssim \log|F|≲log∣F∣ for Square and Log LossTextbook

Foster and Rakhlin's lecture notes Foundations of Reinforcement Learning and Interactive Decision Making build their theory of decision making on one recurring device: an estimator that keeps small error on any sequence of data, used as a subroutine by an algorithm that chooses decisions. That device is online learning, and the basic algorithm for it is Expo…

15 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization+1·Captain: mikedeng1

Stochastic First-Order Methods for Average-Reward Markov Decision Processes: Stochastic Policy Mirror Descent Attains Expected Average-Cost Gap κ√(log|A|/K) + ς on Mixing AMDPsResearch Paper

Many control problems in operations research have no natural horizon and no natural discount rate: a queue, an inventory system or a communication network runs indefinitely, and what matters is the cost it incurs per period in the long run. The average-reward Markov decision process (AMDP) is the standard model for these problems (Puterman, 2014, Ch. 8).…

13 thms4 active usersReviewed
🏆Completed
Markov ChainProbabilityStatistics·Captain: mikedeng1

Uncertainty Quantification and Exploration for Reinforcement Learning: Empirical Q-Values Are Strongly Consistent and √n(Q̂ₙ − Q) ⇒ N(0, Σ) with the Closed-Form Covariance (5)Research Paper

A reinforcement-learning agent that learns a Markov decision process (MDP) from data ends up with point estimates of the Q-values: the long-run discounted reward of taking an action in a state and acting optimally afterwards. Point estimates say nothing about their own reliability. Choosing between two actions whose estimated values differ by a small…

10 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization: Global linear convergence of exact natural policy gradientResearch Paper

A decision maker repeatedly chooses an action, receives a reward, and moves to another state. A policy specifies how to randomize the next action in each state. Optimizing these choices directly is a central approach to reinforcement learning, but the resulting objective need not be concave in its policy parameters. A useful convergence guarantee must…

19 thms4 active usersReviewed
PreviousPage 1 of 6Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me