Tackling Decision Processes with Non-Cumulative Objectives using Reinforcement Learning

We thank the reviewer for their time and valuable feedback. We now comment on the points raised: **[...]they do not address whether the state and action-spaces are or can be finite/infinite, if there is a restriction on the type of policy that can be used (stationary, stochastic, etc.), as well as whether there are implications of their framework being used in off-policy settings. Because of this, the extent to which their framework can be utilized is unclear.** Our framework maps a general NCMDP to a corresponding MDP. Then, any standard method can be used to solve the corresponding MDP. Thus, our framework is completely flexible and agnostic to the type of action space or employed policy. The only limitation we state in the 'Preliminaries' is that we restrict ourselves to an episodic setting (although this could potentially be extended, see reply to reviewer cuNK). 1) The choice of action space is therefore completely arbitrary. In particular, finite, infinite, discrete, and continuous action spaces are supported. 2) The type of policy depends on which solver is chosen to solve the corresponding MDP. In this sense, any type of policy is possible as long as it accommodates the action space of the corresponding MDP (which is the same as the action space of the underlying NCMDP). 3) Our framework can be used in off-policy settings, as long as an off-policy algorithm is chosen to solve the corresponding MDP. We now emphasize this in the conclusion by adding 'As our method is agnostic to the algorithm used to solve the resulting MDP, it works for arbitrary action spaces and in conjunction with both off- and on-policy algorithms.' **'My second concern is related to the experiments. In particular, the comparison of non-cumulative objectives to the cumulative objects seems unintuitive, given that no-where in the paper do the authors claim the non-cumulative objectives are better than the cumulative objectives. Rather, it would be more intuitive, and consistent with the rest of the text, if the experiments showed that the proposed methods indeed are able to find the optimal policy for the non-cumulative objective. As such, it would appear that the experiments in the current draft of the paper do little to support the claim that the proposed methods can be used to optimize non-cumulative objectives.'** The experiments we present are examples of real world problems with a non-cumulative objective that is established and clearly defined by the respective research communities (e.g. maximize the Sharpe ratio in finance, find the state with lowest cost function reachable from the inital state in discrete optimization). However, in the absence of a method to solve general NCMDPs, these real-world problems have previously been tackled by standard MDPs that can only approximate the true objective (differential Sharpe ratio approximates the non-cumulative Sharpe ratio in finance, sum of cost differences approximates the maximum cost reduction in discrete optimization problems). As such, these previous state-of-the-art methods provide a reasonable baseline to compare our method to. There are also two other types of experiments in the manuscript: 1) As suggested by the reviewer: Apply our method in a simple setting where the optimal policy is known and show that our method finds the optimal policy. We show such a proof-of-principle experiment in Figure 2, and demonstrate that our method (paired with dynamic programming as an MDP solver) can successfully find the (in this case known) optimal policy (see Figure A1, and Table A1). We believe that the theoretical foundation of our work is strong enough that further empirical demonstrations on such toy examples are unnecessary. 2) In the new Appendix C, we now also compare our method with the only previous method for solving NCMDPs with objectives other than the max function: The work of Cui et. al. (doi: 10.1109/TMLCN.2023.3285543), which is only applicable in deterministic settings in conjunction with Q-learning based methods and a more restrictive class of functions $f$ than our method. We find that even in this restricted setting, our more general method slightly outperforms the method of Cui et. al. (see Appendix C for details). **'What are the off-policy implications of this method?'** See our answer above: Our method is compatible with off-policy methods, since the choice of MDP solver is completely flexible. **'A regular average would appear to be a common and useful non-cumulative objective to include in the paper. Was there a reason that it was not included?'** Thanks for pointing this out. There was no specific reason. In fact, we now include this objective in Table 1. It could be interesting in settings where the agent can influence the trajectory length by its actions.

