The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes

We thank the reviewer for the positive review, comments, and concerns raised. We answer below the questions/concerns raised:

• "Line 377 (left): "Both $K$ and $H$ contribute to the tightness of the upper bound." However, under Theorem 4.3, the authors mention that "Finally, the upper bound does not get tighter as $H$ increases, for fixed $K$." I may have missed something, but I would like to hear the authors' comments on this.": The aim of our work is to show that the number of trials, $K$, matters. In the context of discounted GUMDPs, to analyze the mismatch between the finite and infinite trials settings, we introduced a truncated estimator (equation 5) that depends on $K$, the number of trajectories, but also on $H$, the length of the sampled trajectories. With our comment after Theo. 4.3. ("the upper bound does not get tighter as $H$ increases, for fixed $K$"), we wanted to emphasize that the number of trials $K$ is the key parameter regulating the tightness of the bound, i.e., even if $H$ is "very high" so that the bias term $2\gamma^H$ is very small, if $K$ is low then we expect the upper bound to be loose; then, if we gradually increase $K$, the upper bound tightens with a rate of $1/\sqrt{K}$. I.e., setting $H$ to be high alone will not make the upper bound tight. However, naturally, for a fixed $K$, increasing $H$ makes the bias of the estimator to decrease and, hence, we write while commenting our experimental results that "both $K$ and $H$ contribute to the tightness of the upper bound.". However, this should not distract us from our key objective, which is to show that $K$, the number of trials, matters irrespective of the value of $H$. Our experimental results illustrate this (Fig. 2): for any fixed $K$, increasing $H$ decreases the bias of the estimator, but the gap between the infinite and finite trials formulations only disappears if $K$ is sufficiently high (as well as $H$ so that the bias is low). We commit to making this clearer in the final version of our manuscript.
• "Line 425 (left): It would be helpful if the authors could demonstrate how the equality holds for $\mathcal{M}_ {f,2}$.": The intuition is that, for $\mathcal{M}_{f,2}$, the distribution of initial states is such that the agent always starts in $s_0$. Now, if the policy is stochastic in both states $s_0$ and $s_1$, it happens that the Markov chain induced by such a stochastic policy comprises a single recurrent class ($s_1$ is always reachable from $s_0$ and vice versa) and, hence, there exists no mismatch between the infinite and finite trials objectives (in light of our Theo. 4.4). Finally, for any deterministic policy, it happens that the agent always gets absorbed with probability one to the same recurrent class and, thus, the mismatch between the finite and infinite trials formulations fades away. More precisely, the only case where it is possible to have two recurrent classes is when the deterministic policy selects the right action in state $s_0$ and the left action in state $s_1$. However, since the agent always starts in $s_0$, recurrent class {$s_1$} is unreachable and, hence, there exists no mismatch between the finite and infinite trials formulations. This result agrees with our Theo. 4.6 since the probability of getting absorbed into one of the recurrent classes is one and the probability of getting absorbed to the other is zero and, hence, the lower bound is zero. We commit to making this clearer in the final version of our manuscript.

We hope our answers addressed the reviewer's main concerns.

We thank the reviewer for the positive review, comments, and concerns raised. We answer below the questions/concerns raised:

• "In Fig 3b, it looks like there are some discontinuities in the performance of around where the finite-trail performance seems to diverge away from the infinite-trail one, but then converges back to it. Is that expected from theoretical analysis?": In Fig 3 (b), in the right-most plot, we agree that there appear to exist some kind of discontinuities since, as $\gamma$ increases, some curves appear to start deviating more and more from the dashed line (infinite trials curve), eventually converging back together as $\gamma \approx 1$. We carried out a detailed analysis as to why this is the case and realized that this happens due to a particular interaction between the occupancy induced by the policy as we increase $\gamma$ and the objective function. Whether these discontinuities may appear depends on the particular GUMDP instance at hand and the policy considered. For example, as seen in Fig. 3 (b) for the other two GUMDPs, the trend is different as the mismatch fades away as $\gamma$ increases. Nevertheless, all the results in Fig. 3 (b) agree with our theoretical results: (i) for the discounted case $\gamma <1$, there exists, in general, a mismatch between the finite and infinite trials formulations, which fades away as the number of trajectories $K$ increases; and (ii) for the average setting ($\gamma \approx 1$), the finite and infinite trials formulations are equivalent since the noisy transition matrices enforce that the underlying GUMDPs have a single recurrent class (hence, being unichain) under the considered policies. Unifying the analysis of the discounted and average settings is beyond the scope of our work, and we envision several technical challenges will arise; even for the case of linear objectives/MDPs, such analysis can be challenging (e.g., the theory of Blackwell optimality).

