acceptodds
Under review as a conference paper at ICLR 2027

Policy Gradients for Average Path-Dependent Utility in Continuing MDPs

Abstract

Reinforcement learning typically represents desired behavior through additive per-step rewards, which can be difficult to design, and may fail to capture preferences that depend on more complicated patterns or entire trajectories. Unlike MORL, AverageRL, or General Utility RL, we study average path-dependent utility (APDU), a long-run average objective for continuing tasks in which performance is evaluated using trajectory-level utility. We restrict our attention to ergodic Markov decision processes and parametrized Markovian policies. For this setting, we first consider the case where the utility functional is known. We show that the APDU objective admits a policy-dependent proxy-reward whose expectation under the stationary state–action distribution exactly recovers the original objective. This proxy reward enables us to define a differential action-value function and derive an average-utility policy-gradient theorem. We then address the more challenging (and versatile) setting in which the utility functional is unknown and only trajectory-level utility feedback is observable. We introduce an action-value quantity that can be estimated directly from such feedback, establish its asymptotic relationship with the known utility action-value function, and derive a corresponding policy-gradient theorem. Building on these results, we propose Average Utility Actor–Critic (AUAC), an algorithm for optimizing APDU from trajectory-level feedback. Experiments validate our theoretical findings and demonstrate the effectiveness of AUAC on path-dependent control tasks.

Primary area:
reinforcement learning
Keywords:
Policy Gradient, Average Path-Dependent Utility, continuing MDP

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_SGpZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper introduces average path-dependent utility (APDU), a long-run objective for continuing, ergodic MDPs in which performance is scored by a utility assigned to whole trajectories rather than by per-step rewards. It assumes this objective can be expressed as a function of the policy’s stationary state–action occupancy measure. Contributions include (1) A gain-matched proxy reward, derived through a degree-one homogeneous extension, that reproduces both the objective’s value and its policy gradient. It yields a differential action-value function, an average-utility policy-gradient theorem, and the ProxyAC algorithm, (2) A trajectory-based action-value function estimated from utility increments along a single continuing trajectory. Asymptotically, it differs from the proxy-reward action-value function only by a curvature constant and a boundary residual. A matching policy-gradient theorem holds when that residual does not depend on the action, and (3) an actor–critic algorithm trained on Monte Carlo window targets.

Validation is done with relatively simple examples, which I think is acceptable given the analytical nature of the work. Experiments cover a two-state MDP, with KL-divergence, temporal-pattern, and entropy-rate objectives that each have a known analytical optimum, and a 22-state queue-control task using neural actor–critic networks. Baselines are shadow-reward actor–critic variants and a REINFORCE method. Monte Carlo tables confirm that the two action-value functions differ by a constant. Known-functional methods converge fastest, while AUAC approaches the optima with a small bias.

Critical strengths
  1. Optimizing trajectory-level, non-Markovian utilities in continuing tasks from black-box incremental feedback Δut(L)=u(τ0:t+L)−u(τ0:t)Δu_t (L)=u(τ_{0:t+L} )-u(τ_{0:t}), without restarting the evaluator, is well motivated (e.g., preference-style feedback on long-running systems). The decomposition qθτ=qθu+Cθ+Bθq_θ^τ=q_θ^u+C_θ+B_θ, whose curvature term Cθ=1⁄2tr[HF(μθ)Σθ]C_θ=1⁄2 tr[H_F (μ_θ ) Σ_θ ] (the bias from evaluating a nonlinear F at empirical occupancies) is action-independent and hence acts as a baseline, is a neat insight that justifies learning a critic directly from trajectory feedback.

  2. The paper offers pathways to address APDU both utility function is known and unknown. The analytical findings are charming and the algorithms for both cases converges elegantly.

