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
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Correcting for Interference in Experiments: A Case Study at Douyin: In Absorbing MDPs the Differences-in-Qs Estimator Has Bias at Most T_abs³ · r_max · δ²Research Paper

A creator-side experiment on a short-video platform may assign treatment to individual videos while measuring outcomes over a viewer's whole session. A treated video can alter what the viewer watches next, so its effect may persist beyond the immediate reward. The paper studies this form of interference using a Markov decision process and asks how well data…

10 thms4 active usersReviewed
Machine LearningStatistics·Captain: mikedeng1

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model 2: The Conservative Model-Based Policy Is ε-Optimal w.p. 1−δ at the Sample Size of Theorem 1Research Paper

Reinforcement learning with a generative model (a simulator that returns an independent next state for any queried state–action pair) is the standard setting for measuring how many samples are needed to plan in an unknown Markov decision process. The simplest algorithm is model-based planning: query each pair NNN times, build the empirical transition kernel,…

19 thms4 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds II: Along Any h, the Empirical Transition Vector Is within 2√(log(n/ρ)Σγᵢcᵢ²/n) + 3D log(2/ρ)/n of the TruthResearch Paper

Model-based reinforcement learning algorithms for Markov decision processes estimate each transition distribution Ps,aP_{s,a}Ps,a​ from the transitions they have observed out of the state–action pair (s,a)(s,a)(s,a). Their regret analyses then need to know how far the empirical distribution p^\hat pp^​ can be from the true one ppp. The standard tool is an ℓ1\ell_1ℓ1​ bound on p^−p\hat p-pp^​−p,…

7 thms4 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds I: An Extended MDP with δ-Optimistic Samples for Hitting Times Has Diameter at Most D/(1−δ)Research Paper

Regret bounds for reinforcement learning in a single, non-episodic Markov decision process (MDP) are stated in terms of the diameter DDD of the MDP: the worst expected time needed to travel between two states when the travel policy is chosen well. UCRL2 (Jaksch, Ortner and Auer, 2010) achieves regret O~(DSAT)\tilde O(DS\sqrt{AT})O~(DSAT​), against a lower bound of …

6 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research·Captain: mikedeng1

Stable Function Approximation in Dynamic Programming I: In a Discounted Finite MDP, Value Iteration Through an Averager Converges to V₀ with ‖V₀ − V*‖ ≤ 2γε/(1 − γ)Research Paper

Value iteration computes the optimal value function of a Markov decision process by applying the dynamic programming backup to every state until the values stop changing. When the state space is too large for a lookup table, practitioners replace the table by a function approximator: after each backup, the new values are computed only at a sample of states…

8 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 5: Natural Policy Gradient with Softmax Policies Is Within log|A|/(ηT) + 1/((1−γ)²T) of OptimalResearch Paper

Policy gradient methods optimize a parameterized policy directly by gradient ascent on its expected discounted return. They underlie most practical reinforcement-learning systems, yet for a long time their convergence was understood only locally: the objective θ↦Vπθ(ρ)\theta\mapsto V^{\pi_\theta}(\rho)θ↦Vπθ​(ρ) is not concave, and plain gradient ascent can stall on…

16 thms4 active usersReviewed
🏆Completed
Linear algebraMachine LearningOptimization·Captain: mikedeng1

Reinforcement Learning: An Introduction X: Off-policy Divergence and the Gradient of the Projected Bellman ErrorTextbook