We hope our answers addressed the reviewer's main concerns.

We thank the reviewer for the positive review, comments, and concerns raised. We answer below the questions/concerns raised:

• "Minus sign in the definition of the expected discounted cumulative reward": We focused on the case of minimization (hence, convex $f$), similarly to what has been done in previous works (e.g., [1]). It is equally possible to consider the problem of maximization (hence, concave $f$), as, naturally, both formulations are equivalent.
• "It should be $\pi^* \in \arg \min$ instead of $\pi^* = \arg \min$ since is the set of all possible optimal policies.": We agree with the reviewer and will fix this in the new version of the manuscript.
• "Redundant definition of item (i) before and after equation (3)": We thank the reviewer for the suggestion. We will incorporate it into the final version of our manuscript.
• "In equation (3), is the minimum always attained, even among Markovian policies?": Under the average multichain setting, the set of possible occupancies attained by all Markovian (possibly non-stationary) policies corresponds to the closed convex hull of a given set of points (Theo. 8.9.3. in [2]). Thus, the minimum is always attained.
• "Also, can you provide a reference here again for the optimality of stationary policies for the case of discounted GUMDPs + average unichain GUMDPs?": We thank the reviewer for the suggestion. We will add a reference to the results in [2] that are of relevance.
• "Recall the definition of $\zeta_\pi$": We thank the reviewer for the suggestion. We will incorporate it into the final version of our manuscript.
• "Line 212: is the convergence $f_{K,H} = f_K$ as $H \rightarrow \infty$ uniform over $\pi$": Yes.

We hope our answers addressed the reviewer's main concerns.

[1] - Zahavy, T., O’Donoghue, B., Desjardins, G., and Singh, S. - Reward is enough for convex mdps. CoRR (abs/2106.00661), 2021.

[2] - Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.

We thank the reviewer for the comments and concerns raised. We answer below each of the questions/concerns raised:

• "(1) Which aspects are identical to [1] and which parts of the extension present significant challenges.": We thank the reviewer for asking about the differences between our article and [1], particularly regarding the technicalities of our results and proofs. Our analysis fundamentally differs, from a technical point of view, from that in [1] where the authors consider the finite-horizon case. The key difference is due to the fact that discounted and average occupancies are inherently different than occupancies induced under the finite-horizon setting. The fact that the occupancies are defined over trajectories of infinite length forced us to seek alternative ways to prove our results. This is because we are mostly worried about the long-term behavior of the Markov chain induced by the policy, and not focused on a fixed number of interaction steps as considered in [1].

  The kind of results we provide also significantly differ from those in [1]: we are the first work to provide lower bounds on the mismatch between the finite and infinite trials objectives, as [1] only proves upper bounds in the context of policy optimization. Also, while [1] shows that, in general, there exists a mismatch between the finite and infinite trials formulations under finite-horizon settings, we prove a result that states that under certain conditions (the GUMDP being unichain), there exists no mismatch. Hence, the nature of our results and those in [1] greatly differ.

  Finally, although Theo. 4.3. is indeed related to Theo. 2 in [1], we focused on the policy evaluation case and had to incorporate the fact that the trajectories are discounted. All our other theorems (Theo. 4.1, 4.2, 4.4, 4.5, and 4.6) are not connected at all to any result in [1], relying on significantly different proof techniques and lines of reasoning than those considered in [1]. For example, Theo. 4.2 and 4.6 rely on the (quite general) strongly convex assumption that was not considered in [1]; Theo. 4.4. relies on multiple Lemmas (Appendix C.2.) related to the study of the ergodicity of the Markov chain induced when conditioning the GUMDP with a given policy.

  We commit to clarify in the final version of the article the novel aspects of our work in comparison to [1].