Critical weaknesses
  1. The novelty of the setting is overstated. By telescoping, which the paper itself uses in Eq. (151), the utility of a prefix is the sum of its one-step increments, u(τ0:T)=u(τ0:0)+∑t=0T−1Δut(1)u(\tau_{0:T}) = u(\tau_{0:0}) + \sum_{t=0}^{T-1} \Delta u_t(1). APDU is therefore average-reward RL with a history-dependent reward rt=Δut(1)r_t = \Delta u_t(1); AUAC simply aggregates these increments over windows. The claim that “this setting is novel in RL” (Appendix A) should be moderated. The paper should also position itself against closely related work, including non-Markovian rewards and reward machines (Toro Icarte et al., 2018), RL with trajectory feedback (Efroni et al., 2021), and convex RL with finite trials (Mutti et al., 2022). The last of these is directly related to the curvature term CθC_\theta.

  2. The proxy reward does not change the differential value function. The proxy reward equals the shadow reward plus a constant shared by all state–action pairs, rθu=rθsh+cθr_{\theta}^u= r_\theta^{sh} + c_\theta. Because the differential qq-function depends only on the reward minus its gain, both rewards yield identical qθq_\theta and hθh_\theta. This contradicts the claim at the end of Appendix B. For the same reason, ProxyAC and ShadowAC have essentially the same TD error, so the overlapping curves in Fig. 1 are expected rather than evidence for the construction. For the entropy-rate objective, FF is degree-1 homogeneous, so cθ=0c_\theta = 0 and the two methods coincide exactly.

  3. The empirical evaluation is limited. The experiments use a one-parameter two-state chain and a 22-state queue, so it is unclear whether the method scales beyond toy problems. In every task, the “black-box” evaluator is built from a known FF, so no experiment covers the motivating case where FF is unavailable. The baselines are weak:

  • ShadowAC is practically identical to ProxyAC.

  • ShadowAC-Biased and ProxyAC-PO are biased by design.

  • REINFORCE is a minimal reference point.

Methods that use comparable feedback are missing, such as an actor–critic with a history-based (e.g., recurrent) critic trained on per-step increments, or return-decomposition approaches. Reward-machine methods would also be an informative comparison for the pattern objectives. Finally, the paper reports neither the number of seeds nor what the shaded regions represent, although some bands are very wide (e.g., AUAC in Fig. 5).

  1. The presentation needs careful proofreading.
  • Typos, e.g., “piθ” (Section 1) and “addtion” (Theorem 3).

  • Redundant appearances. The quantity lim⁡T→∞1TEθ[u(τT)]\lim_{T \to \infty} \frac{1}{T} \mathbb{E}_\theta \left[u(\tau_T)\right] is restated in Eqs. (2), (12), (14), and (24), which wastes space and confuses the reader.

  • Substantive errors: Eq. (11) has the wrong sign; it should be u(τt0:t+T)−u(τt0:t)u(\tau_{t_0:t+T}) - u(\tau_{t_0:t})

Questions for authors

Q1. Below Eq. (5), the paper states that the occupancy-measure representation is a structural assumption defining the class studied. Which practically relevant utilities satisfy this assumption, beyond the distributional and pattern-count objectives in the experiments? Appendix C.9 notes that non-local utilities (running maxima, drawdowns, longest runs) may violate it. How does AUAC behave in such cases, empirically or theoretically?

Q2. The proxy and shadow rewards differ only by a constant, rθur_\theta^u. Appendix D.1.2 already establishes that they share the same policy gradient, and that ShadowAC is correct when centred by its own gain. Beyond reporting F(μθ)F(\mu_\theta) as the gain, does gain matching offer any practical advantage, for example in critic accuracy, stability, or sample efficiency?

Q3. Degradation of APDU-Reinforce. In Figs. 6 and 8, the performance of APDU-Reinforce declines during training rather than improving slowly. Is this due to tuning, implementation, or an intrinsic property of the estimator?

2 comments
AuthorsOpenReview ↗

Reply Reviewer SGpZ, part 1: to critical weekness