Off-policy learning estimates the value function of a target policy π\piπ from data generated by a different behavior policy bbb. It is how an agent learns about a greedy policy while exploring, and how many policies can be evaluated from one stream of experience. Combined with linear function approximation and bootstrapping (updating an estimate toward other…

14 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Reinforcement Learning: An Introduction V: Off-policy Prediction by Importance SamplingTextbook

Reinforcement learning methods must explore in order to find good behaviour, yet the quantity they usually want to evaluate is the value of a different, often deterministic, policy. Off-policy prediction separates the two roles: episodes are generated by a behaviour policy bbb, and the goal is the value function vπv_\pivπ​ of a target policy π\piπ. Almost every…

14 thms4 active usersReviewed
🏆Completed
Experimental DesignOperations ResearchProbability+1·Captain: Shuze Chen

Treatment Locality in A/B TestingResearch Paper

Modern A/B tests must infer lifetime treatment effects — e.g. customer lifetime value under a new feature — from short-horizon experiment data. Chen, Simchi-Levi and Wang (arXiv:2407.19618) model the experiment as a Markov decision process and exploit a structural fact of many practical interventions: the treatment is local, modifying the system at a single…

42 thms4 active users
🏆Completed
Convex OptimizationDynamic ProgrammingOptimization·Captain: iris

On the Convex Formulations of Robust Markov Decision Processes: The Fixed Point of the Entropy-Regularized Robust Bellman Operator Is log_b of the Unique Optimum of a Convex ProgramResearch Paper

A Markov decision process (MDP) models sequential decisions under uncertainty: in each state an agent picks an action, collects a reward and moves to a random next state. Its optimal value function is the fixed point of the Bellman operator, and since the 1960s it has also been the optimum of a linear program over value functions (Puterman, Markov Decision…

14 thms3 active usersReviewed
Dynamic ProgrammingMachine LearningOperations Research·Captain: iris

Adaptive Discretization in Online Reinforcement Learning: AdaMB and AdaQL Have Regret Scaling with the Zooming DimensionResearch Paper

Reinforcement learning in operations problems (inventory control, ambulance routing, pricing, queue admission) often has continuous state and action spaces. A fixed grid of mesh ϵ\epsilonϵ wastes samples on regions where nothing is learned, and its regret grows with the ambient dimension of S×A\mathcal S\times\mathcal AS×A. Adaptive discretization refines a…

37 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchStatistics·Captain: iris

Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games: VI-LCB-Game Returns an ε-Nash Policy Pair with Probability 1−δ from c₁·C⋆_clipped·S(A+B)·log(N/δ)/((1−γ)³ε²) Offline SamplesResearch Paper

Many sequential decision problems with two adversaries are modelled as zero-sum Markov games (Shapley, 1953; Littman, 1994): two players act simultaneously in a shared state, one maximizes and the other minimizes the same discounted reward. In applications such as games, security and robust control, interaction with the system is expensive or unsafe, and…

19 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: iris

Quantile Markov Decision Processes: Backward Dynamic Programming over State and Quantile Level Computes the Optimal Quantile of the Cumulative RewardResearch Paper

A classical Markov decision process (MDP) chooses a policy that maximizes the expected cumulative reward. In many applications the expectation is the wrong summary: a clinician choosing when to start a treatment, or an investor facing ruin, cares about the bad outcomes, and two policies with equal means can have very different lower tails. A natural…

11 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningStatistics·Captain: iris

Foundations of Reinforcement Learning XII: E2D Regret Is at Most the Decision-Estimation Coefficient Times T Plus γ·EstSqTextbook

In a structured bandit a learner repeatedly picks a decision πt\pi^tπt from a possibly huge or continuous set Π\PiΠ and observes a noisy reward with mean f⋆(πt)f^\star(\pi^t)f⋆(πt), where f⋆f^\starf⋆ belongs to a known class F\mathcal FF of functions Π→R\Pi\to\mathbb RΠ→R. The optimal regret depends on F\mathcal FF in ways that are hard to predict: optimism (UCB) and posterior sampling…

27 thms3 active usersReviewed
Machine LearningStatistics·Captain: iris

Foundations of Reinforcement Learning VII: Empirical Risk Minimization over a Finite Class Has Expected Excess Risk ≲ √(log|F|/T), and ≲ log|F|/T for Well-Specified Square LossTextbook

Interactive decision making rests on estimation: an agent that acts well must fit a model to past data and rely on it for data not yet seen. The lecture notes of Foster and Rakhlin (arXiv:2312.16730) therefore open with statistical learning, the passive problem in which the learner does not influence the data. It isolates generalization and function…

20 thms3 active usersReviewed
Captain: Shuze Chen

Is Q-learning Provably Efficient?: Q-learning with UCB-Bernstein achieves near-optimal regretResearch Paper

Q-learning maintains estimates of the reward obtainable from each state and action. This makes it a natural method when an agent can interact with an environment but cannot ask a simulator for arbitrary transitions. The central question is whether these local value updates can support a quantitative guarantee on the reward lost during exploration. Jin,…

17 thms3 active usersReviewed
Markov ChainProbabilityStatistics·Captain: mikedeng1

Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity: Under Geometric Mixing the Empirical Estimator Is ε-Accurate After Order dT/ε² Samples, and This Rate Is MinimaxResearch Paper

Offline reinforcement learning and off-policy evaluation start from a single logged trajectory of a controlled system. The policy that generated the log is often unknown, history-dependent and not stationary. Model-based methods first estimate the transition probabilities of the system from this log, then plan or evaluate policies in the estimated model (Aga…

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

A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation: Projected TD(0) Under Markov Chain Sampling Converges at Mixing-Time-Scaled RatesResearch Paper

Temporal-difference (TD) learning is the basic algorithm of reinforcement learning for estimating the value function of a fixed policy from a single stream of experience. With a linear function approximation Vθ(s)=ϕ(s)⊤θV_\theta(s)=\phi(s)^\top\thetaVθ​(s)=ϕ(s)⊤θ, TD(0) is the evaluation step inside many policy-iteration and actor–critic methods, and its behaviour governs how much…

10 thms3 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Nonstationary Reinforcement Learning: The Blessing of (More) Optimism III: Under Uniform One-Step Reachability ζ, the Un-widened Confidence Region Contains an MDP of Diameter at Most 1/ζResearch Paper

Reinforcement learning in a changing environment has a difficulty that is absent from a fixed Markov decision process: transition data gathered earlier may describe a different system from the one the decision maker currently faces. A learning algorithm therefore estimates transitions from a recent window of observations. The estimate comes with a confidence…

8 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainOperations Research·Captain: mikedeng1

Nonstationary Reinforcement Learning: The Blessing of (More) Optimism II: Per-Step Dynamic Regret of SWUCRL2-CW When the Widened Confidence Region Contains an MDP of Diameter at Most DResearch Paper

A reinforcement-learning agent chooses actions while learning how those actions affect future states. In a stationary model, observations collected long ago remain relevant to the current transition law. In a nonstationary Markov decision process, rewards and transition probabilities may change at each round. Old observations can then bias an estimate even…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationMarkov ChainOperations Research·Captain: mikedeng1

Nonstationary Reinforcement Learning: The Blessing of (More) Optimism I: No Policy Earns More Than the Sum of Per-Step Optimal Gains Plus 4(D_max+1)√((B_r+2D_max B_p)T)Research Paper

Reinforcement learning in a changing environment needs a benchmark that remains meaningful when the transition law and rewards vary from round to round. For a stationary Markov decision process (MDP), the optimal long-run average reward is a standard benchmark. In a nonstationary MDP, summing those stationary optima across rounds is convenient, but it need…

11 thms3 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees: Single-Loop ML-IRL Policy and Reward Iterates Converge at Explicit Finite-Time RatesResearch Paper

Structural estimation of Markov decision processes recovers the parameters of an agent's reward from observed behavior, under the hypothesis that the agent acts optimally in a known dynamic environment. In econometrics this is the dynamic discrete choice model of Rust (Rust 1987); in artificial intelligence it is maximum-likelihood inverse reinforcement…

18 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research·Captain: mikedeng1

The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation: Error Bound for Least-Squares Policy Iteration with LookaheadResearch Paper

Approximate policy iteration is the template behind most practical reinforcement-learning systems for large state spaces: alternate between choosing a policy that looks good under the current value estimate and estimating the value of that policy, with errors in both steps. Game-playing systems such as AlphaZero add two ingredients to this template: a…

19 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Corruption-Robust Exploration in Episodic Reinforcement Learning II: Uniformly Action-Eliminating Algorithms Suffer Expected Regret at Least K/8 for K ≤ A^H/4Research Paper

In stochastic multi-armed bandits, a robust way to explore is action elimination: keep confidence intervals for every arm, discard an arm once its upper confidence bound falls below another arm's lower confidence bound, and sample uniformly among the arms that survive. Uniform sampling is what makes the first corruption-robust bandit algorithm work (Lykouris…

10 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making VII: Policy-Cover Inverse Gap Weighting Certifies dec_γ ≤ 95H³SA/γ for Tabular Reinforcement LearningResearch Paper

In episodic reinforcement learning, an agent learns the rewards and dynamics of a system while choosing actions that determine which states it observes. A bound on the number of states and actions alone does not prescribe how to explore: a policy can be valuable because it earns reward, because it visits an uncertain state-action pair, or both. Foster,…

16 thms3 active usersReviewed
PreviousPage 2 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