• "(2) The figure caption states that all GUMDPs have deterministic transitions, yet Figures 1a and 1b depict states with two distinct transitions each. It would be helpful to clarify what these transitions represent.": We apologize for any confusion our visual depiction of the GUMDPs may have caused. We will improve this in the final version of our paper. Essentially, the GUMDPs we depict in Fig. 1 all have deterministic transitions. In Figs. 1 (a) and 1 (b), the different transitions coming out of the state nodes encode the transitions associated with each of the two actions (we commit to explicitly adding the action labels to the arrows to make it clearer). Finally, in the experimental section of our work (Sec. 4.3), we considered stochastic variants of the GUMDPs depicted in Fig.1. We consider the same GUMDPs as depicted in Fig. 1, but add a small amount of noise to the transition matrices so that there is a non-zero probability of transitioning to any other arbitrary state. Naturally, for the case of noisy transitions the visual depiction of the GUMDPs would be slightly different as the transitions are now stochastic, but we decided to present only the illustration of the GUMDPs for the case of deterministic transitions to make the illustrations easier to parse.

We hope our answers addressed the reviewer's main concerns.

We thank the reviewer for the comments and concerns raised. We answer below the questions/concerns raised:

• "Is there a way to justify looking at this problem given that the infinite horizon setting is an idealization and the whole motivation is to move closer to realism?": We agree and acknowledge that the reviewer raises a relevant point, which leads to an interesting discussion. Still, we argue that there are key differences between the finite and infinite-horizon formulations and, therefore, we should see them as being complementary to each other.

  First, the infinite-horizon setting has been thoroughly considered by previous works in the literature of GUMDPs/convex RL (e.g., [1] considers both discounted and average settings). Therefore, it is of great interest to make the research community aware that the infinite-horizon GUMDPs framework hides some implicit assumptions (infinite trials assumptions), and that the performance of a trained agent may significantly deviate (as we study in this work) at test time in comparison to the expected one. We also highlight that such a mismatch between the finite and infinite trials has been overlooked by previous research, as we describe in our Introduction.

  Second, we argue the infinite-horizon framework is inherently different from the finite-horizon one and, thus, both should be studied in the context of GUMDPs (and, particularly, in the finite-trials regime). This is because infinite-horizon formulations allow to induce certain orders of preference over policies that are not so easily induced under a finite-horizon formulation. For example, one may want to use discounting to tradeoff between earlier/later costs/rewards (or in the case of GUMDPs, between the "importance" of states that are visited earlier or later in the trajectories). Also, infinite-horizon discounted GUMDPs can be used to model finite-horizon tasks where the length of the episode is uncertain (Sec. 5.3 in [2]). Therefore, we strongly believe that previous research adopted infinite-horizon formulations not only for their potential to simplify analysis (e.g., in the discounted setting, stationary policies are optimal) but also because they fundamentally differ from finite-horizon formulations in problem modeling, as exemplified above. Moreover, infinite-horizon formulations do not always simplify the problem yet remain widely used—e.g., in MDPs, the analysis of the average setting is arguably more intricate than the finite-horizon case. In conclusion, we view finite- and infinite-horizon formulations as complementary, both warranting study.

• "Should we care about infinite-finite trials gap described?" We argue that yes, we should care. For example, let us consider the single-trial case ($K=1$), which is very relevant in real domains where the agent may only be able to interact with the environment once (e.g., a robot/agent only has one life). In this case, the gap between the finite and infinite trials formulations can be significant, as our results showcase (constant $1/\sqrt{K}$ will not play a role here as it equals one). Even though our focus in this paper was on the task of policy evaluation, we agree with the reviewer that policy optimization in the single-trial setting is harder than in the case of infinite trials. However, we conjecture and have some preliminary evidence that it is, indeed, possible to do much better than the infinite trials policy in a reasonably efficient fashion for the single-trial setting. We leave such a study for future work.