\paragraph{Reply to W1} \textbf{APDU is average reward with time window history.} We thank the reviewer for these references, which we now cite and discuss in the paper. We do not believe they diminish the novelty of APDU: although related in motivation, each differs from our setting in an essential way, as we explain below. Reward machines (Toro Icarte et al., 2018) make a non-Markovian reward Markov through a finite automaton: this covers window utilities such as ABB, but not nonlinear FF (KL, entropy rate), whose increment depends on the whole empirical occupancy and admits no finite-state representation. RL with trajectory feedback (Efroni et al., 2021) shares our motivation, but assumes the trajectory score is the sum of latent per-step rewards and recovers them by least squares; our utility is not additive, so no such reward exists to recover. Neither work treats the average-reward criterion or a differential qq-function. Mutti et al.\ (2022) shows that the gap between finite-trials and infinite-trials objectives exists and matters, and gives an instance-agnostic upper bound on the loss between the two optimal policies under a Lipschitz assumption, in the episodic finite-horizon setting. Our result is complementary: for differentiable FF in the ergodic average-reward setting, we derive the leading-order value of the per-policy gap that underlies their bound, \begin{equation} \mathbb{E}\bigl[F(\hat\mu_T)\bigr] - F(\mu_\theta) \approx \frac{C_\theta}{T}, \qquad C_\theta = \frac{1}{2}\operatorname{tr}\bigl[H_F(\mu_\theta),\Sigma_\theta\bigr], \end{equation} where μ^T\hat\mu_T is the empirical occupancy of a length-TT trajectory and μθ\mu_\theta is the stationary occupancy of πθ\pi_\theta. For an unscaled utility this vanishes as T→∞T\to\infty, consistent with their remark; for our trajectory utility T F(μ^T)T\,F(\hat\mu_T) the constant CθC_\theta remains. We do not claim to subsume their result, which is non-asymptotic and covers non-smooth utilities. However, the following elements of our analysis do not appear in either version of their paper: any Hessian, covariance, or Taylor term; any constant correction to the reward or qq-function; the fact that CθC_\theta is the same for all (s,a)(s,a) and therefore drops out of the advantage; and the state-action-dependent transient Bθ(s,a)B_\theta(s,a). These are contributions made in our paper. \\

\paragraph{Reply to W2} \textbf{This contradicts the claim at the end of Appendix B. } You are correct. There is a typo in the appendix B we have fixed it. But the argument in main text (page 6) are correct.

\paragraph{Reply to W3}

\textbf{Scale.} We agree and state this as a limitation; the small environments were chosen because their optima are known, so estimator bias is measured against ground truth (see reply to Reviewer 1 W2).\\ \textbf{Known F.} AUAC never accesses FF: it receives only the scalar utility of each window from the evaluator. When the utility depends on earlier states (e.g.\textbackslash{} ABB), the history is handled inside the evaluator; the policy and critic do not observe it. We build the evaluator from a known FF only so that the optimum is available and the ∇F\nabla F-based methods can be run at all.\ \textbf{Baselines.} These are ablations, not competitors, and we now label them so. ShadowAC vs. ProxyAC isolates the normalising constant (same gradient, different ρ\rho); ShadowAC-Biased and ProxyAC-PO show what fails when the correction is dropped or the critic state is not Markov. REINFORCE is the standard method under the same black-box feedback.\\ \textbf{Missing comparisons.} We respectfully disagree that these are comparable baselines. A critic trained on per-step increments needs uu evaluated at every prefix, which is strictly more feedback than our setting provides. The increments are also poorly behaved targets: for KL they are unbounded and non-stationary when the history is short, and when the history is long they converge to the proxy reward. Reward machines and return decomposition were developed for episodic or discounted problems with finite-automaton or additive rewards with Neural Network (RUDDER); applying them here would first require extending them to the average-reward criterion and to nonlinear utilities, which is itself an open problem. Our experiments are designed to validate the theory against known optima. For the pattern objectives, ProxyAC on the window state already plays the role of the reward-machine construction. We discuss all three in related work in appendix then.\\ \textbf{Reports.} Each curve is the mean over 10 independent runs with randomly drawn seeds; shaded regions indicate the min–max variation across independent runs at each global training step. We now state this in every caption. The wide AUAC band in Fig.5 reflects the Monte-Carlo target, whose variance grows with HH, as our analysis predicts.\\

\paragraph{Reply to W4} Thank you. We have corrected these flagged typos.

AuthorsOpenReview ↗

Reply Reviewer SGpZ, part 2: to questions

