- 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
-
Optimizing trajectory-level, non-Markovian utilities in continuing tasks from black-box incremental feedback , without restarting the evaluator, is well motivated (e.g., preference-style feedback on long-running systems). The decomposition , whose curvature term (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.
-
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
-
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, . APDU is therefore average-reward RL with a history-dependent reward ; 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 .
-
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, . Because the differential -function depends only on the reward minus its gain, both rewards yield identical and . 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, is degree-1 homogeneous, so and the two methods coincide exactly.
-
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 , so no experiment covers the motivating case where 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).
- The presentation needs careful proofreading.
-
Typos, e.g., “piθ” (Section 1) and “addtion” (Theorem 3).
-
Redundant appearances. The quantity 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
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, . 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 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
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 (e.g. it does not support ), 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 score terms by a single utility of scale , 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.
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 F (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 q-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 F 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 is the empirical occupancy of a length-T trajectory and μθ is the stationary occupancy of πθ. For an unscaled utility this vanishes as T→∞, consistent with their remark; for our trajectory utility TF(μ^T) the constant Cθ 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 q-function; the fact that Cθ is the same for all (s,a) and therefore drops out of the advantage; and the state-action-dependent transient Bθ(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 F: 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 F only so that the optimum is available and the ∇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 ρ); 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 u 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 H, as our analysis predicts.\\
\paragraph{Reply to W4} Thank you. We have corrected these flagged typos.