acceptodds
Under review as a conference paper at ICLR 2027

Tabular TD Descends the Absolute Bellman Error

Abstract

Temporal-difference (TD) learning is the standard method for policy evaluation in reinforcement learning, but its expected update is not, in general, the negative gradient of any global objective, even in the tabular setting. This has limited the use of optimization ideas to interpret TD and to streamline its analysis. Classical contraction arguments establish convergence without requiring a strict decrease in a global error measure after each one-state update. In this paper, we show that expected tabular TD descends the stationary-weighted absolute Bellman error. As our main contribution, we prove that an expected update of any single state strictly decreases this measure whenever the updated state's Bellman error is nonzero, for any step size in . This monotonicity yields convergence under standard cumulative-step-size conditions. We then use the same descent property to derive a finite-sample bound on the expected absolute value error of sampled TD under independent sampling. We also give a local-optimization interpretation of this descent property: each expected tabular TD update can be written as the solution of a trust-region subproblem for a linear model of the absolute Bellman error. Although we focus on the tabular case, this perspective may offer a starting point for new algorithms, including ones that use function approximation.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning theory, temporal difference learning, tabular TD

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_M9oVOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies policy evaluation in discounted, ergodic, tabular Markov reward processes. It uses the stationary-distribution-weighted absolute Bellman error (ABE) to characterize TD’s progress. The main result shows that an expected TD update at any state with a nonzero Bellman residual strictly decreases ABE for any step size in (0, 1]. The authors use this property to establish convergence, provide a local optimization interpretation, and derive a last-iterate error bound under independent generative-model sampling.

Critical strengths

Finding an explicit objective that explains TD’s progress is an interesting and well-motivated research direction. The main descent theorem is simple, technically sound, and provides useful insight into the algorithm. Its connections to convergence analysis and local optimization make the contribution coherent.

Critical weaknesses

The applicability beyond the tabular setting remains unclear. In particular, it is not evident how the proposed objective and optimization interpretation extend to standard linear TD or emphatic TD (ETD). Although function approximation is acknowledged as future work, a clearer discussion would help readers understand the broader implications of the result.

Questions for authors

Could the authors clarify whether an analogous objective and optimization interpretation can be established for linear TD or ETD? If such an extension requires additional assumptions, please state them and provide a brief proof sketch where feasible. Otherwise, please explain the main obstacle.

2 comments
AuthorsOpenReview ↗

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=Φθv=\Phi\theta, where row ss of the feature matrix Φ\Phi is the feature vector ϕ(s)\phi(s). Under standard on-policy assumptions, linear TD converges to the TD fixed point, which generally differs from the minimizer of BE1BE_1 over θ\theta, so BE1BE_1 itself cannot in general be the objective that linear TD descends. At the TD fixed point, the expected update direction h(θ)=Φ⊤DπδΦθh(\theta)=\Phi^\top D_\pi\delta_{\Phi\theta}, with Dπ=diag(dπ)D_\pi=\mathrm{diag}(d_\pi), is zero, although the Bellman errors generally are not. An analogue of BE1\mathrm{BE}_1 is therefore an ℓ1\ell_1 norm of hh, as linear TD relates to the projected rather than the full squared Bellman error.