\paragraph{Reply to Q1} Theoretically, we think it violates our theory (the smoothness assumption). But empirically, we have tried it and it works. This is a topic we may address in future work. \paragraph{Reply to Q2} First, in terms of explainability, it is better aligned with human users (value matching). Second, we believe the proxy reward derived from the homogeneity property reveals other mathematical properties of the proxy or shadow reward, whereas the shadow reward comes from Fenchel duality. For example, the duality \textit{derivation} needs a concave FF (e.g. it does not support F=∑sμ(s)2F=\sum_s\mu(s)^2), whereas our theory supports it. \paragraph{Reply to Q3} \textbf{Degradation of APDU-Reinforce.} It is intrinsic to the estimator; the decline persists across our tuning sweeps. REINFORCE weights HH score terms by a single utility of scale HH, so its variance grows with the trajectory length, and large noisy steps drive the policy to a near-deterministic one from which it does not recover. Nonlinear utilities (entropy, KL) amplify this, since windows that miss a state give extreme values. AUAC avoids it by using a critic and a per-step advantage.

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

The paper studies the problem of reinforcement learning with reward dependent on trajectory instead of each timestep. First, proxy per-step reward is designed using the assumption of 1-degree homogenous function on the performance metric. Using the proxy per-step reward function trajectory-based differential action-value function is designed. Further, policy gradient theorem is proven for the trajectory based reward, followed by a practical implementation of the actor-critic algorithm for both known performance metric functional and unknown case. Further, the proposed actor-critic algorithm is evaluated on two state MDP and queue control problem.

Critical strengths
  1. The paper addresses an important class of reinforcement learning problem where reward is not instantaneous but depends on the trajectory.
  2. The idea of using homogenous functions to design the per-step reward from the functional F is interesting.
  3. The paper proposes policy gradient theorem for path-based utility function and implements a practical algorithm using it.
Critical weaknesses
  1. The functional F is restricted to homogenous function of degree 1 in the paper. For an arbitrary utility function over trajectory, there is no guarantee that the induced functional F would be degree-1 homogenous function.
  2. The notation simplification used in Eq. 12 using Eq. 10 is confusing and reduces the readability of the paper.
  3. Eq. 27 contains Rt,LR_{t,L} but there is no description about the symbol.
  4. The entire discussion from Eq. 25 to Eq. 28 hides some of the really important and non-trivial details and defer it to the Appendix. The significance of Bθ(s,a)B_\theta(s,a) and CθC_\theta is not explained.
  5. Algorithm 1, step 9 is not supported by the Eq. 26. The critic update rule is unexplained.
  6. In Figure 1, the axes are not properly marked.

The paper needs a major rewrite, specially for the later part of section 6.

Questions for authors

Please refer to weaknesses.

5 comments

\paragraph{Reply to W1} Thanks for the comment. In Appendix B.1 we show that it is always possible to extend any function FF on the probability simplex to a function F~\tilde F that is homogeneous of degree 1, and that coincides with FF on the simplex. The proof is given for a discrete state space setting, but we believe it can easily be generalized. Because of the page limit, we have to move this part in the appendix.

\paragraph{Reply to W2} We thank the reviewer for this comment and agree that the passage was harder to read than necessary. We have rewritten it as follows. (i) The objective is now defined once, directly as \begin{equation*} J^u(\theta) := \lim_{T\to\infty} \frac{1}{T},\mathbb{E}\theta\bigl[u(\tau{t:t+T})\bigr], \end{equation*} where τt:t+T\tau_{t:t+T} denotes the path segment of length TT starting at time tt. (ii) We state explicitly that, under the ergodicity assumption, this limit does not depend on the starting time tt or on the history before tt, which is what justifies dropping the time indices and writing u(τT)u(\tau_T). (iii) The incremental form (former Eqs.10-11) is no longer used as the definition; it now follows the definition as an equivalent expression, with the reason for the equivalence stated explicitly. (iv) We corrected a sign inconsistency between the former Eqs.10 and 11 and unified the notation for path segments throughout the section. \paragraph{Reply to W3} Agreed. We corrected this oversight.

