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
Machine LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making II: Every Algorithm Has Expected Regret at Least (1/6)·dec_γ(M^∞_ε̄γ(M̄), M̄)·T, the Localized DEC Lower BoundResearch Paper

In interactive decision making, an algorithm chooses actions while learning which model governs its observations. A low-regret guarantee for one algorithm does not by itself say whether every algorithm could do better. The Decision-Estimation Coefficient (DEC) was introduced to express the cost of choosing useful decisions while distinguishing plausible…

12 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingProbability·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 5: The Effective Concentrability Coefficient Is at Most 1/min ρ(s), ‖dη_π*/dρ‖∞, or C/cResearch Paper

Policy gradient methods optimize a parameterized policy for a Markov decision process by local search on its expected cost. The objective is nonconvex, so local search can in principle stall at a poor stationary point. Bhandari and Russo, Global Optimality Guarantees for Policy Gradient Methods show that for a broad family of control problems this does not…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimization·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 4: In Finite-Horizon Problems with a Non-Stationary Policy Class Containing an Optimal Policy, Every Stationary Point Is OptimalResearch Paper

Policy gradient methods optimize a parameterized policy by gradient descent on its expected total cost. They are a staple of reinforcement learning and of simulation-based optimization in operations research, but the objective is nonconvex in the policy parameters, and the standard theory guarantees convergence only to a stationary point. J. Bhandari and D.…

10 thms2 active usersReviewed
Dynamic ProgrammingOptimization·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 3: Under Closure up to Inherent Bellman Error ε, Every Stationary Point Is Within κε/(1−γ) of OptimalResearch Paper

Policy gradient methods search for a policy by changing a finite vector of parameters. The method can reach a stationary point of its objective without finding an optimal policy: a small change in the available parameters might not represent the policy improvement that the underlying control problem calls for. Bhandari and Russo identify a condition on the…

10 thms2 active usersReviewed
Dynamic ProgrammingOptimization·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 1: If the Policy Class Is Closed Under Policy Improvement, Every Stationary Point of the Policy Gradient Objective Is Globally OptimalResearch Paper

Policy gradient methods optimize a parameterized policy for a Markov decision process by running gradient descent on its expected cost. They underlie most large-scale reinforcement learning, from robotics to game playing, and are also natural in operations research, where structured policy classes (linear feedback, base-stock levels, thresholds) are…

9 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimization·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 6: In the KL-Regularized Finite MDP, a Regularized-Optimal Policy Is Within λ(1 + log(1 + c/λ)) of OptimalResearch Paper

Policy gradient methods for Markov decision processes are frequently run on a regularized objective rather than on the cost of interest: a convex penalty on the action distribution is added to every single-period cost. Regularization smooths the problem, makes optimal policies strictly stochastic, and keeps iterates away from the boundary of the probability…

13 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningProbability·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning VI: In a Deterministic MDP an Algorithm Acts T-Step Optimally at All but NAT TimestepsTextbook

A reinforcement-learning agent that does not know its environment has to act and learn at once. Each step spent gathering information about unfamiliar states is a step not spent collecting reward, and an agent that only exploits what it already knows may never find better behaviour. Chapter 8 of Kakade's thesis (Kakade 2003) turns this trade-off into a…

14 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning IV: Advantages at Most ε/T under μ Make a Policy ε + T‖d_{π′,s₀} − μ‖₁ Close to Every Policy of the ClassTextbook

Planning in a Markov decision process with a large or infinite state space cannot visit every state. The trajectory tree method of Kearns, Mansour and Ng (2000) finds a near-best policy in a class Π\PiΠ with a number of generative-model calls independent of the state space, but exponential in the horizon TTT. Chapter 6 of S. M. Kakade's PhD thesis, On the…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning II: The Gradient of the Normalized Discounted Value Is the Sum over Actions of ∇π·Q under the Discounted Future State DistributionTextbook