Extensions.

  • An analogue of Theorem 1. If A=Φ⊤Dπ(I−γP)ΦA=\Phi^\top D_\pi(I-\gamma P)\Phi is diagonally dominant by columns under some positive weights ww, i.e., wjAjj>∑i≠jwi∣Aij∣w_jA_{jj}>\sum_{i\ne j}w_i|A_{ij}| for every column jj, as I−γPI-\gamma P is under dπd_\pi by stationarity, then ∑jwj∣hj∣\sum_jw_j|h_j| decreases at every mean update with α≤1/max⁡jAjj\alpha\le1/\max_jA_{jj}. The proof is the same: the mean update maps hh to (I−αA)h(I-\alpha A)h, and column dominance with the triangle inequality gives the decrease. The argument of Corollary 2 then gives a trust-region interpretation in parameter space. The condition holds, for example, under state aggregation: if the states are partitioned into disjoint groups G1,…,GkG_1,\dots,G_k and ϕ(s)\phi(s) is the one-hot indicator of the group containing ss, so that all states in a group share one value, then AA has nonpositive off-diagonal entries and, by stationarity, its jj-th column sums to (1−γ)∑s∈Gjdπ(s)>0(1-\gamma)\sum_{s\in G_j}d_\pi(s)>0; hence the condition holds with w=1w=\mathbf 1.
  • ETD. For ETD(0) with constant interest, ETD's emphatic state weights make the weighted matrix F(I−γPπ)F(I-\gamma P_\pi) strictly diagonally dominant by columns, where FF is the diagonal matrix of emphatic weights. Hence, in the tabular case, the emphasis-weighted absolute Bellman error decreases after every expected ETD update, for any full-support behavior policy with target-policy coverage, provided the effective step size at the updated state (the step size times its expected emphasis) is at most 1. With features, the analogue above, including the aggregation case, carries over with the emphatic weights in place of dπd_\pi.

Obstacle. In the tabular case, an update at ss changes only v(s)v(s), so the only errors it can increase are those of predecessors of ss, through their transitions into ss; stationarity bounds these increases. With general features, the update also changes every v(s′)v(s') by αδ(s)ϕ(s′)⊤ϕ(s)\alpha\delta(s)\phi(s')^\top\phi(s). These changes depend on how much the feature vectors of ss and s′s' overlap, not on whether s′s' transitions into ss, 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.

Thanks!

Reviewer_tkEUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper shows that the expected tabular TD update at each step decreases the stationary-weighted absolute Bellman error. From this descent property, it derives convergence guarantees, a trust-region interpretation, and a finite-sample bound for sampled TD under independent state sampling.

Critical strengths

The paper offers a clear optimization perspective on expected tabular TD: it identifies a global error measure that decreases after each coordinate update.

Critical weaknesses

The main descent theorem appears to be a special case of an existing residual inequality. Frommer and Szyld [1, Section 3, proof of Theorem 4, Eq. (24)] establish a residual inequality for each coordinate update. As far as I can tell, this inequality yields Theorem 1 of the paper as follows.

Let P\mathbf P be the transition matrix and dπ>0\mathbf d_\pi>\mathbf 0 its stationary distribution. For a stepsize 0<α≤10<\alpha\le 1, set H=(1−α)I+αγP\mathbf H = (1-\alpha)\mathbf I+\alpha\gamma\mathbf P, c=αr\mathbf c = \alpha\mathbf r, and u=dπ\mathbf u = \mathbf d_\pi in their framework. Their residual becomes r^=αδv\widehat{\mathbf r} = \alpha\boldsymbol\delta_{\mathbf v}, and their coordinate update becomes the expected TD update v+=v+αδv(s)es\mathbf v^+ = \mathbf v+\alpha\delta_{\mathbf v}(s)\mathbf e_s. Since α≤1\alpha\le 1, the matrix H\mathbf H has nonnegative entries, and the stationarity of dπ\mathbf d_\pi gives

ρs=∑jdπ(j)∣Hj,s∣dπ(s)=1−α(1−γ).\rho_s = \frac{\sum_j d_\pi(j)|H_{j,s}|}{d_\pi(s)} = 1-\alpha(1-\gamma).

Their inequality

∥r^+∥1,u≤∥r^∥1,u−(1−ρs)u(s)∣r^(s)∣\Vert\widehat{\mathbf r}^{+}\Vert_{1,\mathbf u} \le \Vert\widehat{\mathbf r}\Vert_{1,\mathbf u} - (1-\rho_s)u(s)|\widehat r(s)|

then yields, after division by α\alpha,

BE⁡1(v+)≤BE⁡1(v)−α(1−γ)dπ(s)∣δv(s)∣.\operatorname{BE}_1(\mathbf v^+) \le \operatorname{BE}_1(\mathbf v) - \alpha(1-\gamma)d_\pi(s)|\delta_{\mathbf v}(s)|.