\paragraph{Reply to W4} We thank the reviewer for this comment. We have rewritten the text preceding Theorem 3 to make clear which utilities the theorem covers. The condition in Eq.29 requires only that the term Bθ(s,a)B_\theta(s,a) in Eq.26 does not contribute to the policy gradient, and the revised text now lists the families of utilities for which this holds. (i) The central family is that of scaled occupancy functionals, Δut(T)=F(μ^t,T) T\Delta u_t(T) = F(\widehat\mu_{t,T})\,T with FF twice differentiable, for which Bθ≡0B_\theta \equiv 0 and qθτ=qθu+Cθq^\tau_\theta = q^u_\theta + C_\theta; it includes KL divergence, entropy, and entropy rate. (ii) Additive utilities, i.e.\ the standard average-reward setting, are the linear case F(μ)=⟨μ,r⟩F(\mu)=\langle\mu,r\rangle, where in addition Cθ=0C_\theta=0. (iii) Finite-memory pattern-count utilities, such as the ABB count, are occupancy functionals of length-kk windows; they can leave a non-zero Bθ(s,a)B_\theta(s,a), but it does not depend on the action aa, so Eq.29 holds. We also explain why this family is a natural one: under ergodicity, the long-run rate of any utility that is insensitive to transient events is determined by the stationary occupancy μθ\mu_\theta, so every long-run objective can be written as Ju(θ)=F(μθ)J^u(\theta)=F(\mu_\theta). The statement of Theorem 3 itself is unchanged: given Eq.26, Eq.29 is exactly the condition under which qθτq^\tau_\theta can replace qθuq^u_\theta in the policy gradient, and it is satisfied by all utilities considered in the paper. \paragraph{Reply to W5} The update rule is based on the definition in Eq.25. We write the Loss form in the pseudocode (details in the appendix).

\paragraph{Reply to W6} Agreed. We corrected the labeling.

Thank you for addressing my concerns. Please highlight the modification made to the paper with different-colored text so that it is easy to track the changes. Further, make sure that expressions in your response are rendered properly. I still have the following concerns:

  1. Theorem 2 proof location is not provided.
  2. Rt,LR_t,L is still not defined.
  3. Several terms are used without proper definition like "stochastic fluctuation of empirical occupancy measure" (line 348), "canonical path-level representatives"(line 363), "finite memory pattern count" (Line 377)
  4. Assumption made in Theorem 3 is not justified properly. The remark following the theorem is not enough.
  5. What is incremental utility feedback (line 396)? Are you redefining differential value function ?
  6. Why is the paper estimating qτq^{\tau} instead of quq^{u} ?

We thank the reviewer for the follow-up. Since we are not sure whether colour-marking changes is permitted in the current version, we instead refer to the relevant line numbers below. Our answers to the new concerns are as follows.

  1. The proof of Theorem 2 is the whole of Appendix B; because it is long, we present it as a section rather than a single proof environment. Its core is the existence of the proxy reward, Ju(θ)=∑s,aμθ(s,a)rθu(s,a)J^u(\theta)=\sum_{s,a}\mu_\theta(s,a) r^u_\theta(s,a) . Given this representation, the remaining two claims are existing results applied to rθur^u_\theta: the existence of qruq^{r^u} follows from average-reward theory[1] , and the policy gradient theorem follows from the average-reward policy gradient theorem[2] . [1]Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. [2]Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approxiamation. Advances in neural information processing systems, 12, 1999

  2. Rt,LR_{t,L} in Eq.~(59) is defined in Appendix C.1; the index (t,L)(t,L) refers to the path segment τt:t+L\tau_{t:t+L} of length LL starting at time tt. It is a residual term that is bounded in LL, i.e.
    E[Rt,L∣st=s,at=a]=O(1)\mathbb E[R_{t,L}\mid s_t=s,a_t=a] = O(1) and converges as L→∞L\to\infty. Consequently it vanishes from the long-run average, Rt,L/L→0R_{t,L}/L \to 0, so it does not affect ρu=F(μθ)\rho^u = F(\mu_\theta). It does, however, remain in the relative value qτq^\tau, which collects all O(1)O(1) terms. Only its state--action-dependent part enters the advantage, and hence the policy gradient; a constant part cancels. We have added a pointer to Appendix C.1 after Eq. (59).

  3. We thank the reviewer. These terms are defined in context already, and we have made the definitions explicit here: (i) The \emph{stochastic fluctuation of the empirical occupancy measure} (line 348) is the deviation μ^t,L−μθ\hat\mu_{t,L}-\mu_\theta of the window occupancy from the stationary one; we now state this symbol at first use. (ii) \emph{Finite-memory pattern-count utilities} (line 377) are defined in the same sentence as occupancy functionals of length-kk windows, with the ABB count as an example. (iii) The \emph{canonical path-level representatives} (line 363) are the scaled occupancy functionals u(τ)=T F(μ^T)u(\tau)=T\,F(\hat\mu_T): every long-run objective Ju(θ)=F(μθ)J^u(\theta)=F(\mu_\theta) is realized at the path level by this utility.

