Improved TD learning reduces batch sampling error.
problem TD learning can be inaccurate in batch settings due to action weighting.
method Introduced PSEC-TD(0) to correct action weighting using importance sampling.
result PSEC-TD(0) produces more accurate value function estimates.
Unified analysis of TD learning using MJLS theory for linear function approximators.
problem Characterizing the exact behaviors of TD learning algorithms with linear function approximators.
method Exploiting connections to Markov jump linear systems (MJLS) theory to analyze TD learning algorithms.
result Closed-form expressions for mean and covariance matrix of TD estimation error at any time step.
Adaptive TD learning reduces bias in policy evaluation by switching between TD and MC methods.
problem Achieving accurate policy evaluation with Temporal Difference (TD) learning in the presence of state-specific uncertainty.
method Adaptive switching between TD and Monte Carlo (MC) methods, using learned confidence intervals to detect and mitigate bias.
result The proposed adaptive algorithm outperforms existing methods in policy evaluation tasks.
TD learning reduces prediction error in Markov chain problems.
problem Estimating value functions in Markov chains with temporal inconsistency.
method Temporal difference learning minimizes temporal inconsistency between successive estimates.
result TD learning can significantly reduce mean-squared error in value estimates.
Study non-parametric value function estimation from a single path.
problem Estimating value function from a single trajectory in Markov reward processes.
method Kernel-based multi-step temporal difference (TD) estimates, including K-step look-ahead TD and TD(λ). result Non-asymptotic guarantees for TD estimates, capturing interactions between mixing time and model mis-specification.
Improved TD learning reduces variance and bias errors.
problem Inefficient optimization variance in TD learning.
method Proposed a mathematically solid analysis of VRTD, showing linear convergence rate and reduced variance and bias errors.
result VRTD converges to a fixed-point solution with reduced variance and bias errors compared to vanilla TD.
The study proposes using TD error for selecting σ in Q(σ, λ).
problem Selecting the value of σ in Q(σ, λ) based on state characteristics.
method TD error as a heuristic for selecting σ.
result TD error can effectively select σ based on state characteristics.
Enhances reinforcement learning uncertainty estimation with a generalized Gaussian error model.
problem Inaccurate error representations and compromised uncertainty estimation in conventional uncertainty-aware TD learning.
method Introduces a novel framework for generalized Gaussian error modeling in deep reinforcement learning, incorporating higher-order moments, particularly kurtosis, to improve uncertainty estimation and mitigation.
result Significant performance gains in policy gradient algorithms with the proposed framework.
Improved TD learning with tail averaging and regularization achieves optimal convergence rates.
problem Convergence analysis of TD learning with linear function approximation.
method Tail-averaging and regularization applied to TD learning algorithm.
result Achieves optimal O(1/t) convergence rate in expectation and with high probability. New TD algorithms stabilize RL tasks by reformulating updates into fixed point equations.
problem TD learning's sensitivity to step size specification.
method Implicit TD algorithms reformulate TD updates into fixed point equations.
result Implicit TD algorithms are more stable and less sensitive to step size.
A new estimator combines bootstrapping and rollout methods in RL.
problem Combining strengths of bootstrapping and rollout methods in RL.
method Subgraph Bellman operators and fixed point solving.
result Upper bound on error approaches optimal TD variance with additional term.
Unified framework for finite-sample RL algorithms using Lyapunov theory.
problem Finite-sample convergence guarantees of asynchronous RL algorithms.
method Reformulate RL algorithms as Markovian SA, develop Lyapunov analysis.
result Mean-square error bounds and convergence for various RL algorithms.
Stochastic differential equation approximation for linear TD(0) under Markovian noise
problem Temporal-difference learning with linear function approximation
method Stochastic differential equation approximation
result Explains the constant-stepsize error floor
New TD method stabilizes average-reward learning.
problem Stability issues in average-reward TD learning.
method Implicit fixed point update for average-reward TD(λ). result Improved numerical stability and broader step-size range.
Paper improves TD(0) convergence rate with LFA, i.i.d. samples, and averaging.
problem Improving convergence rate of TD(0) with linear function approximation.
method Polyak-Juditsky averaging, i.i.d. samples, strong mixing assumption.
result Established a new convergence rate for Mean-Square Error (MSE) of approximated function.
The paper identifies overfitting as the main bottleneck in efficient deep reinforcement learning.
problem Improving sample efficiency in deep reinforcement learning.
method Empirical analysis on DMC tasks to identify overfitting as the main issue and developing a hill-climbing method targeting validation TD error.
result Overfitting is the primary bottleneck in sample-efficient deep RL, and regularization techniques can control this.
TD-Flow improves long-term predictions in agent learning.
problem Cumulative errors in step-by-step inference of future states.
method Leverages flow-matching techniques and a novel Bellman equation to learn accurate geometric horizon models.
result Significantly reduces errors at long horizons compared to prior methods.
Decentralized TD learning converges linearly with linear function approximation.
problem Policy evaluation in fully decentralized multi-agent reinforcement learning.
method Temporal-difference learning with linear function approximation, analyzing i.i.d. and Markovian samples.
result Local estimates converge linearly to the optimum under both i.i.d. and Markovian samples.
Study on distributional TD learning with linear approximations for better return estimation.
problem Estimating the return distribution of a policy in reinforcement learning.
method Finite-sample analysis of distributional TD learning with linear function approximation, using the linear-categorical Bellman equation and exponential stability arguments for products of random matrices.
result Sample complexity of linear distributional TD learning matches that of classic linear TD learning, indicating similar difficulty in estimating return distribution versus its expectation.
Paper analyzes statistical efficiency of TD learning in Hilbert spaces with Freedman's inequality.
problem Statistical efficiency of distributional TD learning in Hilbert spaces.
method Non-parametric distributional TD (NTD) and variance-reduced variants of NTD and CTD.
result Sharp statistical rates achieved through novel Freedman's inequality in Hilbert spaces.
Temporal-difference learning (TD), coupled with neural networks, is among the most fundamental building blocks of deep reinforcement learning. However, due to the nonlinearity in value function approximation, such a coupling leads to nonconvexity and even divergence in optimization. As a result, the global convergence …
Our understanding of reinforcement learning (RL) has been shaped by theoretical and empirical results that were obtained decades ago using tabular representations and linear function approximators. These results suggest that RL methods that use temporal differencing (TD) are superior to direct Monte Carlo estimation (M…
Quantile TD learning outperforms classical TD learning for value estimation.
problem Temporal-difference learning in reinforcement learning.
method Quantile Temporal-Difference Learning (QTD) for policy evaluation.
result QTD offers superior performance to classical TD learning, even in tabular settings.
Improved TD learning for non-i.i.d. Markovian data.
problem Convergence analysis of two time-scale TD learning under Markovian samples.
method Non-asymptotic convergence analysis of two time-scale TD with gradient correction under Markovian data.
result Two time-scale TD can converge as fast as O(log t/(t^(2/3))) under diminishing stepsize.
TDS provides exact samples for conditional distributions in diffusion models.
problem Lack of exact sampling methods for diffusion models.
method Sequential Monte Carlo (SMC) algorithm with twisting technique.
result TDS offers more accurate approximations with fewer particles compared to heuristics.
The paper analyzes the sample complexities for policy evaluation with linear function approximation.
problem Policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes.
method Investigates sample complexities for two policy evaluation algorithms: TD and TDC.
result Establishes high-probability sample complexity bounds for policy evaluation algorithms.
New bounds show linear predictors rarely overfit with certain optimization methods.
problem Bounding test error for linear predictors with stochastic optimization methods.
method Coupling argument for fixed point methods like stochastic and batch mirror descent.
result Locally-adapted rates that depend on predictor properties, not global problem structure.
Study cyber-attacks on RL algorithms, focusing on cost signal manipulation.
problem Adversarial manipulation of cost signals in reinforcement learning.
method Quantitative analysis of TD(λ) and Q-learning algorithms under manipulation. result Bound on approximation error for TD(λ) and convergence properties for Q-learning under stealthy attacks. In this analytical study we derive the optimal unbiased value estimator (MVU) and compare its statistical risk to three well known value estimators: Temporal Difference learning (TD), Monte Carlo estimation (MC) and Least-Squares Temporal Difference Learning (LSTD). We demonstrate that LSTD is equivalent to the MVU if …
Temporal Difference learning or TD(λ) is a fundamental algorithm in the field of reinforcement learning. However, setting TD's λ parameter, which controls the timescale of TD updates, is generally left up to the practitioner. We formalize the λ selection problem as a bias-variance trade-off where the solution is …
Modern deep reinforcement learning methods have departed from the incremental learning required for eligibility traces, rendering the implementation of the λ-return difficult in this context. In particular, off-policy methods that utilize experience replay remain problematic because their random sampling of minibatch…
Actor-critic methods can achieve incredible performance on difficult reinforcement learning problems, but they are also prone to instability. This is partly due to the interaction between the actor and critic during learning, e.g., an inaccurate step taken by one of them might adversely affect the other and destabilize…
While there are convergence guarantees for temporal difference (TD) learning when using linear function approximators, the situation for nonlinear models is far less understood, and divergent examples are known. Here we take a first step towards extending theoretical convergence guarantees to TD learning with nonlinear…
Paper improves TD learning algorithm bounds with linear approx.
problem Sharp bounds for TD method performance in MDPs.
method Polyak-Ruppert averaging, universal step size, refined error bounds, stability of random matrices.
result Near-optimal variance and bias terms achieved.
Study optimal and instance-dependent guarantees for solving linear equations with Markovian data.
problem Approximately solving linear fixed point equations with Markovian data.
method Non-asymptotic bounds and instance-dependent characterizations for stochastic approximation.
result Instance-optimality of the averaged SA estimator and matching upper and lower bounds.
This paper motivates and develops source traces for temporal difference (TD) learning in the tabular setting. Source traces are like eligibility traces, but model potential histories rather than immediate ones. This allows TD errors to be propagated to potential causal states and leads to faster generalization. Source …
Swift-Sarsa combines TD learning with Sarsa to control tasks robustly.
problem Learning effective control policies from noisy signals.
method Combines True Online Sarsa(λ) with step-size optimization and decay. result Swift-Sarsa learns relevant signals without prior knowledge.
Emotions are intimately tied to motivation and the adaptation of behavior, and many animal species show evidence of emotions in their behavior. Therefore, emotions must be related to powerful mechanisms that aid survival, and, emotions must be evolutionary continuous phenomena. How and why did emotions evolve in nature…
In reinforcement learning, temporal difference (TD) is the most direct algorithm to learn the value function of a policy. For large or infinite state spaces, exact representations of the value function are usually not available, and it must be approximated by a function in some parametric family. However, with \emph{no…
Paper analyzes biased stochastic approximation with a novel multistep Lyapunov function.
problem Finite-time analysis of biased stochastic approximation algorithms.
method Developed a multistep Lyapunov function to analyze convergence and error bounds.
result First finite-time error bounds for TD- and Q-learning with linear function approximation.
The true online TD(λ) algorithm has recently been proposed (van Seijen and Sutton, 2014) as a universal replacement for the popular TD(λ) algorithm, in temporal-difference learning and reinforcement learning. True online TD(λ) has better theoretical properties than conventional TD(λ), and the expectation is that it als…
Temporal difference learning (TD) is a simple iterative algorithm used to estimate the value function corresponding to a given policy in a Markov decision process. Although TD is one of the most widely used algorithms in reinforcement learning, its theoretical analysis has proved challenging and few guarantees on its s…
New algorithms improve distributional TD learning with linear approximations.
problem Estimating return distributions in reinforcement learning.
method Fine-grained analysis of linear-categorical Bellman equation, variance reduction techniques.
result Tight sample complexity bounds for distributional TD learning with linear approximations.
RO-TD learns sparse value functions efficiently.
problem Learning sparse value functions efficiently.
method RO-TD integrates off-policy convergent gradient TD methods and online convex regularization.
result RO-TD learns sparse value functions with low computational complexity.
We solve POMDPs by approximating them as finite-state MDPs.
problem Computational challenges in learning optimal policies for POMDPs.
method Transform POMDP into a Superstate MDP, apply TD-learning and policy optimization.
result Finite-time bounds on TD-learning error for non-Markovian dynamics.
Unified framework for PE and TD methods in continuous time and space.
problem Policy evaluation and TD learning in continuous settings.
method Martingale characterization for designing PE algorithms.
result Convergent time-discretized algorithms converge to continuous-time counterparts.
Introduces TDRC to balance TD's ease and soundness.
problem TD learning's instability and divergence issues.
method Gradient Temporal-Difference Learning with Regularized Corrections (TDRC).
result TDRC performs as well as TD when TD works, but is sound in divergent cases.
A critical and challenging problem in reinforcement learning is how to learn the state-action value function from the experience replay buffer and simultaneously keep sample efficiency and faster convergence to a high quality solution. In prior works, transitions are uniformly sampled at random from the replay buffer o…