This matches Theorem 1, including its constant and its stepsize range. For this reason, I have concerns about the novelty of the paper's central result.

[1] Andreas Frommer and Daniel B. Szyld. "On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations."

Questions for authors
  1. If my specialization above is correct, it recovers Theorem 1. Could the authors clarify whether Theorem 1 contains a distinction or an additional contribution that I may have missed? Such a clarification would help me assess the novelty of the result.
  2. If Theorem 1 follows from the result of Frommer and Szyld [1], and the absolute Bellman-error objective has been studied by Patterson et al. (2023), as the paper acknowledges, the remaining contribution would rest on the optimization interpretation and the stochastic analysis. The descent guarantee concerns exact expected updates, and the sampled result bounds the expected value error under independent state sampling. Neither result describes how the absolute Bellman error evolves along TD updates driven by a single Markov trajectory, which makes it difficult for me to assess the relevance of the interpretation to trajectory-based TD. Could the authors clarify what new insight or guarantee these results provide beyond the existing objective and descent inequality?
3 comments
AuthorsOpenReview ↗

Author Response: Relation to prior work (1/2)

We thank the reviewer for their positive assessment of the optimization perspective and for identifying the connection to Frommer and Szyld (2023). We appreciate this connection and believe it strengthens the paper.

W1 / Q1: Relation to Frommer & Szyld, and the contribution of Theorem 1

The reviewer's derivation is correct. With H=(1−α)I+αγPH=(1-\alpha)I+\alpha\gamma P, c=αrc=\alpha r, and u=dπu=d_\pi, their residual becomes αδv\alpha\delta_v, and stationarity gives ρs=1−α(1−γ)\rho_s=1-\alpha(1-\gamma). Their Eq. (24), divided by α\alpha, recovers Theorem 1. The revision presents this derivation in a remark after Theorem 1, credited to the anonymous reviewer, since it does not appear in the referenced Frommer & Szyld paper. We keep our direct proof because it shows the mechanism: stationary weighting makes the improvement at the updated state dominate the possible increases at its predecessors.

In the reviewer's words, the paper "identifies a global error measure that decreases after each coordinate update." That identification, of a previously unrecognized property of TD, is the contribution of Theorem 1, not the technical difficulty or originality of its proof. Indeed, the proof is deliberately elementary and short enough to include in the main text. The important finding is that expected TD, whose update is not the gradient of any objective (Barnard, 1993), strictly decreases a fixed global objective at every nontrivial one-state update, for every state and step size in (0,1](0,1]. This reveals a connection between TD and optimization that is not implied by convergence alone: under the same updates, the squared Bellman error can increase (App. A) and the maximum value error can stay unchanged. The theorem therefore provides a concrete and informative notion of global progress for TD's local bootstrapping updates. The paper contributes an understanding of TD's update dynamics, not a technically difficult proof.

Recovering this result through a retrospective specialization differs from identifying the TD property in the first place. Eq. (24) of Frommer & Szyld (2023) is an intermediate step in the proof of their Theorem 4: a one-step bound for an arbitrary iteration matrix and arbitrary weights, within an analysis of randomized and greedy relaxation methods. Their paper does not consider TD, Bellman errors or Markov chains, so neither the correspondence nor the resulting understanding of TD appears there. The link is visible in retrospect, once the TD statement is formulated; formulating and establishing that statement is our contribution, and the alternative derivation adds to it rather than replacing it.

AuthorsOpenReview ↗

Author Response: Implications for TD (2/2)

Q2 (a): What the paper contributes beyond the objective and the inequality

Beyond the descent inequality, the paper characterizes what TD does on this objective: it is a local trust-region method, not gradient descent. Corollary 2 shows that each expected TD update is the unique minimizer of a supporting affine model of BE1\mathrm{BE}_1 (Eq. 19) over a residual-scaled trust region. The region's shape is not arbitrary: its statewise cap ∣δv(s)∣|\delta_v(s)| is exactly the one under which Proposition 1 certifies descent, and it cannot be uniformly enlarged (App. B).

