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
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making VI: Posterior Sampling Bounds the Dual DEC of Tabular Reinforcement Learning by 26H²SA/γResearch Paper

In episodic reinforcement learning, an agent acts repeatedly in an unknown system and must learn which policy earns the largest expected reward. Even when states and actions are finite, the agent's choices change which data it observes. Foster, Kakade, Qian, and Rakhlin use the decision-estimation coefficient (DEC) to connect this information constraint to…

12 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making IV: Log-Loss Regret Controls Hellinger Estimation Error, Est_H ≤ Reg_KL + 2 log(1/δ) with Probability 1−δResearch Paper

Interactive decision methods often need an estimate of an unknown outcome law after each round. A learner can be good at decisions only if its model of the observations is accurate where future decisions will sample. Foster, Kakade, Qian and Rakhlin measure this accuracy by a cumulative squared Hellinger distance and use it in their regret bounds for…

12 thms3 active users
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making IX: Posterior Sampling Bounds the Square-Loss DEC by 2Δ + 24·θ·log²(γ)/γ, θ the Disagreement CoefficientResearch Paper

In a structured bandit problem a learner repeatedly chooses a decision π\piπ from a set Π\PiΠ and observes a noisy reward whose mean fM(π)f^M(\pi)fM(π) is an unknown function from a known class FM\mathcal{F}_{\mathcal{M}}FM​. Classical analyses of such problems measure the complexity of FM\mathcal{F}_{\mathcal{M}}FM​ by the eluder dimension (Russo and Van Roy, 2013; 2014) or the st…

13 thms3 active users
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making VIII: Linear Bandits on the Unit Ball Have Localized DEC at Least d/(12γ)Research Paper

In a linear bandit a learner repeatedly chooses a decision π\piπ from a set Π⊆Rd\Pi \subseteq \mathbb{R}^dΠ⊆Rd and observes a noisy reward whose mean is ⟨θ⋆,π⟩\langle \theta^\star, \pi\rangle⟨θ⋆,π⟩ for an unknown parameter θ⋆\theta^\starθ⋆. It is the standard model for sequential decisions with many correlated actions, such as ad placement, routing and recommendation, and its…

11 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimization·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 2: Under Closure, a (c, µ)-Gradient-Dominated Policy Iteration Objective Makes ℓ (κc/(1−γ), κµ/(1−γ))-Gradient DominatedResearch Paper

Policy gradient methods optimize a parameterized control policy by gradient descent on its long-run cost. They underlie much of modern reinforcement learning, from REINFORCE and actor-critic methods to trust-region and proximal policy optimization, and they are used in operations problems such as inventory control and optimal stopping. Their objective is…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine Learning·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning III: Non-Stationary Approximate Policy Iteration Is Within 2T Times the Regression Error Averaged over Any Competitor's State-Time DistributionTextbook

Approximate dynamic programming replaces the exact value functions of a Markov decision process by approximations, typically produced by a regression algorithm. The classical guarantees for the resulting policies are stated in the max norm: if every state-action value is estimated to within ε\varepsilonε uniformly over the state space, the greedy policy loses…

19 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOptimization·Captain: mikedeng1

On the Sample Complexity of Reinforcement Learning V: Exact Conservative Policy Iteration Improves at Every Update and Halts within 8H²/ε² Updates with Future Advantages at Most ε/HTextbook

Policy iteration replaces the current policy by the greedy policy with respect to its state-action values. With exact values this improves the policy at every state. When the improvement step is only approximate, or is restricted to a class of policies, a greedy replacement can make the policy worse, and the resulting error bounds are stated in max norm…

18 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Bounded-parameter Markov Decision Processes 2: Interval Policy Evaluation Converges to the Interval Value Function of Every PolicyResearch Paper

A Markov decision process (MDP) is evaluated by solving a linear fixed-point equation built from its transition probabilities. In practice those probabilities are rarely known exactly: they are estimated from data, elicited from experts, or obtained by aggregating the states of a larger model, and each estimate comes with an error band. Givan, Leach and…

