The paper provides new perspectives on the process of tabular temporal difference (TD) learning. Generally not being a gradient-descent algorithm, TD learning does not provide the same intuition of decreasing an error along its surface. To fill that intuition gap, the authors provide an interpretation of individual TD update steps, which is based on the optimization of a local supporting affine model over a state-dependent trust region. To that end they use the stationary-weighted absolute Bellman error (BE1) as the objective. This error is the weighted sum of absolute Bellman errors across states for a given value function/vector, weighted by the stationary distribution of those states. Besides the local trust region update interpretation, the main contribution of the paper is a strict descent property of the BE1 under single asynchronous updates. Using this property, they then show a finite-sample complexity on the error bound obtained from updates that follow an arbitrary, but independent, sampling distribution. The authors highlight that their work is purely of a theoretical nature and they don't challenge existing convergence results but instead want to offer a complementary perspective and to show how the ℓ1 norm based error makes it possible to connect tabular TD learning to optimization theory.
As its first step, the paper establishes the strict descent property of the BE1 error under asynchronous TD updates. They show that the BE1 of a value vector after one TD update step is smaller than or equal to the BE1 of the value vector before the update minus the stationary-distribution-weighted absolute Bellman error of the updated state s∈S, which also depends on the learning rate and discount factor
BE1(v′)≤BE1(v)−α(1−γ)dπ(s)∣δv(s)∣.
Based on this property, convergence of the tabular TD update is guaranteed under standard update frequency and learning rate conditions. In the appendix, they also show that this property is specific to the ℓ1 property of BE1, since it does not hold for, e.g., a the squared equivalent of the error.
Building on the strict descent property, their second step is to construct a local supporting model update over a trust region. They construct the supporting affine model of BE1 by multiplying each term in the sum of the error with the sign of the Bellman error of the corresponding state at a given reference value vector. For a Bellman error of zero, the sign function is defined as the subgradient of the absolute value. For a single update step, this reference vector is the pre-update value vector v, such that the model is written as Lv(⋅). In the appendix, the paper shows that BE1 can be decreased if the values of the updated vector v′ are closer to their respective Bellman targets than v for all states, that is, when the state-wise absolute distance between v and v′ is bounded by the absolute Bellman error. When this upper bound is scaled by the learning rate times each state's sampling probability, the trust region the paper uses consists of all the candidate vectors v′ that satisfy this state-wise scaled bounded distance to v. The unique minimizer of the local model Lv(⋅) over that trust region is the mean expected TD update rule. The authors highlight that this comparison is intended for interpretation of the descent geometry, in the sense of: we can build this system that allows us to recover and study the dynamics we are interested in.
As the final step, the authors derive a finite-sample bound and complexity for BE1 TD learning with the update states sampled according to an arbitrary, but full-support, distribution. As stated in the introduction, the authors highlight that these bounds are not intended to improve upon existing bounds but instead to demonstrate the descent property of BE1 can be used in finite-sample analysis.
The paper then concludes with a discussion of related literature that positions the authors' work in the space of existing methods of analyzing TD learning and a discussion of their contributions in that context.
Author Response to Reviewer M9oV
We thank the reviewer for the positive assessment and for their question, which helped us clarify how the results extend beyond the tabular case.
Q: Can an analogous objective and optimization interpretation be established for linear TD or ETD? If this requires additional assumptions, which ones, with a proof sketch; otherwise, what is the main obstacle?
Short answer. Partly. Under explicit structural assumptions, both the descent property and the trust-region interpretation extend, for TD and ETD; we state them below with proof sketches. For features without such structure, we have not found a positive result, and we explain the obstacle.
Objective. Let v=Φθ, where row s of the feature matrix Φ is the feature vector ϕ(s). Under standard on-policy assumptions, linear TD converges to the TD fixed point, which generally differs from the minimizer of BE1 over θ, so BE1 itself cannot in general be the objective that linear TD descends. At the TD fixed point, the expected update direction h(θ)=Φ⊤DπδΦθ, with Dπ=diag(dπ), is zero, although the Bellman errors generally are not. An analogue of BE1 is therefore an ℓ1 norm of h, as linear TD relates to the projected rather than the full squared Bellman error.
Extensions.
Obstacle. In the tabular case, an update at s changes only v(s), so the only errors it can increase are those of predecessors of s, through their transitions into s; stationarity bounds these increases. With general features, the update also changes every v(s′) by αδ(s)ϕ(s′)⊤ϕ(s). These changes depend on how much the feature vectors of s and s′ overlap, not on whether s′ transitions into s, so stationarity does not bound them, and column dominance can fail. We do not know an objective of this kind that linear TD descends for general features; finding one, or the broadest conditions under which one exists, is an open research direction.
The revised Discussion (Section 7) discusses a summary of these obstacles.