We thank the reviewer. We have expanded the remark( line 371-377) after Theorem 3. It now lists all assumptions of the theorem, explains why the representation in Eq. 59 is not an additional assumption, and summarises why the only additional condition, Eq. 86, holds for the utility classes discussed before the theorem. Theorem 3 relies on the same assumptions as Theorem 2. Ergodicity is the standard assumption of average-reward RL, and smoothness of FF holds for all objectives considered in the paper. The representation in Eq. 59 is not an additional assumption: it follows from viewing the trajectory utility as the path-level form of F(μ)F(\mu), where Ju=lim⁡T→∞1T Δut(T)=F(μθ)J^u=\lim_{T\to\infty}\frac{1}{T}\,\Delta u_t(T) = F(\mu_\theta).

  1. The incremental utility is Δut(L)\Delta u_t(L), defined in Eq. 23: the utility accrued by the path segment τt:t+L\tau_{t:t+L} of length LL starting at time tt. Substituting it into Eq. 25 gives the relative value function qτq^\tau used in AUAC, i.e.\ the limit as L→∞L\to\infty of the expected centred incremental utility Δut(L)−ρuL\Delta u_t(L) - \rho^u L given (st,at)(s_t,a_t). So yes, Eq. 25 defines a differential value function, but as a generalization rather than a redefinition: for an additive utility, Δut(L)=∑i=tt+L−1ri\Delta u_t(L)=\sum_{i=t}^{t+L-1} r_i, and qτq^\tau coincides with the classical differential value function. For non-additive uu, qτq^\tau is its natural path-level analogue.

  2. This is the main motivation of the paper. Estimating quq^{u} requires the proxy reward rθur^u_\theta, which presupposes that the trajectory utility is representable as a functional F(μ)F(\mu) of an occupancy measure and that FF is known explicitly. In that case, we have shown how to construct rθur^u_\theta and the associated quq^u (see Theorem 2), and one can use a proxy-reward actor-critic, which we include as a baseline.

In many applications, however, FF is unknown: the utility is only available as a black box, e.g.\ human feedback on a whole trajectory, which can be queried but not decomposed into per-step rewards or differentiated with respect to μ\mu. Then rθur^u_\theta, and hence quq^u, cannot be constructed, whereas qτq^\tau is defined directly from u(τ)u(\tau) and can be estimated from observed trajectory utilities alone. This is the setting AUAC is designed for.

Reviewer_kz5XOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies long-run path dependent utility in continuing ergodic MDPs. The objective is not restricted to an additive per-step reward. The paper assumes that the objective can be written as a functional of the stationary occupancy measure. When this functional is known, the authors construct a policy dependent proxy reward. They use it to derive a policy gradient theorem and propose ProxyAC. When the functional is unknown, they use utility increments from continuous trajectories to define a trajectory based differential q-function. They then propose AUAC, which learns from trajectory level utility feedback.

Critical strengths
  1. The paper gives a useful theoretical framework for policy gradients with path dependent objectives. The proxy reward connects trajectory-level utility to standard average reward actor-critic methods.
  2. AUAC can learn from scalar trajectory level utility increments without knowing the utility functional or using an explicit per-step reward.