10 thms3 active usersReviewed
Machine LearningMarkov ChainProbability·Captain: mikedeng1

An Analysis of Temporal-Difference Learning with Function Approximation 2: For Every Sampling Distribution q and 5/6 < α < 1, Off-Line q-Sampled TD(0) Can Diverge in ExpectationResearch Paper

Temporal-difference learning estimates the future cost of a system from observed transitions. In a Markov model, a state has a distribution of possible successors and each transition carries a cost. An agent may approximate the future cost with a small number of basis functions rather than store one number per state. This is useful when the state set is…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Planning and Acting in Partially Observable Stochastic Domains: The Witness Theorem, a Set of Useful Policy Trees Is Incomplete iff Replacing One Subtree Improves on It at Some Belief StateResearch Paper

A partially observable Markov decision process (POMDP) models an agent that acts in a stochastic world whose state it cannot see directly. The agent sees only noisy observations. POMDPs are the standard model for planning under uncertainty in robotics, dialogue systems, medical decision making and machine maintenance. The exact finite-horizon theory goes…

11 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 4: Log-Barrier-Regularized Softmax Policy Gradient Is ε-Optimal After 320|S|²|A|²D∞²/((1−γ)⁶ε²) StepsResearch Paper

Policy gradient methods search directly over parameterized policies of a Markov decision process (MDP) by gradient ascent on the expected discounted reward. They are among the most widely used methods in reinforcement learning, yet the value Vπθ(ρ)V^{\pi_\theta}(\rho)Vπθ​(ρ) is a nonconcave function of the parameters, and until recently little was known about whether,…

20 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Asynchronous Stochastic Approximation and Q-Learning 2: Asynchronous Stochastic Approximation with Outdated Information Converges with Probability 1 Under a Weighted Maximum Norm ContractionResearch Paper

Many iterative algorithms update only part of a vector at a time. In a parallel implementation, one processor may read a value written several rounds earlier by another processor. Random observations also perturb each update. John N. Tsitsiklis's 1994 paper gives conditions under which such an asynchronous stochastic iteration still converges. The paper…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Asynchronous Stochastic Approximation and Q-Learning 1: Bounded Asynchronous Stochastic Approximation Iterates Converge with Probability 1 to the Unique Fixed Point of a Monotone Continuous MapResearch Paper

Q-learning (Watkins, 1989) learns the optimal action values of a Markov decision problem from sampled transitions, without a model of the transition probabilities. At each step only one state–action pair is updated, with a noisy estimate of the Bellman operator evaluated at possibly outdated values of the other pairs. Watkins and Dayan (1992) gave a first…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningProbability·Captain: mikedeng1

Technical Note: Q-Learning: With Bounded Rewards and Learning Rates with Σα = ∞, Σα² < ∞ at Every State–Action Pair, Tabular Q-Learning Converges to Q* with Probability 1Research Paper

Q-learning is the basic model-free algorithm of reinforcement learning: an agent that does not know the transition probabilities or the reward structure of a controlled Markov process learns the optimal action values from experience alone, by a one-line update applied after every observed transition. It was introduced in C. J. C. H. Watkins' 1989 thesis,…

8 thms3 active usersReviewed
🏆Completed
Linear algebraMachine LearningMarkov Chain·Captain: mikedeng1

Learning to Predict by the Methods of Temporal Differences: Linear TD(0) Converges in Expected Value to the Ideal Predictions on Absorbing Markov ChainsResearch Paper

Temporal-difference (TD) methods learn to predict an eventual outcome from the differences between successive predictions rather than from the difference between each prediction and the final outcome. Sutton's 1988 paper Learning to predict by the methods of temporal differences introduced the TD(λ\lambdaλ) family and gave the first convergence proof for a TD…

24 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 6: Agnostic Q-NPG for Log-Linear Policies, Bounded by Transfer Error, Excess Risk and Condition NumberResearch Paper

Policy gradient methods optimize a decision rule by changing the parameters that determine its action probabilities. In reinforcement learning, the objective is the expected total reward collected over time. Once a policy is restricted to a feature-based class, the best policy may be less effective than the unrestricted optimum. A useful guarantee must…

