Loop Estimator for Discounted Values in Markov Reward Processes
- URL: http://arxiv.org/abs/2002.06299v3
- Date: Wed, 3 Mar 2021 05:05:36 GMT
- Title: Loop Estimator for Discounted Values in Markov Reward Processes
- Abstract summary: A policy evaluation step estimates the value of states with samples from a Markov reward process induced by following a Markov policy.
We propose a simple and efficient estimator called loop estimator that exploits the regenerative structure of Markov reward processes.
In preliminary numerical experiments, the loop estimator outperforms model-free methods, such as TD(k) and is competitive with the model-based estimator.
- Score: 19.011189395046014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: At the working heart of policy iteration algorithms commonly used and studied
in the discounted setting of reinforcement learning, the policy evaluation step
estimates the value of states with samples from a Markov reward process induced
by following a Markov policy in a Markov decision process. We propose a simple
and efficient estimator called loop estimator that exploits the regenerative
structure of Markov reward processes without explicitly estimating a full
model. Our method enjoys a space complexity of $O(1)$ when estimating the value
of a single positive recurrent state $s$ unlike TD with $O(S)$ or model-based
methods with $O\left(S^2\right)$. Moreover, the regenerative structure enables
us to show, without relying on the generative model approach, that the
estimator has an instance-dependent convergence rate of
$\widetilde{O}\left(\sqrt{\tau_s/T}\right)$ over steps $T$ on a single sample
path, where $\tau_s$ is the maximal expected hitting time to state $s$. In
preliminary numerical experiments, the loop estimator outperforms model-free
methods, such as TD(k), and is competitive with the model-based estimator.
Related papers
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
arXiv Detail & Related papers (2026-08-06T19:49:48Z) - CollabEval: Statistically Efficient Collaborative Model Evaluation via Matrix Completion [65.53153291902454]
Collaborative Evaluation (CollabEval) is a simple, effective, and principled method for exploiting dependencies between historical runs of different models on the same tasks to improve statistical efficiency.<n>We build a low-rank approximation of the score matrix, and use the reconstructed values to guarantee unbiased estimates of the true evaluation metric mean.<n>We find that CollabEval substantially reduces the mean confidence interval size, and the mean squared error of the point estimate, compared to baseline methods at the same annotation budget.
arXiv Detail & Related papers (2026-07-06T13:22:04Z) - $V_0$: A Generalist Value Model for Any Policy at State Zero [80.7505802128501]
Policy methods rely on a baseline to measure the relative advantage of an action.<n>This baseline is typically estimated by a Value Model (Critic) often as large as the policy model itself.<n>We propose a Generalist Value Model capable of estimating the expected performance of any model on unseen prompts.
arXiv Detail & Related papers (2026-02-03T14:35:23Z) - Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
We tackle average-reward infinite-horizon POMDPs with an unknown transition model.
We present a novel and simple estimator that overcomes this barrier.
arXiv Detail & Related papers (2025-01-30T22:29:41Z) - Markov Chain Variance Estimation: A Stochastic Approximation Approach [14.883782513177094]
We consider the problem of estimating the variance of a function defined on a Markov chain, an important step for statistical inference of the stationary mean.
We design a novel recursive estimator that requires $O(1)$ at each step, does not require any historical samples or any prior knowledge of run-length, and has optimal $O(frac1n) rate of convergence for the mean-squared error (MSE) with provable finite sample guarantees.
arXiv Detail & Related papers (2024-09-09T15:42:28Z) - Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm [6.481009996429766]
inverse reinforcement learning (IRL) aims to recover a reward for which the expert is optimal.
This work proposes a model-free algorithm to solve the entropy-regularized IRL problem.
arXiv Detail & Related papers (2024-03-25T14:54:42Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples.
We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
arXiv Detail & Related papers (2023-10-21T18:48:45Z) - Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
We show that a model-free stage-based Q-learning algorithm can enjoy the same optimality in the $H$ dependence as model-based algorithms.
Our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions.
arXiv Detail & Related papers (2023-08-17T08:34:58Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
We show a non-asymptotic bound of the order $t_mathrmmix tfracdn$ on the squared error of the last iterate of a standard scheme.
We derive corollaries of these results for policy evaluation with Markov noise.
arXiv Detail & Related papers (2021-12-23T18:47:50Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning.
The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences.
The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
arXiv Detail & Related papers (2021-10-09T21:13:48Z) - A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
We present a sharp analysis of model-based self-play algorithms for multi-agent Markov games.
We design an algorithm -- Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games.
We further adapt our analysis to designing a provably efficient task-agnostic algorithm for zero-sum Markov games.
arXiv Detail & Related papers (2020-10-04T15:27:39Z) - Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
We present a unified framework for approximately solving infinite-horizon Markov decision processes (MDPs) given a linear model.
We achieve these results through a more general mirror descent framework for solving bigenerative saddle-point problems with simplex and box domains.
arXiv Detail & Related papers (2020-08-28T17:58:40Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP)
We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
arXiv Detail & Related papers (2020-06-04T17:51:00Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.