Learning Successor States and Goal-Dependent Values: A Mathematical Viewpoint

• URL: http://arxiv.org/abs/2101.07123v1
• Date: Mon, 18 Jan 2021 15:33:26 GMT
• Title: Learning Successor States and Goal-Dependent Values: A Mathematical Viewpoint
• Abstract summary: We derive a temporal difference algorithm for successor state and goal-dependent value function learning. We provide finite-variance estimators even in continuous environments. We have fully understood fixed points to long-range dependencies.
• Score: 18.70146287117806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In reinforcement learning, temporal difference-based algorithms can be sample-inefficient: for instance, with sparse rewards, no learning occurs until a reward is observed. This can be remedied by learning richer objects, such as a model of the environment, or successor states. Successor states model the expected future state occupancy from any given state for a given policy and are related to goal-dependent value functions, which learn how to reach arbitrary states. We formally derive the temporal difference algorithm for successor state and goal-dependent value function learning, either for discrete or for continuous environments with function approximation. Especially, we provide finite-variance estimators even in continuous environments, where the reward for exactly reaching a goal state becomes infinitely sparse. Successor states satisfy more than just the Bellman equation: a backward Bellman operator and a Bellman-Newton (BN) operator encode path compositionality in the environment. The BN operator is akin to second-order gradient descent methods and provides the true update of the value function when acquiring more observations, with explicit tabular bounds. In the tabular case and with infinitesimal learning rates, mixing the usual and backward Bellman operators provably improves eigenvalues for asymptotic convergence, and the asymptotic convergence of the BN operator is provably better than TD, with a rate independent from the environment. However, the BN method is more complex and less robust to sampling noise. Finally, a forward-backward (FB) finite-rank parameterization of successor states enjoys reduced variance and improved samplability, provides a direct model of the value function, has fully understood fixed points corresponding to long-range dependencies, approximates the BN method, and provides two canonical representations of states as a byproduct.

Related papers

• Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL [8.809468023364703]
  Design of robust reinforcement learning algorithms poses fundamental challenges.<n>We propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional.<n>To learn the fixed point of this approximate equation, we propose Mean-Variance Approximation (MVSA)
  arXiv  Detail & Related papers  (2026-05-08T19:24:28Z)
• Operator-Guided Invariance Learning for Continuous Reinforcement Learning [8.820825533010543]
  Reinforcement learning (RL) with continuous time and state/action spaces is often data-intensive and brittle under nuisance variability and shift.<n>We propose textbfVPSD-RL (Value-Preserving Structure Discovery for Reinforcement Learning)<n>It models continuous RL as a controlled diffusion with value-preserving mappings defined through Lie-group actions and associated pullback operators.<n>We show that a value-preserving structure exists exactly when pulling back the value function and pushing forward actions commute with the controlled generator and reward functional.
  arXiv  Detail & Related papers  (2026-05-07T16:18:37Z)
• Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity [16.835098688159004]
  Tail-end risk measures such as static conditional value-at-risk (CVaR) are used in safety-critical applications to prevent rare, yet catastrophic events.<n>We develop risk-averse value and model-free Q-learning algorithms that rely on discretized augmented states.<n> Empirical results demonstrate that our algorithms successfully learn CVaR-sensitive policies and achieve effective performance-safety trade-offs.
  arXiv  Detail & Related papers  (2026-02-03T17:39:45Z)
• Beyond Softmax: A Natural Parameterization for Categorical Random Variables [61.709831225296305]
  We introduce the $textitcatnat$ function, a function composed of a sequence of hierarchical binary splits.<n>A rich set of experiments show that the proposed function improves the learning efficiency and yields models characterized by consistently higher test performance.
  arXiv  Detail & Related papers  (2025-09-29T12:55:50Z)
• Bayesian Optimization for Robust Identification of Ornstein-Uhlenbeck Model [4.0148499400442095]
  This paper deals with the identification of the derivation Ornstein-Uhlenbeck (OU) process error model. We put forth a sample-efficient global optimization approach based on the Bayesian optimization framework.
  arXiv  Detail & Related papers  (2025-03-09T01:38:21Z)
• Tractable and Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation [8.378137704007038]
  We present a regret analysis for distributional reinforcement learning with general value function approximation. Our theoretical results show that approximating the infinite-dimensional return distribution with a finite number of moment functionals is the only method to learn the statistical information unbiasedly.
  arXiv  Detail & Related papers  (2024-07-31T00:43:51Z)
• Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation [47.08004958269403]
  We prove a weaker convergence condition for bootstrapped value estimation in certain cases, even with off-policy data. We extend our results to learning with truncated trajectories, showing that convergence is achievable for all tasks with minor modifications.
  arXiv  Detail & Related papers  (2024-05-31T17:36:16Z)
• Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
  We consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation. We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2024-01-26T20:45:40Z)
• Value-Distributional Model-Based Reinforcement Learning [59.758009422067]
  Quantifying uncertainty about a policy's long-term performance is important to solve sequential decision-making tasks. We study the problem from a model-based Bayesian reinforcement learning perspective. We propose Epistemic Quantile-Regression (EQR), a model-based algorithm that learns a value distribution function.
  arXiv  Detail & Related papers  (2023-08-12T14:59:19Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection [136.4014229319618]
  We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first derive a necessary condition on the representation, called universally spanning optimal features (UNISOFT), to achieve constant regret in any MDP with linear reward function.
  arXiv  Detail & Related papers  (2021-10-27T22:07:08Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)
• Robust Value Iteration for Continuous Control Tasks [99.00362538261972]
  When transferring a control policy from simulation to a physical system, the policy needs to be robust to variations in the dynamics to perform well. We present Robust Fitted Value Iteration, which uses dynamic programming to compute the optimal value function on the compact state domain. We show that robust value is more robust compared to deep reinforcement learning algorithm and the non-robust version of the algorithm.
  arXiv  Detail & Related papers  (2021-05-25T19:48:35Z)

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.