Policy gradient methods search a parameterized family of stochastic policies π(a∣s,θ)\pi(a\mid s,\theta)π(a∣s,θ), θ∈Rk\theta\in\mathbb R^kθ∈Rk, by following the gradient of the policy's performance. They are the standard tool when the state space is too large for tabular dynamic programming and when a compact policy class (a neural network, a linear softmax) is easier to represent…

9 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOptimization·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning I: Approximate Policy Iteration with Max-Norm Evaluation Error ε Is Eventually Within 2ε/(1−γ)² of OptimalTextbook

Most practical reinforcement-learning methods do not compute value functions exactly. They alternate between estimating a value function from data, usually with a parametric approximator, and acting greedily with respect to that estimate. Approximate value iteration and approximate policy iteration are the two classical schemes of this kind, and their error…

13 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Bounded-parameter Markov Decision Processes 1: The Optimistic and Pessimistic Optimal Interval Value Functions Satisfy Bellman-like EquationsResearch Paper

A Markov decision process is specified by numbers: transition probabilities and rewards. In practice these numbers are estimated from data, elicited from experts, or produced by aggregating the states of a larger model, and in each case what is actually known is a range for each parameter rather than its value. Givan, Leach and Dean (Artificial…

12 thms2 active usersReviewed
Dynamic ProgrammingMachine LearningMarkov Chain+1·Captain: mikedeng1

An Analysis of Temporal-Difference Learning with Function Approximation 1: Linear TD(λ) Converges with Probability 1 to the Fixed Point of ΠT^(λ), with Error ≤ ‖ΠJ* − J*‖_D/(1 − α(1−λ)/(1−αλ))Research Paper

Temporal-difference learning, TD(λ\lambdaλ), is the basic algorithm of reinforcement learning for estimating the expected discounted cost of a Markov chain from observed transitions (Sutton, 1988). On large or infinite state spaces it is run with a linear function approximator: the cost-to-go is represented as a weighted sum of KKK fixed basis functions, and…

13 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 3: Softmax Policy Gradient Ascent with Step Size η ≤ (1−γ)³/8 Converges to the Optimal ValuesResearch Paper

Policy gradient methods optimize a parameterized policy of a Markov decision process by gradient ascent on its expected discounted return. They underlie much of modern reinforcement learning (REINFORCE, actor–critic methods, TRPO, PPO), yet the objective θ↦Vπθ(μ)\theta \mapsto V^{\pi_\theta}(\mu)θ↦Vπθ​(μ) is non-concave in the parameters, and until recently even the most…

22 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Learning in Structured MDPs with Convex Cost Functions: Improved Regret Bounds for Inventory Management: Base-Stock Values from Any Two Starting States Differ by at Most 36 max(h,p)LxResearch Paper

The lost-sales inventory problem with lead times is a basic model of operations management. A retailer reviews one product's stock each period and places an order that arrives LLL periods later. Demand that cannot be met from stock on hand is lost, and the retailer pays a holding cost hhh per unit left on the shelf and a penalty ppp per unit of lost demand. The…

9 thms2 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: mikedeng1

Linear Least-Squares Algorithms for Temporal Difference Learning II: Probability-One Convergence of LS TD on Ergodic Markov ChainsResearch Paper

Temporal-difference (TD) learning estimates the value function of a Markov chain — the expected discounted sum of future rewards from each state — from a single stream of observed transitions, without knowing the transition probabilities. With a linear function approximator the value of state xxx is represented as ϕx′θ\phi_x'\thetaϕx′​θ for a feature vector ϕx\phi_xϕx​ and…

8 thms2 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning II: High-Probability Regret Bound for UCBVI with a Bernstein–Freedman BonusResearch Paper

An agent can learn to act in an unknown environment by repeatedly running a finite episode, observing the states reached after its actions, and updating its model of the environment. The agent must trade off rewards in the current episode against information that may improve later decisions. A regret bound measures the cumulative value lost relative to an…

13 thms2 active usersReviewed
🏆Completed
Linear algebraMachine LearningMarkov Chain·Captain: mikedeng1

Reinforcement Learning: An Introduction VIII: The TD Fixed Point of Linear Semi-gradient TD(0) and Its Error BoundTextbook

Reinforcement learning methods estimate the value function vπv_\pivπ​ of a policy π\piπ: the expected discounted sum of future rewards from each state. When the state space is large, vπv_\pivπ​ cannot be stored as a table and is approximated by a parametrized function. The most studied case is linear function approximation, where each state sss carries a feature vector …

11 thms2 active usersReviewed
🏆Completed
Linear algebraMachine Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction XI: Dutch Traces and the Equivalence of Forward and Backward Views in Monte Carlo LearningTextbook

Eligibility traces are one of the basic mechanisms of reinforcement learning. A trace is a short-term memory vector ztz_tzt​ with one component per weight. It records which components contributed to recent value estimates, so that an error observed now can be credited to the right components without storing the past. Chapter 12 of Sutton and Barto's Reinforcement…

11 thms2 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning I: High-Probability Regret Bound for UCBVI with a Chernoff–Hoeffding BonusResearch Paper

An agent learning to control an unknown environment must balance rewards it can collect now against information that improves later decisions. In a finite Markov decision process (MDP), every action changes the distribution of the next state, so a mistaken transition estimate can affect decisions many steps later. Regret measures this loss against a policy…

9 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOptimization·Captain: mikedeng1

Reinforcement Learning: An Introduction I: The Gradient Bandit Algorithm Is Stochastic Gradient AscentTextbook

The multi-armed bandit is the simplest setting in which a learner must trade off exploiting what it knows against exploring what it does not: one situation, kkk actions, and a reward drawn from an unknown distribution each time an action is taken. Chapter 2 of Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) uses it to…