16 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 2: On a Chain MDP All Low-Order Derivatives of the Value Are Exponentially Small at Suboptimal PoliciesResearch Paper

Policy gradient methods adjust a policy by following derivatives of its expected reward. A common expectation is that a small gradient indicates a policy close to optimal. For discounted Markov decision processes, that interpretation can fail when a policy rarely reaches the states where reward is available. Agarwal, Kakade, Lee, and Mahajan study this…

12 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 1: Projected Gradient Ascent on the Simplex Is ε-Optimal After 64γ|S||A|D∞²/((1−γ)⁶ε²) IterationsResearch Paper

Policy gradient methods optimize a parameterized policy of a Markov decision process by gradient ascent on its expected discounted return. They are among the most widely used methods in reinforcement learning, from REINFORCE (Williams 1992) and the policy gradient theorem to natural policy gradient and trust-region methods. The objective is not concave in…

18 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 2: The Greedy Policy of the R2 Optimal Value Is the Unique Optimal R2 PolicyResearch Paper

A robust Markov decision process (robust MDP) evaluates a policy against the worst transition kernel and reward in an uncertainty set around a nominal model (P0,r0)(P_0, r_0)(P0​,r0​). It is the standard model for planning when the dynamics are estimated from data (Iyengar 2005; Nilim and El Ghaoui 2005; Wiesemann, Kuhn and Rustem 2013). Its Bellman update contains an…

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

Linear Least-Squares Algorithms for Temporal Difference Learning I: Probability-One Convergence of Trial-Based LS TD on Absorbing Markov ChainsResearch Paper

Temporal-difference learning estimates the value of a policy from observed state transitions and rewards. In a finite Markov decision process, fixing a policy produces a Markov chain, so policy evaluation becomes the task of estimating the expected return from each state. Bradtke and Barto's 1996 paper introduced a least-squares temporal-difference method, L…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningMarkov Chain·Captain: mikedeng1

Reinforcement Learning: An Introduction IX: Average Reward and the Futility of Discounting in Continuing ProblemsTextbook

Reinforcement learning formulates control as maximizing reward accumulated over time. For continuing tasks, where interaction never terminates, the standard textbook objective is the discounted return with a discount rate γ<1\gamma < 1γ<1. Chapter 10 of Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018), argues that once values…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 1: The Robust Value Function Is the Optimum of a Policy- and Value-Regularized Convex ProgramResearch Paper

A Markov decision process (MDP) is solved for one model of its dynamics and rewards, but in practice that model is estimated from data, and a policy that is optimal for the estimate can perform poorly on the true system (Mannor et al., 2007). Robust MDPs address this by evaluating a policy against the worst model in an uncertainty set U\mathcal UU (Iyengar,…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction IV: Policy Iteration for ε-Soft PoliciesTextbook

Policy iteration alternates two steps: evaluate the current policy, then replace it by a policy that is greedy with respect to the evaluated action values. The policy improvement theorem guarantees that each greedy step does not make the policy worse, and that the process stops only at an optimal policy. When the action values are estimated from experience…

11 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainOptimization·Captain: mikedeng1

Reinforcement Learning: An Introduction XII: The Policy Gradient TheoremTextbook

Policy gradient methods learn a parameterized policy π(a∣s,θ)\pi(a \mid s, \theta)π(a∣s,θ) directly, by stochastic gradient ascent on a scalar performance measure J(θ)J(\theta)J(θ), instead of deriving the policy from learned action values. They are how reinforcement learning handles continuous action spaces, stochastic optimal policies and prior knowledge built into the policy's…

14 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov Chain·Captain: mikedeng1

Reinforcement Learning: An Introduction VII: The Error Reduction Property of n-step ReturnsTextbook

Temporal-difference (TD) learning estimates the value of a policy by moving a current estimate toward a target built from observed rewards and from the estimate itself. Chapter 7 of Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) interpolates between the two extreme targets of the preceding chapters: the one-step TD…

10 thms3 active usersReviewed
PreviousPage 3 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