Critical weaknesses
  1. The generality of the main results is unclear. The unknown functional result requires Eq.29, but the paper does not clearly state which path dependent utilities satisfy this condition.
  2. The empirical validation is limited to a small two state MDP and one queue control task. AUAC also suffers from finite window bias and variance.
Questions for authors
  1. Could the authors reorganize the paper to make the main logic easier to follow? In particular, the paper could use a clearer structure: (1) problem setup and assumptions, (2) a unified theory section for the known and unknown functional cases, (3) algorithms, and (4) experiments. The current presentation introduces APDU and occupancy measures in several places and separates closely related theory and algorithm sections.
  2. Does Eq.29 hold for all utility functions considered in the paper, or is it an additional restriction? Can the authors characterize when it holds and give examples where it fails?
  3. The theory uses an infinite-horizon limit, but AUAC uses a finite window H. Can the authors provide a finite-window error analysis or a sensitivity study over different values of H?
  4. Please clarify the apparent sign and notation inconsistencies between Eq.10 – 12, Eq.25, and Algorithm 1.
4 comments
AuthorsOpenReview ↗

Reply to kz5X: part 1/2

\paragraph{Reply to W1} When Δut(T)=F(μ)\Delta u_t(T)=F(\mu), then Bθ(s,a)=0B_\theta(s,a)=0; when it involves a temporal pattern reward (F(μk)F(\mu^k) where k>1k>1 but we decompose it to degree 1), Bθ(s,a)=Bθ(s)B_\theta(s,a)=B_\theta(s). In both cases, Eq. 29 holds.

\paragraph{Reply to W2} \textbf{Experiments.} Our evaluation follows the practice of theory-oriented work in average-reward RL and convex RL, where small environments with known optima are used so that estimator bias can be measured against ground truth; the queue task adds function approximation. To our knowledge, general-utility objectives under the average-reward criterion have not yet been studied on large-scale tasks. Our claim is the formulation and its analysis, not performance at scale. [1] Wan, Naik & Sutton, “Learning and Planning in Average-Reward Markov Decision Processes”, ICML 2021. [2] Mutti, De Santi, De Bartolomeis & Restelli, “Convex Reinforcement Learning in Finite Trials”, JMLR 24(250), 2023.\ \textbf{Finite-window bias and variance.} Correct. In the limit, qθτ=qθu+Cθ+Bθq^\tau_\theta=q^u_\theta+C_\theta +B_\theta with CθC_\theta constant in (s,a)(s,a), so the gradient is unbiased. With a finite window HH, the critic target deviates from qθτq^\tau_\theta by an (s,a)(s,a)-dependent term, which is the only gradient bias: it is O(1/H)O(1/H) for KL and decays geometrically for ABB. With NN windows per update, the variance of the gradient estimate scales as H/NH/N. Both vanish as H→∞H\to\infty with N/H→∞N/H\to\infty.

\paragraph{Reply to Q1} We have reorganised Section 4 and the related part of Section 6. We also believe the original paper was organised in a reasonable sequence, which closely aligns with your suggestion.

\paragraph{Reply to Q2} Eq. 29 holds for all utilities considered in the paper. The decomposition in Eq. 26 holds in general; Eq. 29 is the additional condition under which the policy gradient theorem (Eq. 30) holds with qθτq^\tau_\theta, and we have added a paragraph before Theorem 3 characterising when it is satisfied. For scaled occupancy functionals, Δut(T)=F(μ^t,T) T\Delta u_t(T)=F(\widehat\mu_{t,T})\,T (KL, entropy, entropy rate, and additive rewards as the linear case), Bθ≡0B_\theta\equiv 0. For finite-memory pattern counts (ABB), Bθ(s,a)B_\theta(s,a) does not depend on aa, so Eq. 29 holds. When BθB_\theta depends on the action, Eq. 26 remains valid but Eq. 30 does not: the gradient computed from qθτq^\tau_\theta acquires the extra term ∑sμθ(s)∑aBθ(s,a) πθ(a∣s)∇θlog⁡πθ(a∣s)\sum_s\mu_\theta(s)\sum_a B_\theta(s,a)\,\pi_\theta(a\mid s)\nabla_\theta\log\pi_\theta(a\mid s).