This sharply separates TD from Patterson et al. (2023), who minimize absolute and Huber Bellman errors with saddle-point gradient methods that do not reduce to TD in the tabular case. Specifically, with on-policy weighting and an exact secondary estimate, the expected update of their absolute-error method is a subgradient step on BE1\mathrm{BE}_1. Patterson et al. describe semi-gradient rules (like TD) as ones that "do not minimize a known loss"; to our knowledge, this paper is the first to relate TD to this objective and to trust-region methods on it. Methods built on this geometry would therefore differ from gradient methods on the same objective, such as Patterson et al.

The descent property also yields guarantees that the inequality alone does not:

  • Convergence (Cor. 1) for any sequence of updated states and time-varying step sizes, proved by descent of a fixed objective rather than by the contraction or ODE arguments of prior TD analyses.
  • Finite-sample bounds for sampled TD (Thm. 2, Cor. 3). With sampled rewards and transitions, the update matrix and the noise share samples, a setting Frommer & Szyld do not treat. Cumulative descent bounds the propagated variance (C.38–C.41), giving a noise term independent of the sampling distribution.
  • Why ℓ1\ell_1 (App. A): the squared Bellman error can increase under the same updates.

Because the tabular instance of this trust-region geometry is TD, it offers a principled starting point for new methods with function approximation; developing them is beyond the scope of this paper.

Q2 (b): Single-trajectory TD

Theorem 1 and Corollary 1 hold for any state-selection sequence, including those generated by a Markov trajectory, when updates use exact Bellman residuals. Under the independent sampling of Section 5, the sampled result bounds not only the expected value error but also E BE1\mathbb E\,\mathrm{BE}_1 (Cor. 3). Theorem 2 does not make any claim about single trajectory TD. Independent sampling is a standard first setting for finite-sample analysis of TD (e.g., Bhandari et al., 2021); a bound for a single Markov trajectory would require mixing-time arguments and is not claimed. The revision makes this boundary and the step decomposition above explicit.

We are grateful for these questions, which have sharpened the paper's positioning. We have added a discussion of the contrast between TD's trust region and the Euclidean ball underlying Patterson et al.'s subgradient step, and clarified in Section 5 how Theorem 1 applies along a single trajectory and that the finite-sample analysis assumes independent sampling.

Reviewer_tkEUOpenReview ↗

Response to authors

Thanks for the thorough reply and for including the Remark following Theorem 1. I appreciate your honesty in confirming that Theorem 1 is a consequence of the Frommer–Szyld inequality. I take your point that observing this property for TD is worthwhile in its own right, but that still leaves the paper's main theorem as a special case of a known result.

As I see it, the trust-region perspective and the finite-sample bound do not offer anything new on top of that either.

Given these points, I will leave my rating unchanged.