11 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research·Captain: mikedeng1

Approximately Optimal Approximate Reinforcement Learning II: Near-Optimality of a Policy with Small Policy AdvantageResearch Paper

Approximate policy iteration and policy-gradient methods stop when they can no longer find a direction of improvement. Kakade and Langford (ICML 2002) asked what such a stopping point guarantees. Their algorithm, conservative policy iteration, halts at a policy π\piπ for which no policy can improve much on π\piπ as measured under a restart distribution μ\muμ; the…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research+1·Captain: mikedeng1

Approximately Optimal Approximate Reinforcement Learning I: Conservative Policy Iteration Improves Monotonically and Returns a Near-Greedy PolicyResearch Paper

Approximate policy iteration and policy gradient methods are the two classical families of reinforcement learning algorithms that work with approximate, sampled information instead of an exact model. Kakade and Langford (ICML 2002) observed that neither family answers three basic questions: is there a performance measure that is guaranteed to improve at…

14 thms2 active usersReviewed
Dynamical SystemsProbabilityStochastic Systems·Captain: mikedeng1

The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning I: Stability and Almost-Sure Convergence under Tapering StepsizesResearch Paper

Stochastic approximation is the family of recursive algorithms that locate a zero of a function observed only through noisy evaluations. It goes back to Robbins and Monro (1951) and today underlies stochastic gradient descent, temporal-difference learning, Q-learning and actor–critic methods in reinforcement learning, and models of learning by boundedly…

17 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Foundations of Reinforcement Learning II: Contextual Bandits and Inverse Gap WeightingTextbook

Decision-making problems rarely present the same fixed choice twice. A doctor prescribing a treatment sees each patient's medical history and symptoms before deciding; a website choosing which article to show sees the visitor's profile first. The multi-armed bandit model — where the learner repeatedly picks from a fixed set of arms with no side information…

5 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

Foundations of Reinforcement Learning I: Multi-Armed Bandits and the UCB AlgorithmTextbook

The multi-armed bandit is the simplest model of sequential decision-making under partial feedback: a learner repeatedly picks one of finitely many options and observes a reward only for the option chosen, never for the alternatives. It formalizes problems ranging from clinical trial design (which treatment to offer a patient) to online advertising (which ad…

7 thms2 active usersReviewed
PreviousPage 5 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