We thank the reviewer for their time and valuable feedback. **'[...] $f$ is defined as a function on $\\mathbb{R}^T$. But later on, the authors also use notations like $f(r_0, \\dots, r_t)$, where $f$ should be treated as a function on $\\mathbb{R}^t$. I think it may be helpful to define $f$ as a function of a set.'** We thank the reviewer for pointing out this source of possible confusion and agree that $f$ should be defined more rigorously. However, set functions are not applicable, since sets have no notion of order and do not support duplicate elements. Thus, we define $f$ as a family of functions and add after Equation (2): '[...], we require $f$ to be a family of functions consisting of a function $f_t : \\mathbb{R}^t \\rightarrow \\mathbb{R}$ for each $t \\in \\mathbb{N}$. For brevity, we denote $f_t(\\tilde r_0, \\tilde r_1, \\dots, \\tilde r_{t-1}) = f(\\tilde r_0, \\tilde r_1, \\dots, \\tilde r_{t-1})$.' **'The authors should try to find a classification of functions f with constant-size state adaptions. Even some preliminary results [...] would be helpful.'** We now discuss conditions on $f$ to allow for constant size state adaptions $h_t$ in the new Appendix B: 1) We provide a necessary and sufficient condition for objectives $f$ with constant size additional state information $h_t$ (see Appendix B.1). 2) We also provide a sufficient, but not necessary, condition that is easier to verify and covers a large class of objectives, e.g. all functions in Table 1. Specifically, we consider function families that can be written with a constant $k\in\mathbb{N}$ as $$ f(\\tilde r_0, \\dots, \\tilde r_t) = F\\left(t, b_0, \\dots, b_{k-1}\right), $$ where $F: \\mathbb{R}^{k+1} \\rightarrow \\mathbb{R}$, $$ b_j = b_j(\\tilde r_0, \\dots, \\tilde r_t) =B_j\\big(\\varphi_j(0, \\tilde r_0), \\dots, \\varphi_j(t, \\tilde r_t)\\big), $$ where $\\varphi_j : \\mathbb{R}^2 \\rightarrow \\mathbb{R}$, and $B_j$ is an arbitrary binary operation, such as $+, \\times, \\max, \\min$, and $$ B_j(x_0, \\dots, x_t) = B_j(x_t, B_j(x_{t-1}, B_j(...))). $$ For details and an explicit construction of $u$, $\\rho$, and $h_t$ with dimension $k+1$, see the new Appendix B.2. **'They claim their methods work for arbitrary functions $f$. However, [...] it turns out only for certain choices of $f$ there exist fix-size $h_t$'** Our method works for arbitrary functions by appending all past rewards to the state. This is a realistic possibility as the state space grows exponentially with the trajectory length, but the representation of a single state grows only linearly and reinforcement learning methods have successfully been applied to a variety of problems with inherently exponentially large state spaces (e.g. Chess, Go). Of course, finding constant size $h_t$ can improve the efficiency of our method. **'The authors should compare their methods with prior works on the control of NCMDPs with a specific choice of objectives and I am curious if the proposed method (which is more general) can produce comparable performances.'** In the new Appendix C, we compare our method with the only previous method for solving NCMDPs with objectives other than the max function: The work of Cui et. al. (doi: 10.1109/TMLCN.2023.3285543). Specifically, we consider the problem of traversing a grid with deterministic rewards on each tile together with the minimum objective. We find that even in this restricted setting, our more general method slightly outperforms the method of Cui et. al. (see Appendix C for details). **'Can the proposed mapping of NCMDPs to MDPs be generalized to infinite-horizon MDPs? (when is defined as a function of set.)'** We believe that any algorithm used to solve infinite-horizon MDPs could, in principle, be used to solve the corresponding MDP of an infinite-horizon NCMDP. However, a full proof would require checking the convergence of the now infinite sums in the proof of Theorem 1. For example, optimizing the average Sharpe ratio in an infinite horizon NCMDP seems like a reasonable application. **'[...]I am curious whether there are some connections with the framework called MDPs with latent dynamics (see [1], [2]).'** We are not sure whether the following answers your question. Please clarify, if not. In the following, we understand MDPs with latent dynamics as in source [1] to be 'episodic MDPs with rich observations generated from a small number of latent states'. Consider an NCMDP with a corresponding MDP where we append all previous rewards to the state, i.e., $h_t = [\tilde r_0, \dots, \tilde r_{t-1}]$. Consider also a second MDP corresponding to the same NCMDP with a lower dimensional extra state information $h_t^\prime$ (e.g. $h_t^\prime \in \mathbb{R}$). In the context of MDPs with latent dynamics, $h_t$ can now be seen as part of a 'rich observation' (i.e. an observation containing redundant information) governed by the latent variable $h_t^\prime$.

