Source-linked AI summary
Reinforcement Learning as (Discrete) Potential Theory
Christopher Connolly
TL;DR
Reinforcement learning theory is closely tied to probability through Markov chains, but its connection to potential theory is underused. This paper reviews that connection under fixed policies and shows how it reframes value functions, temporal-difference learning, and credit assignment through discrete potential theory.
Problem
The paper addresses the limited use of probability–potential theory equivalences as viewpoints for reinforcement-learning representations, sample efficiency, and credit assignment.
Method
The paper reviews core reinforcement-learning representations and algorithms through discrete potential theory for fixed policies, including value functions, temporal differencing, and eligibility fields.
Results
The potential-theoretic view identifies value functions with harmonic or hitting-probability solutions and extends eligibility traces into fields that diffuse credit across learned transition structures.
Takeaways & Limitations
Harmonic value functions support convergence and correctness tests, while harmonic interpolation suggests strategies for filling sparse state spaces.
Takeaways & Limitations
The framework is developed primarily for fixed-policy reinforcement learning; nonlinear potential theory for policy and game-theoretic optimization is out of scope.
Abstract
from arXiv · showhide
Reinforcement learning (RL) theory fundamentally depends on probability theory through the Markov chain. There is a deep connection between probability theory and potential theory. This paper reviews that connection and explores the potential-theoretic viewpoint for core reinforcement learning representations and algorithms under a fixed-policy assumption. This viewpoint may offer a path for improved sample efficiency and formal constraints that can be applied to RL. When the fixed-policy assumption is relaxed, the linear potential theory framework can be naturally extended to the nonlinear case.
1 Introduction
The paper reviews reinforcement learning through potential theory, linking Markov-chain structures to equations and representations from potential theory. It focuses initially on discrete graph problems under a fixed policy, while identifying extensions to continuous domains and nonlinear policy optimization.
- Motivation: RL’s Markov-chain foundations correspond to potential-theoretic structures, including harmonic functions, Poisson equations, and Green’s functions.These correspond respectively to hitting probabilities, expected costs, and occupancy measures, and appear in RL value functions and temporal-difference learning.
- Core correspondences: Episodic RL with terminal rewards maps to Laplace’s Equation, ongoing control with distributed rewards to Poisson’s Equation, and nonstationary environments to the Diffusion (Heat) Equation.The three cases admit both discrete and continuous domains.
- Discrete viewpoint: In discrete graph problems, optimal state-action sequences can be viewed as streamlines in a value-induced flow through state space.The discussion primarily uses discrete problems on graphs, with finite difference methods treated as discrete potential problems.
- Assumptions and scope: The analysis fixes a policy to preserve linearity and expose direct equivalences, while nonlinear policy optimization can be decomposed into multiple linear subproblems.Continuous state-space extensions follow from the connection to potential theory.
- RL representations: The discrete RL linear system is the analogue of Poisson’s equation, with reward r(x) serving as the source function f(x), and one matrix equation gives a TD credit-assignment step.Successor Representations are linear operators mapping reward vectors directly to value functions.
2 Case by Case Equivalences
Under a fixed policy, RL value functions correspond to discrete potential-theoretic solutions: absorbing problems yield harmonic functions and Dirichlet problems, while distributed rewards yield Poisson equations. Iterative policy evaluation corresponds to heat-equation relaxation, converging toward the Poisson solution, with discounting represented as decay.
- Absorbing and harmonic equivalences: In absorbing MDPs, the value function is harmonic on transient states and satisfies Dirichlet boundary conditions at absorbing states.The harmonic relation is v = Pv, with boundary values determined by rewards at absorption.
- Absorbing and harmonic equivalences: With win-boundary reward 1 and lose-boundary reward 0, each transient-state value equals the probability of hitting win before lose.A deterministic policy maximizing success follows the value gradient toward the win set.
- Absorbing and harmonic equivalences: Any absorbing-MDP value function obeys the mean-value and min-max properties, so transient local extrema indicate improper convergence.The residual Pvn − vn+1 provides a convergence score indicating whether more training is needed.
- Poisson equivalence: Distributed rewards act as interior source terms, making the undiscounted Bellman equation the discrete Poisson equation for persistent control problems.This formulation applies to ongoing tasks such as cart-pole balancing rather than rewards limited to absorbing states.
- Heat-equation equivalence: Iterative policy evaluation is a discrete heat-equation relaxation process that converges as t →∞ to the Poisson solution.With discounting, value functions arise as steady states of forced diffusion with decay.
3 Green’s Functions: The Fundamental Matrix and Dayan’s Successor Representation
The section connects absorbing-state block decompositions with Green’s functions and Dayan’s Successor Representation, enabling value computation from rewards. It then extends the potential-theoretic formulation to ongoing non-absorbing chains through the fundamental matrix, with normalization required for unique solutions.
- Absorbing chains: Reordering transient and absorbing states into blocks reveals a Green’s function equivalent to Dayan’s Successor Representation for computing value or Q from rewards.Absorbing states have no outward transitions and rows containing a single 1.
- Absorbing chains: For absorbing chains, the value over transient states is computed from rewards and absorbing-state outcome probabilities.The function g(s), when normalized to [0, 1], represents configurable absorption probabilities.
- Ongoing chains: For ongoing non-absorbing control problems, P = Q, and the discrete Poisson equation describes the resulting Markov chain potential.With no absorbing states, Q fills P.
- Ongoing chains: The fundamental matrix is generated by repeated applications of Q, represented by a convergent Neumann series, and serves as a Green’s function for the Markov chain potential.This provides the ongoing-chain analogue of the Green’s-function formulation.
- Ongoing chains: Poisson-equation solutions are otherwise unique only up to an additive constant, so fixed-point iteration requires a constraint such as zero mean.Defining average reward and differential value supports this constrained formulation.
- Ongoing chains: A normalization condition such as h(s0) = 0 fixes the additive constant and ensures uniqueness without risking solution divergence.The condition removes the ambiguity in differential-value solutions.
4 Successor Representation
The successor representation was developed in reinforcement learning and resembles the fundamental matrix, with exponential discounting applied to the transition operator P. Under exponential discounting, its defining equation has a unique solution for γ < 1.
- Dayan’s successor representation was developed in the context of reinforcement learning.
- The successor representation resembles the fundamental matrix while applying exponential discounting to the transition operator P.
- For γ < 1, exponential discounting guarantees a unique solution to the successor representation equation.
5 Eligibility Trace to Eligibility Field
The section reframes eligibility traces as a potential-theoretic mechanism for credit assignment over learned state-transition structure. It generalizes chain-based eligibility into an eligibility field that propagates credit spatially backward through the learned graph.
- Trace-Based Eligibility: Traditional TD distributes value-update credit along recent state traces, while eligibility traces expose state-space topology through experienced chains.The potential-theoretic counterpart is described as similar to a Monte Carlo solution.
- Trace-Based Eligibility: TD(λ) defines eligibility distributed over a trace using state-dependent updates.The state indicator 1{S_t = s} is a one-hot encoding of the current state.
- Eligibility Field: Eligibility generalizes to a field e′ using the partially learned transition operator P^⊤.This extends credit assignment beyond the experienced trajectory as the agent estimates transition structure while exploring state space.
- Eligibility Field: Unlike the classic accumulating trace e_t+1 = γλe_t + ϕ(S_t+1), the field inserts spatial propagation through P^⊤.The injection vector ϕ(S_t+1) can be one-hot at S_t+1.
- Eligibility Field: Eligibility therefore both decays along chains and diffuses credit backward across the learned Markov transition graph.The backward diffusion follows the graph defined by P^⊤.
6 Summary and Observations
Under a fixed-policy assumption, reinforcement learning admits a discrete potential-theoretic interpretation linking core representations to Laplace, Poisson, heat, and Green’s-function concepts. This viewpoint suggests formal convergence guarantees, improved sample efficiency, and possible biological and analog-computing substrates, while policy optimization requires nonlinear potential theory beyond this paper’s scope.
- Scope and biological implications: Relaxing the fixed-policy assumption introduces nonlinearities through policy-iteration max operations and game-theoretic max-min operations, leading to nonlinear potential theory outside the paper’s scope.The paper also raises the possibility that electrical networks in the striatum, potentially involving astrocytic syncytia, could compute value functions rapidly.
- Discrete potential-theoretic correspondence: Fixed-policy reinforcement learning maps terminal-only rewards to harmonic functions and hitting probabilities, rewards-as-sources to Poisson equations, relaxation to heat equations, and successor representations to Green’s functions.These correspondences frame RL representations and dynamics through discrete potential theory.
- Limitations and interpretations: In large state spaces, harmonic value functions may develop barren plateaus near saddle points, while optimal state sequences can be viewed as discrete streamlines maximizing goal-reaching success.This perspective also motivated harmonic potentials for robot motion planning.
- Formal guarantees for RL: Episodic RL value functions are harmonic over transient states, whose mean-value and min-max properties guarantee no local minima after full convergence.The mean-value property also suggests convergence and correctness tests and interpolation strategies using harmonic interpolants.
- Sample Efficiency: Potential theory may improve sample efficiency by extending TD eligibility traces into multidimensional eligibility fields over learned transition structures, distributing credit across more states.The same viewpoint also permits analog substrates such as resistive networks for computing value functions.