Reviewer_spBiOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

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\text{BE}_{1}) 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\text{BE}_{1} 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\ell_{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\text{BE}_{1} error under asynchronous TD updates. They show that the BE1\text{BE}_{1} of a value vector after one TD update step is smaller than or equal to the BE1\text{BE}_{1} of the value vector before the update minus the stationary-distribution-weighted absolute Bellman error of the updated state s∈Ss\in\mathcal{S}, which also depends on the learning rate and discount factor BE1(v′)≤BE1(v)−α(1−γ)dπ(s)∣δv(s)∣.\text{BE}_{1}(v')\leq\text{BE}_{1}(v)-\alpha(1-\gamma)d_{\pi}(s)|\delta_{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\ell_{1} property of BE1\text{BE}_{1}, 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\text{BE}_{1} 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 vv, such that the model is written as Lv(⋅)L_{v}(\cdot). In the appendix, the paper shows that BE1\text{BE}_{1} can be decreased if the values of the updated vector v′v' are closer to their respective Bellman targets than vv for all states, that is, when the state-wise absolute distance between vv and v′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′v' that satisfy this state-wise scaled bounded distance to vv. The unique minimizer of the local model Lv(⋅)L_{v}(\cdot) 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\text{BE}_{1} 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\text{BE}_{1} 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.

Critical strengths
  1. The paper pursues the goal of extending the tools and perspectives available for the (theoretical) analysis of TD learning. This goal is valuable, since new tools can have downstream use cases that are not yet obvious.
  2. The paper and appendix are well written and "documented", with steps and context justified and explained, which makes them easy to follow and read. While this is expected in a main body of a paper, I appreciate that this also extends throughout the appendix.
Critical weaknesses
  1. The related-literature section would be better placed directly after the introduction, since it does not depend on the paper’s results and provides context that is useful while reading. In addition, the related-literature and discussion sections partly repeat each other; with related work placed before the core sections and the discussion after them, this overlap would disappear.
  2. The related literature currently relates the paper to other works evaluating TD learning. Since the paper uses methods related to the positive-systems and switched-systems theory (Equation (9) can be represented as such a system via δv′=M(s)δv\delta_{v'} = M(s)\delta_{v} with M(s)=I∣S∣+α(γP−I∣S∣)eses⊤M(s) = \mathbb{I}_{|\mathcal{S}|}+\alpha(\gamma P - \mathbb{I}_{|\mathcal{S}|})e_{s}e_{s}^{\top} which has non-negative entries for α≤1\alpha\leq 1), an additional paragraph for context of the work relative to that branch of research would improve positioning and point interested readers to related directions.
Questions for authors
  1. The setup of Corollary 2 requires α>0\alpha>0 whereas the trust region (21), used in the corollary, is constructed with αμ(s)≤1\alpha\mu(s)\leq 1 for all s∈Ss\in\mathcal{S}. Is this condition assumed implicitly in the corollary, or how is the trust region interpreted when αμ(s)>1\alpha\mu(s)>1?
  2. The trust-region perspective is mentioned in several places as being a possible tool for designing new TD variants with function approximation, while the discussion sections explains the limitation of the state-wise argument not extending to that setting. Do you already have a direction in mind for what an analogue could look like under function approximation, or is this, at the current stage, intended as a broad outlook?

Details

  1. There is a paragraph from the reviewer instructions embedded at the bottom of the first page that should not be there.
  2. Equation (8) ends with a red dot.
  3. Lines 187-188: Adding something like "...summing the per-step decreases and telescoping the RHS ..." would improve clarity.
  4. Around Equation (19): Adding a subscript σv\sigma_{v} to the sign function would carry the dependence on the fixed vv more clearly while matching the general notation style.
  5. Proof of Corollary 2: Introducing the constant cc and function g(⋅)g(\cdot) would improve clarity and flow.
2 comments
AuthorsOpenReview ↗

Author Response to Reviewer spBi

We thank the reviewer for the careful reading, for the constructive suggestions, and for recognizing the value of extending the tools and perspectives available for TD analysis.

W1: Placement of related work.

We agree that related work section would be more useful right after the introduction. In the revised version, we moved the conceptual related-work discussion after the introduction and retained theorem-dependent quantitative comparisons alongside the finite-sample results.

W2: Relation of Eq. (9) to positive- and switched-systems theory.

We agree that this is a useful connection. In the reviewer's notation, M(s)=I+α(γP−I)eses⊤≥0M(s)=I+\alpha(\gamma P-I)e_se_s^\top\ge0 for α≤1\alpha\le1 (the nonnegativity used in our proof of Proposition 1, App. B), and stationarity gives dπ⊤M(s)=dπ⊤−α(1−γ)dπ(s)es⊤d_\pi^\top M(s)=d_\pi^\top-\alpha(1-\gamma)d_\pi(s)e_s^\top for every ss. In this language, Theorem 1 states that BE1(v)=dπ⊤∣δv∣\mathrm{BE}_1(v)=d_\pi^\top|\delta_v| is a common weak Lyapunov function for the switched residual dynamics, with strict decrease whenever the selected state's Bellman error is nonzero. On the nonnegative orthant, this reduces to a linear copositive function. Convergence additionally requires the update-coverage condition of Corollary 1. In the revised version, we added this systems-theoretic interpretation and relevant references (e.g., Mason and Shorten, 2007), alongside the related weighted-residual perspective of Frommer and Szyld (2023).

Q1: Corollary 2 assumes only α>0\alpha>0, but Eq. (21) is motivated by αμ(s)≤1\alpha\mu(s)\le1. Is the latter implicit, and what happens when αμ(s)>1\alpha\mu(s)>1?

No condition is implicit. Corollary 2 states that the minimizer of the supporting model LvL_v over the box (21) is the mean TD update (7). This holds for every α>0\alpha>0: (21) is a bounded box for any step size, and the proof does not use αμ(s)≤1\alpha\mu(s)\le1. Whether the update also decreases BE1\mathrm{BE}_1 is not the subject of Corollary 2.

That is what max⁡sαμ(s)≤1\max_s\alpha\mu(s)\le1 ensures, and it is what makes the box a trust region: by Proposition 1, the trust-region minimizer then decreases BE1\mathrm{BE}_1 whenever the update is nonzero. The condition is needed because LvL_v only bounds BE1\mathrm{BE}_1 from below, so minimizing it does not by itself reduce BE1\mathrm{BE}_1. The condition max⁡sαμ(s)≤1\max_s\alpha\mu(s)\le1 holds automatically for α≤1\alpha\le1, since μ(s)≤1\mu(s)\le1. If αμ(s)>1\alpha\mu(s)>1 for some ss, Corollary 2 still holds, but BE1\mathrm{BE}_1 can increase (App. B). The revision states the condition before Eq. (21) and adds a remark after Corollary 2 separating the two statements.

Q2: Is there a concrete direction for the trust-region view under function approximation, where the state-wise argument does not extend, or is this a broad outlook?

There is a concrete direction, though developing it is beyond this paper. The trust-region view separates TD from gradient methods on the same objective: over a Euclidean ball, the supporting model of BE1\mathrm{BE}_1 yields a (sub)gradient step, while over our residual-scaled box it yields TD (Corollary 2). This suggests minimizing BE1\mathrm{BE}_1 with trust-region rather than steepest-descent steps under function approximation, for instance by constraining the change in predicted values, rather than the parameters, to a residual-scaled region. The main obstacle is that with shared features a parameter step moves many states at once, so the state-wise region cannot be enforced directly; finding an effective form is future research. This is one potential use; as the reviewer notes, new tools can have downstream uses that are not yet obvious. We state this direction and its obstacle in the Discussion (Section 7).

Details.

We thank the reviewer for detailed reading. We addressed all the suggested modifications.

  • (1) Reviewer instructions on page 1: This notice is not part of our source; it appears to have been added to the review copy.
  • (2) Red dot after Eq. (8): Removed.
  • (3) Lines 187–188: Now state that summing the per-step decreases and telescoping the right-hand side gives (17).
  • (4) Subscript on the sign function: We now write σv(s)=sign(δv(s))\sigma_v(s)=\mathrm{sign}(\delta_v(s)) consistently in Section 5.
  • (5) cc and gg in the proof of Corollary 2: Now Lv(v′)=cv+gv⊤v′L_v(v')=c_v+g_v^\top v' with cv=σv⊤Dπrc_v=\sigma_v^\top D_\pi r and gv=−(I−γP)⊤Dπσvg_v=-(I-\gamma P)^\top D_\pi\sigma_v. Stationarity gives σv(s)gv(s)≤−(1−γ)dπ(s)<0\sigma_v(s)g_v(s)\le-(1-\gamma)d_\pi(s)<0 whenever δv(s)≠0\delta_v(s)\ne0, which shortens the proof.

[1] O. Mason and R. Shorten (2007). On Linear Copositive Lyapunov Functions and the Stability of Switched Positive Linear Systems. IEEE Transactions on Automatic Control, 52(7), 1346-1349.

Thank you for the detailed clarification of my questions and the updated manuscript. I do think the revised manuscript has also increased accessibility, which is great for a work that provides new tools.

With these issues/questions resolved, I will raise my score now and give my final recommendation after the reviewer–AC discussion phase.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.