We thank the reviewer for their time and valuable feedback. We now comment on the points raised: **'[...] The paper gives very specific examples of construction of $u$ and $\rho$ that allows an efficient reduction from NCMDP to MDP of small augmented state size. Can you give examples of more general classes of non-cumulative objective function that induces $h_t$ that is of reasonably small dimensions?'** We now discuss conditions on $f$ to allow for constant size extra state information $h_t$ in the new Appendix B: 1) We provide a necessary and sufficient condition for objectives $f$ with constant size additional state information $h_t$. Namely, that we can write $$f(\\tilde r_0, \\dots,\ \tilde r_t) = \\rho^\\prime\\left(\\tilde r_t, u^\prime\\left(\tilde r_{t-1}, u^\\prime\left(\\tilde r_{t-2}, ...\\right)\\right)\\right),$$ with $\rho^\\prime: \\mathbb{R}^{k+1} \\rightarrow \\mathbb{R}$ and $u^\\prime: \\mathbb{R}^{k} \\rightarrow \\mathbb{R}$, where $k+1 \\in \\mathbb{N}$ is the dimension of $h_t$. This can be seen as an extension of the optimal substructure condition used by Cui et. al. (doi: 10.1109/TMLCN.2023.3285543). 2) We also provide a sufficient, but not necessary, condition that is easier to verify and covers a large class of objectives, e.g. all functions in Table 1. Specifically, we consider function families that can be written with a constant $k\\in\\mathbb{N}$ as $$ f(\\tilde r_0, \\dots, \\tilde r_t) = F\\left(t, b_0, \\dots, b_{k-1}\\right), $$ where $F: \\mathbb{R}^{k+1} \\rightarrow \\mathbb{R}$, $$ b_j = b_j(\\tilde r_0, \\dots, \\tilde r_t) = B_j\\big(\\varphi_j(0, \\tilde r_0), \\dots, \\varphi_j(t, \\tilde r_t)\\big), $$ where $\\varphi_j : \\mathbb{R}^2 \\rightarrow \\mathbb{R}$, and $B_j$ is an arbitrary binary operation, such as $+, \times, \max, \min$, and $$ B_j(x_0, \\dots, x_t) = B_j(x_t, B_j(x_{t-1}, B_j(...))). $$ For example, if $B_j$ is the multiplication operation, $B_j(x_0, \\dots, x_t) = \\prod_{i=0}^{t} x_i$. For details on the explicit construction of $u$, $\\rho$, and $h_t$ with dimension $k+1$, see the new Appendix B.2. **'[...] the paper only shows a list of examples of special examples of and does not specify how to construct and for arbitrary function in general, and does not provide an bound to the resulting state dimensions, which at worst case must contain the set of all historical rewards.'** We agree that this is a limitation of our work. However, we partially resolved it (see previous answer). Moreover: 1) When appending all past rewards to the state, the state space grows exponentially with the trajectory length, but the representation of a single state grows only linearly. Reinforcement learning methods have succesfully been successfully applied to a variety of problems with inherently exponentially large state spaces, but modest trajectory lengths (e.g. Chess, Go). Therefore, appending all past rewards to the state may not be limiting in some problems (though it may be in others). 2) Even only the functions specified in Table 1 are of interest to large reinforcement learning communities (finance, discrete optimization). **'[...] the paper compares their method of MDP reduction (with modified state and reward) with an RL agent with cumulative objective. This does not seem like a very fair comparison given the cumulative objective will be the wrong objective in each of these environments, and it is clear that correct specification of the objective will lead to better performance.'** We agree, and the fact that, using our method, it is now possible to specify the correct objective to an RL algorithm is a main advancement of our paper: 1) In the absence of a method for solving general NCMDPs, the real-world problems we consider in the experiment section have so far been solved by standard MDPs that only approximate the true objective (differential Sharpe ratio approximating non-cumulative Sharpe ratio in finance, sum of cost differences approximating maximum cost reduction in discrete optimization problems). As such, these previous state-of-the-art methods provide a reasonable baseline against to compare our method. 2) We also show a proof-of-principle experiment in Figure 2, and demonstrate that our method (paired with dynamic programming as an MDP solver) can successfully find the (in this case known) optimal policy (see Figure A1, and Table A1). 3) In the new Appendix C, we now also compare our method with the only previous method for solving NCMDPs with objectives other than the max function: The work of Cui et. al. (doi: 10.1109/TMLCN.2023.3285543), which is only applicable in deterministic settings in conjunction with Q-learning based methods and a more restrictive class of functions $f$ than our method. We find that even in this restricted setting, our more general method slightly outperforms the method of Cui et. al. (see Appendix C for details).