\paragraph{Reply to Q3} We thank the reviewer for the question. We have carried out this analysis and added it as Appendix F. Because qτq^\tau is estimated by Monte Carlo from trajectory utilities, AUAC splits one long trajectory into NN shorter windows of length HH, so its performance depends on both. On the two-state MDP, where the true gradient and the finite-HH expectation of the estimator are available in closed form, the error separates into two parts: (i) \textbf{Finite-window bias}, which depends only on HH. For the ABB reward (linear in the pattern occupancy) it decays geometrically and is negligible for H≥10H\ge 10. For the KL objective (nonlinear) it decays as O(1/H)O(1/H) and is small for H≥50H\ge 50. (ii) \textbf{Sampling error}, which decreases as 1/N1/\sqrt{N} and, away from the optimum, grows with HH.

The window length HH therefore controls a bias that more data cannot remove, while NN controls the variance. For a fixed budget of NHNH samples, HH should be the smallest value for which the bias is acceptable. In both experiments the expected estimate crosses zero close to θ⋆\theta^\star, so the finite window does not change the direction of the update except in a small neighbourhood of the optimum that shrinks with HH.

AuthorsOpenReview ↗

Reply to kz5X: part 2/2

\paragraph{Reply to Q4} We thank the reviewer for the careful reading. The inconsistencies were real and have been corrected as follows. Equation numbers below refer to the original submission. (i) \textbf{Sign (former Eqs. 10-11).} The former Eq. 11 had the two terms of the utility increment in the opposite order to the former Eq. 10. The increment is now written everywhere as later minus earlier, u(τt0:t+T)−u(τt0:t)u(\tau_{t_0:t+T}) - u(\tau_{t_0:t}). With this correction, Eq. 25, the critic target in Algorithm 1 (increment minus rate times window length), and the ascent step of the actor are all sign-consistent. (ii) \textbf{Definition of the objective (former Eqs. 11-12).} Ju(θ)J^u(\theta) was defined twice. It is now defined once, as Ju(θ):=lim⁡T→∞1TEθ[u(τt:t+T)]J^u(\theta) := \lim_{T\to\infty}\frac{1}{T} \mathbb E_\theta [u(\tau_{t:t+T})], and the incremental form follows as an equivalent expression with the reason stated. The argument of uu is always a path segment τa:b\tau_{a:b}. (iii) \textbf{Increment symbol (former Eq. 10 vs. Eq. 25 and Algorithm 1).} The increment was written as Δtu(T)\Delta_t u(T) in the former Eq. 10 and as Δut(T)\Delta u_t(T) elsewhere. We now use Δut(T)\Delta u_t(T) throughout. (iv) \textbf{Window length (Algorithm 1).} Line 5 queried Δuti(L)\Delta u_{t_i}(L) with an undefined LL, while the target in line 8 subtracted HρuH\rho^u. Both now use the window length HH. (v) \textbf{Limit versus batch length (Eq. 25 vs. Algorithm 1).} TT denotes the limit variable in Eqs. 10-12 and Eq. 25, but the finite batch length NHNH in Algorithm 1. We now state explicitly that the algorithm uses a finite window HH in place of the limit in Eq. 25. (vi) In Algorithm 1, the estimated APDU is denoted as ρu\rho^u and the empirical APDU is denoted as ρ^u\hat{\rho}^u .

Thank you for the clarifications and additional analysis, which address several of my concerns. Could you give a simple example where Eq. 29 fails while the other assumptions hold?

Thank you for the question. The simplest case is u(τT)=F(μ^T) T+r~(s0,a0)u(\tau_T)=F(\hat\mu_T)\,T+\tilde r(s_0,a_0). The first term can be any utility discussed in the paper, such as the average reward or the KL divergence; the second is a transient reward that depends only on the initial pair (s0,a0)(s_0,a_0). This term does not affect the objective ρu\rho^u, but it can bias the gradient computed from qθτq^\tau_\theta: it gives Bθ(s,a)=r~(s,a)B_\theta(s,a)=\tilde r(s,a) in Eq. 26, so Eq. 29 is not guaranteed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.