• "On running experiments with $H = \infty$:" As suggested by the reviewer, in practice, it is impossible to draw trajectories of infinite-length. With this in mind, when running our experiments, we tuned $H$ so as to mitigate the impact of trajectories' truncation in our experimental results. We did this by running our experiments with "sufficiently high" $H$ values and plotting the values of the objectives as we increase $H$ and looking at how fast the curves were stabilizing (similar to the curves in Fig. 2). This allowed us to have a good confidence that the picked $H$ makes the impact of trajectories' truncation negligible.

We hope our answers addressed the reviewer's main concerns.

[1] - Zahavy, T., O’Donoghue, B., Desjardins, G., and Singh, S. - Reward is enough for convex mdps. CoRR (abs/2106.00661), 2021.

[2] - Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.

We thank the reviewer for the comments and concerns raised. We answer below the questions/concerns raised:

• "Have the authors considered how their theoretical results hold when relaxing assumptions on utility function convexity or continuity, which might often be violated in real-world scenarios?'' We thank the reviewer for raising the discussion on how our assumptions may limit the generality of our results. Our assumptions remain valid under the great majority of objectives in the convex RL/GUMDPs literature and, hence, our results readily apply to many different tasks such as maximum state entropy exploration or imitation learning. We address each of our assumptions below:

  1. Strongly convex objectives: We require the strong convexity assumption to prove the lower bounds of Theo. 4.2 and 4.6. All objective functions we consider in our work, which we believe to be representative of common objective functions used in the literature (e.g., maximum state entropy exploration, imitation learning, etc.), satisfy this assumption. We refer to Appendix C for the proofs of strong convexity. Naturally, if the objective is linear, as is the case for standard MDPs/RL, the objective function is not strongly convex; however, it should be clear that in such a case there does not exist a mismatch between the finite and infinite trials objectives and, thus, proving bounds on the mismatch between the objectives is meaningless. Finally, if our convexity assumptions are not met (e.g., the function is non-convex), we conjecture that the mismatch between the finite and infinite trials continues to exist in general, but we leave the study of such a case for future work.
  2. Continuous and bounded objectives: We use the assumption that the objective is bounded and continuous to prove Theo. 4.4 and 4.6, which rely on the bounded convergence theorem. All objective functions we consider in our work are continuous and, up to the authors' knowledge, this assumption is satisfied for every objective function previously considered in the literature of GUMDPs. Thus, we believe our assumption is as general as it can be. Regarding the boundedness of the objective function, several objective functions (e.g., entropy and norm-based objectives) satisfy this assumption, as we state in our article. In the case of imitation learning tasks with KL-divergence-based objectives, as stated in the text before Theo. 4.4., we need to ensure that occupancy $d_\beta$ (the occupancy induced by the policy we want to imitate) is lower-bounded to meet our assumption. Nevertheless, we argue that: (i) this assumption is commonly used by previous theoretical works; and (ii) in practice, one can ensure the distribution is lower-bounded by adding a small value ($\epsilon$) to every entry of the occupancy. Finally, we highlight that boundedness assumptions are commonly considered in the literature of MDPs/RL.

• "Could the authors provide additional empirical analysis with more realistic, stochastic environments (beyond the simplistic toy examples), to demonstrate clearly the practical significance of their theoretical bounds?"

  1. Simplistic environments/experiments: While our GUMDPs comprise a small set of states, we argue they are representative of several tasks considered by previous works in the literature of convex RL/GUMDPs (we refer to Fig. 1 for a description of our GUMDPs). Also, we aimed to provide the simplest possible GUMDPs/experimental settings to stress the generality of our results, as acknowledged by reviewers 3gey and dxJG. We mainly used our empirical results to validate the theoretical results of our paper, which readily apply to GUMDPs of any dimension under the assumptions stated by each result, which we believe to be general enough to be representative of the great majority of objectives used by previous works.
  2. Experiments with stochastic transitions: We also provide experiments with stochastic transitions in the paper (Fig. 3 (b)) and analyzed how the stochasticity of the transitions impacts our results, connecting our experimental results with the theoretical findings.

We hope our answers addressed the reviewer's main concerns.