We thank the reviewer for their time and valuable feedback. We now comment on the points raised: **'It seems to me that if the update function u of definition 1 is a constant function, no information is preserved and the constructed MDP could not have the same value function as the NCMDP. Is this right? If it is, this sort of choice should be excluded in definition 1.'** We think there may be a slight misunderstanding: We only claim that if Definition 1 is satisfied, Theorem 1 holds. However, Definition 1 is not generally satisfied for all $u$ and $\rho$. To your comment: If $u$ is chosen as a constant function, then $h_t$ is also constant, and Eq. (3), i.e., $r_t = \rho(\tilde r_t, h_t)$ cannot be satisfied for any $\rho$. Therefore, a constant $u$ is already excluded by Definition 1. **'Later in the same paragraph, the authors note that an h_t recording all reward history is sufficient to construct an MDP but the state space is exponentially large so there must be some tradeoff between state space and "Markovness". How much information can be lost from the full history before we lose the Markov condition? Is there a characterisation of the functions u that satisfy this property?'** 1) All functions $u$ satisfying Definition 1 preserve full 'Markovness', so our scheme always chooses 'Markovness' in the trade-off between 'Markovness' and size of the state space. 2) It is an interesting question to ask which functions $f$ allow (small) constant size extra state information $h_t$. We now discuss some results related to this in Appendix B: Specifically, we provide a necessary and sufficient condition for objectives $f$ with constant size additional state information $h_t$. However, this condition might be difficult to check in practice. Therefore, we also provide a sufficient, but not necessary, condition that is easier to verify and covers a large class of functions, e.g. all functions in Table 1. For functions in this class, we also provide an explicit construction of $u$, $\rho$, and $h_t$. See Appendix B for details. 3) When appending all past rewards to the state, the state space grows exponentially with the trajectory length, but the representation of a single state grows only linearly. Reinforcement learning methods have succesfully been applied to a variety of problems with inherently exponentially large state spaces, but modest trajectory lengths (e.g. Chess, Go). Therefore, appending all past rewards to the state may not be limiting in some problems (though it may be in others). **'The variables u, h and $\rho$ are discussed in the paragraph following the statements of equations 3,4,5. You should introduce them before [...] I suggest the statement of theorem 1 be rearranged to: assumptions then conclusion, instead of the current: assumption then conclusion then more assumptions.'** We prefer to first give the rigorous (and already self-contained) definition of these variables in Definition 1, and then provide intuition for this definition after that (note, that there are no additional assumptions after Definition 1). Finally, we present the result (Theorem 1) that builds on this definition. Ultimately, the choice of this structure is, of course, highly subjective. However, we agree that the discussion about constant size extra state information should not interrupt the argument between Definition 1 and Theorem 1 and moved it to the end of the theory section. **'[...]Also, their description is too vague. For example "This can be achieved by extending the state space with ht , which preserves all necessary information about the reward history" does not give me a good sense of what the function u should be.[...]'** The functions and variables are rigorously defined in Definition 1. The description in the paragraph after Definition 1 is simply to provide intuition. We agree that a more concrete statement would be desirable. However, this is unfortunately not possible for general $f$. Therefore, we moved the example with the minimum function right after this statement in the updated manuscript. We also provide many examples in Table 1 (second row defines $u$, third row defines $\rho$). Additionally, we now provide a construction of $u$, $\rho$, and $h_t$ for a large class of objectives in Appendix B.