The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes
Authors: Pedro Pinto Santos
Alberto Sardinha
Francisco S. Melo
Venue: ICML 2025 spotlightposter (2025)
Keywords: Planning
sequential decision-making
general-utility markov decision processes
convex markov decision processes
Primary area: theory->reinforcement_learning_and_planning

Abstract: The general-utility Markov decision processes (GUMDPs) framework generalizes the MDPs framework by considering objective functions that depend on the frequency of visitation of state-action pairs induced by a given policy. In this work, we contribute with the first analysis on the impact of the number of trials, i.e., the number of randomly sampled trajectories, in infinite-horizon GUMDPs. We show that, as opposed to standard MDPs, the number of trials plays a key-role in infinite-horizon GUMDPs and the expected performance of a given policy depends, in general, on the number of trials. We consider both discounted and average GUMDPs, where the objective function depends, respectively, on discounted and average frequencies of visitation of state-action pairs.  First, we study policy evaluation under discounted GUMDPs, proving lower and upper bounds on the mismatch between the finite and infinite trials formulations for GUMDPs. Second, we address average GUMDPs, studying how different classes of GUMDPs impact the mismatch between the finite and infinite trials formulations. Third, we provide a set of empirical results to support our claims, highlighting how the number of trajectories and the structure of the underlying GUMDP influence policy evaluation.

The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes
Pedro P. Santos 12
Alberto Sardinha 3 Francisco S. Melo
Abstract
the scalar reward function, which expresses the degree of desirability of each state-action pair, allows the encoding of different objectives. MDPs have found wide range of applications in different domains (White, 1988), such as inventory management (Dvoretzky et al., 1952), optimal stopping (Chow et al., 1971) or queueing control (Stidham, 1978). MDPs are also of key importance in the field of reinforcement learning (RI.) (Sutton Barto, 2018) since the agent-enviromment interaction is typically formalized under the framework of MDPs. Recent years witnessed significant progress in solving challenging problems across various domains using RL (Mnih et al., 2015; 5; Silver et al., 2017; Lillicrap et al., 2016). Such results attest to the flexi- bility of MDPs as a general framework to study sequential decision makinn under uncertainty.
The general-utility Markov decision processes (GUMDPs) framework generalizes the MDPs framework by considering objective functions that depend on the frequency of visitation of state- action pairs induced by given policy. In this work, we contribute with the first analysis on the impact of the number of trials, i.e., the number of randomly sampled trajectories, in infinite-horizon GUMDPs. We show that, as opposed to standard MDPs, the number of trials plays key-role in infinite-horizon GUMDPs and the expected per- formance of given policy depends, in general, on the number of trials. We consider both discounted and average GUMDPs, where the objective func- tion depends, respectively, on discounted and aver- age frequencies of visitation of state-action pairs. First, we study policy evaluation under discounted GUMDPs, proving lower and upper bounds on the mismatch between the finite and infinite trials formulations for GUMDPs. Second, we address average GUMDPs, studying how different classes of GUMDPs impact the mismatch between the finite and infinite trials formulations. Third, we provide set of empirical results to support our claims, highlighting how the number of trajecto- ries and the structure of the underlying GUMDP influence policy evaluation.
However, there are relevant objectives that cannot be easily specified within the framework of MDPs (Abel al., 2022). These include, for example, imitation learning (Hussein et al., 2017; Osa et al., 2018), pure exploration problems (Hazan et al., 2019), risk-averse RL. (García et al., 2015), diverse skills discovery (Eysenbach et al., 2018; Achiam et al., 2018) and constrained MDPs (Altman, 1999; Efroni et al., 2020). Such objectives, including the scalar reward objective of standard MDPs, can be formalized under the framework of general utility Markov decision processes (GUMDPs) (Zhang et al., 2020; Mutti et al., 2023). In GUMDPs. the objective is, instead, encoded as a function of the occupancy induced by a given policy, i.e., as a function of the frequency of visitation of states (or state-action pairs) induced when running the policy on the MDP. Recent works have unified such objectives under the same framework and proposed general algorithms solve GUMDPs under convex objective functions (Zhang et al., 2020; Zahavy et al., 2021; Geist et al., 2022). Extensions to the case of unknown dynamics are also provided by the aforementioned works.
1. Introduction
Markov decision processes (MDPs) (Puterman, 2014) pro- vide mathematical framework to study stochastic sequen- tial decision-making. In MDPs, the agent aims to find mapping from states to actions such that some function of the stream of rewards is maximized. The specification of
Despite providing a more flexible framework with respect to objective-specification in comparison to standard MDPs, Mutti al. (2023) show that finite-horizon GUMDPs im- plicitly make infinite trials assumption. In other words, GUMDPs implicitly assume the performance of given policy is evaluated under an infinite number of episodes of interaction with the environment. Since this assumption may
INESS-ID,, Lisbon, Portugal Institutt Superior Técnico, Lis- bon, Portugal PPUC-Rio, Rio Janciro, Brazil. Correspondence to: Pedro P. Santos spedro.pinto. pinto.santosseeeeeeo reccicc.ulisboa.pt..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
be violated under many interesting application domains, the authors introduce modification of GUMDPs where the objective function depends on the empirical state-action oc- cupancy induced over a finite number of episodes. Under the introduced finite trials formulation, the authors show that the class of Markovian policies does not suffice, in general, to achieve optimality and that non-Markovian policies may need to be considered. Finally, the authors suggest that the difference between finite and infinite trials fades away under the infinite-horizon setting.
rule maps the current state to a distribution over actions, i.e., Ty : 8 - (AA) In the case of deterministic Markovian de- cision rules ne S + A instead. A policy = {To, TI....} is a sequence of decision rules, one for each timestep. If, for all timesteps, the decision rules are deterministic or stochastic, we say the policy is deterministic or stochastic, respectively, We denote the class of Markovian policies with HM and the class of Markovian deterministic policies with m A policy is stationary if it consists of the same decision rule for all timesteps. We denote with IIs the set of station- ary policies and with Hy the set of stationary deterministic policies. We highlight that 1ls C Il and 11 C ug.
In this work, we contribute with the first analysis on the impact of the number of trials in infinite-horizon GUMDPs. We show that the number of trials plays a key role in infinite- horizon GUMDPs, as opposed to what has been suggested (Mutti et al., 2023). Such a finding is of interest and rele- vance as: (i) the infinite-horien prevalent settings in the planning/RL. literature and has found important applications in different domains where the lifetime of the agent is uncertain or infinite; and (ii) the assumption that the agent is evaluated under an infinite number of trajectories is usually violated in relevant appli- cation domains. We focus our attention on discounted and average GUMDPs, where the objective function depends on discounted and average occupancies, respectively. We show, both theoretically and empirically, that the agent's s performance may depend on the number of infinite-length trajectories drawn to evaluate its performance, but also on the structure of the underlying GUMDP. Our analysis fun- damentally differs, from a technical point of view, from that in Mutti al. (2023) where the authors consider the case; this is because discounted and average occupancies are inherently different than occupancies in- duced under the finite-horizon setting.
For a given policy т, the interaction between the agent and the environment gives rise to a random process (So, Ao, S1, AI,...... E (8 A)% where the probability of trajectory T = (su, au, $1, $1, a1....) ..) is given by (x(T). In the case of т Ils. we denote with pa the |S| x [S] matrix with elements PM (ssss5' s') = (Awx())s) [p(s'|s, (iss|ss, A)].
setting is one of the most
The infinite-horizon discounted setting The discounted state-action occupancy under policy ι is
(8, = (1 - 7) 1=0
Pr T. (S. 8, A.= a), (1)
where y E [0, 1) is the discount factor and P (S. s, A, = a) denotes the probability of state-action pair (s,a) at timestep when following policy т and Su Po- The expected discounted cumulative re- ward of policy ι can be written as (dy,:=-) where dy = [dy, (so, ao).........................aa.. .... dyys (3]s), [ and r [r(50, (000,a))... ((Is))
We aim to find
n arg (in,, -r) nElls
2. Backkround
Infinite-horizon MDPs (Puterman, 2014) provide a math- ematical framework to study sequential decision making and are formally defined as a tuple M = P,,, r) where: S is the discrete finite state space; AA is the discrete finite action space; : S x A + ASS) is the transition probability function with (SS) being the set of distribu- tions over S, Po E (SS) is the initial state distribution; and r P:Sx x A + IR is the bounded reward function. The interaction protocol is: (i) an initial state So is sampled from Po: (ii) at each step f, the agent observes the state of the environment St E S and chooses an action A₁ E AA. The environment evolves to state S.41 E S with proba- bility p(-|S,, At). and the agent receives a reward R, with expectation given by r(S,, Ar); (iii) the interaction repeats infinitely.
The infinite-horizon average setting action occupancy under policy x is
The average state-
H Σ
dan. (s, a) = lim H 1=
Pr (S:= A: = =a) (2)
H
The expected average reward of policy can be written as (dwg. -r), where davg. [davg ao)..... davg, (51s)) 4[4]]].
The analysis
of the average reward setting depends on the structure of the Markov chains induced by conditioning the MDP on different policies. We say that an MDP is (Puterman, 2014; Altman, 1999):
unichain if, for every и E MT. the Markov chain with transition matrix pa contains single recurrent class
A decision rule n, specifies the procedure for action selec- tion at each timestep t. A stochastic Markovian decision
(a, b) denotes the dot product between vectors a and b.
2

---

The Number of Trials Matters in General- Utility Markov Decision Processes
dg LD
do
do
80
d1
dg
do
2
01
a1
01
01
dgg, (3)
2
(a) M
(b) M
(c) M
Figure 1: Illustrative GUMDPs (M and M are adapted from Mutti et al., 2023). All GUMDPs have deterministic transitions. The objective for M is f(d) (d, log(d)) (entropy maximization), for M is f(d) = KL(d)ds) where is a fixed policy (imitation learning), and for M is f(d) d Ad where A is positive-definit (quadratie minimization).
plus a possibly empty set of transient states. A recur- rent class is an irreducible class where all states are recurrent. An irreducible class is a set of states such that every state is reachable from any other state in the set. state recurrent if the probability of returning to it in the future is one and transient if the probability is less than one. In finite-state Markov chain, all irreducible classes are recurrent.
(Altman, 1999, Theo. 3.2.) and average unichain GUMDPs (Puterman, 2014, Theo. 8.9.4). When f is linear, we are under the standard MDP setting; if f is convex, we are under the convex MDP setting (Zahavy et al., 2021). Finally, is known that the optimal policy may not be deterministic (Hazan et al., 2019; Zahavy al., 2021).
Throughout this paper, make use of the GUMDPs depicted in Fig. 1, which are represen- tative of three common tasks in the convex RI literature.
Illustrative GUMDPs
multichain the MDP is not unichain.
Under both unichain and multichain MDPs we aim to find
3. From Expected to Empirical Objectives for GUMDPs
arg min (dag, r)- TElls
In this section, we introduce multiple objectives for GUMDPs. As opposed to the objective in (3), which de- pends on the expected discounted or average state-action occupancy dx, the objectives herein introduced depend on the empirical discounted average state-action occupancy.
2.1. General-utility Markov decision processes
The framework of GUMDPs generalizes suliit--peciiiiction by allowing the objective of the agent to be written in terms of the frequency of visitation of state-action pairs. This is in contrast to the standard MDPs framework, where the objective of the agent is encoded by the reward function.
We start by considering that the agent interacts with its enviromment over multiple trials, i.e., multiple trajecto- ries/episodes. We denote by K the number of trials. We assume the K trials are independently sampled. As it is gen- erally clear from the context to understand whether we are referring discounted or average empirical occupancies, use d to denote both types of empirical occupancies.
We define an infinite-horizon GUMDP tuple M (8, A. P, Po. f) where S, .A. p, and po defined in simi- lar way to the standard MDP formulation. The objective of the agent is encoded by f (S A) + IR, as a function of a state-action occupancy d. Similar to the case of standard MDPs, d can correspond to: (i) a discounted state-action oc- cupancy d,, as defined in (1), in the case of anfinite-horize discounted GUMDPs; (ii) an average state-action occu- pancy davg. as defined in (2), in the case of infinite-horizon average GUMDPs. The objective is then to find
3.1. Empirical state-action occupancies
Discounted state-action occupancies We introduce dT which denotes the empirical discounted state- action occupancy induced by a set of K trajec- tories TK = .T..... ,xx,, where each Tī (Sk,0, AR.o, Sk.1,AA,1, defined as
π E arg min ((dx): *Ell
(3)
where: (i) dz can either correspond to a discounted or av- erage state-action occupancy depending on the considered setting; and (ii) II A in the case of average multichain GUMDPs and II = IIş in the case of discounted GUMDPs
d (s, a) K E0- Σ
- = =8, =);
(4)
where 1 is the indicator function. In practice, it is common to truncate the trajectories of interaction between the agent and its environment. We denote by E N the length at which the trajectories are truncated, i.e. the length of the
"Since f can be non-linear it may happen that stationary policy does attain the minimum of and, hence, we need to consider the case where π E TTy (Puterman, 2014, p. 402).
3

---

The Number of Trials Matters in Infinite-Horizonn General-Utilie Markoy Decision Processes
sampled trajectories. We then introduce truncated version of estimator d which we denote dr Ht, defined as
Proof. Under both discounted and average occupancies d, for any K E N, it holds that
k K k=1
H-1
[aa(TT) (dl,, b) -IETI [dTTa) [dTx] bb)
(8, a) =
Σ
7 1(( = =8, Ak, =a).
=BTK [ b)} fK(T))
(5)
due the linearity of the expectation.
Average state-action occupancies In the case of average state-action occupancies, we define
Thus, all objectives are equivalent. Intuitively, the perfor- mance of a given policy is, in expectation, the same inde- pendently of the number of trajectories drawn evaluate its performance.
K
H-1 Σ 1(ktt = =s, a). 1=
1 (s, = K k=1
Σ
lim
H
(6)
We emphasize that the estimator above d always consid- ers infinite-length trajectories.
However, assume that the objective function f is convex, possibly non-linear. We make the following remark.
Remark 3.2. If f is convex, for both discounted and average occupancies, we have that S (TT) S [x((T, for any K E N.
3.2. Infinite and finite trials objectives for GUMDPs
We now introduce multiple objectives for GUMDPs that are functions of empirical discounted/averrge state-action occupancies. Below, in the case of discounted GUMDP, dTx corresponds to empirical discounted occupancy and dx . For average GUMPDs, dTx is an empirical average occupancy and d davg.x.
Proof. Under both discounted and average occupancies, for any K E and convex f, it holds that
(oa(T) = [(dx) = (ETx-se [JTR]]
S ETRNa [f (dre)) = fx (T),
The finite trials discounted/average objective, fx. is
where the inequality follows from Jensen's inequality.
fx(T) min ETK [f(dTx).
As a consequence, the theorem above suggests that, in gen- eral, there may be a mismatch between the finite and infinite trials formulations for GUMDPs. In the next section we show that, indeed, fx (T) + (x) in general and further investigate the impact of the number of trajectories in the mismatch between the infinite and finite trials formulations under both discounted and average occupancies.
where Ta ~ & for each IA E Tk. The infinite trials discounted/average objective, foo. is
min foo = min f(dx) min f TET (dTk))
where Tg ~ Sr for each Tk E Tk. We note that foe, un- der both discounted and average occupancies, is equivalent to the objective introduced in (3). Precisely, we call the objective above the infinite trials objective because, assum- ing is continuous, limx- f(drx) = f(dx) foo (r)). The finite trials truncuted objective, JK,H, which we only consider under discounted occupancies, is
4. Policy Evaluation in the Finite Trials Regime
In this section, we investigate the mismatch between the different GUMDP objectives introduced in the previous section, while evaluating the performance of a fixed policy. We consider convex objective functions. First, we focus our attention on the discounted setting and show that, in general, fK(#) + fT) for fixed π E IIs. Furthermore, provide lower bound the mismatch between fx (T) and Soe (T)) well as upper probability bound on the absolute distance between f(dTx. ,H) and foo Second, study policy evaluation under GUMDPs with average occupancies. We investigate the mismatch between fx(m) and fae (TT) for different classes of GUMDPs, also proving a lower bound on the mismatch between fx (T) and foo (T). Finally, we provide a set of empirical results to support our theoretical claims.
min (k. = min ETx [()drx.t).
where Ta ~ for for each T& Tk. We note that the finite trials truncated objective is more general than the finite trials objective. In particular, fK fx as H + 0C.
Why there may be mismatch between the infinite and finite trials objectives? When ff is linear, we make the following remark.
Remark 3. If f is linear, for both discounted and average occupancies, we have that foe (T) = fx (T), for any K N.

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
4.1. The infiitt-horizon discounted setting
Proof sketch. From the strongly convex assumption it holds, for random vector X, that
We first consider the discounted setting. Thus, let dx d as defined in (I). Also, we consider estimators dTx and dri,. as defined in (4) and (5) respectively. We prove the following result.
E[f(x) 2 (E[X)) + L [I
- B[X]12]
Using the inequality above, it holds that
Theorem 4.1. Under the discounted setting. it does not always hold that fK(T) = foe (T) for arbitrary x E IIs.
fK(TT) [oc(T) = ENT [s(TTe) - -5 TET [dtTx]
c 2 2
|| - dx [
TTx
Proof. We prove the theorem by providing GUMDP in- stance where fK(T)) * (T). We consider the GUMDP MA (Fig. lc). For simplicity, we let f and the occupancies depend only on the states. Hence, d = [d(so), d(s1), d( We let f(d) = d Ad, where A is the identity matrix (hence, f is a strictly convex function). It holds that d, = [[1 - ()), (T)(a))s)), ( [so]]. On the other hand, let K 1. It holds that, with probability =(aolso), the trajectory gets absorbed into $1 and t (so. $1, $1,...), yielding å, = [[1 - 7), %. Oj. With probability {{a]|s)) the trajectory gets absorbed into 82 and r = (80, 82, -2)...);
2
1 K
( c
VarTk
Σ
dr ())
2
K
sES,eEA
A=1
C
Vartwc, (dr(s,
2K
BES,aEA
where (a) follows from simplifying the previous expression
and substituting drx (s,a) K E dr, (8, a) where = s, Au, = a). The
dr, (s, a) = (1 - 7) Ei= result follows since ds a) is equivalent to the discounted return in an MDP with an indicator reward function.
yielding d, [[1 7), 0, 71. Let (ao)ss)) and note that <aa (8)
p. For any non-deterministic policy,
i... p (0, 1). it holds that
As stated in the theorem above, the difference between fx (T) and (T) can be lower bounded by the sum of the variances of the discounted returns for the MDPs with reward functions re.a. as defined above. We refer Ben- ito (1982); Sobel (1982); Sitař (2006) for an expression to calculate the variance of discounted returns in MDPs. We highlight the 1/ K dependence on the number of trajectories. Therefore, the result above shows that, for a low number of trajectories, the mismatch between the objectives can be significant, linearly decaying as K increases.
(T) =((d)
= =(p[(1 ()) 7, 0] +1 (1-p)(11 -7), 7),000) 0, 7))
<pf((1->)) 7, 0)) + (1 (1-r)/((11>)) 7), 0, +
= =kK=((T),
where the inequality holds since f is strictly convex.
As stated in the theorem above, under the discounted setting, fx( # foe (r) in general. Thus, we further analyze the impact of the number of trials, K, on the deviation between fx (x) and foo (T)) To derive the result below, assume f is e-strongly convex, i.e., it exists > 0 such that ((d) 2 f(22) + (d2)) (d1 d2) _ ||d] dz dzll2- for any d1, d2 belonging to the domain of f. We note that the objective functions of all GUMDPs in Fig. 1 are c-strongly convex (proof in appendix). We state the following result (full proof in appendix).
Finally, we provide a probability bound on the absolute deviation between [( and (T), for fixed ा E ss. To derive result, we assume is L-Lipschitz, i.e., lf((d) fd2)) S Ll[d] d2 l1, for any d1 d2 belonging to the domain of f. We prove the following result (full proof in Appendix).
Theorem 4.3. Lei M2 be a discounted GUMDP with con- vex and L--Lipschitz f, K E N be the number of sampled trajectories, each with length H N. Then, for any policy π and ā E +0, 1] it holds with probability at least 1- 5
Theorem 4.2. Let Mj be discounted GUMDP with e- strongly convex I and K E N be the number of sampled trajectories. Then, for any policy E IIs it holds that
(V 2/8 log(2H + 27
- foo 2
c
Σ
[dr(s.a) (a) TwC,
Var
f(d))
K
2K
SES
aEA
c(1 7)
Var [ Peaa
Proof sketch. Via the application of successive inequalities, it can be shown that, for any
2K
TwCa=
acA
( -f(dTT. .H)
== Eee r' aa (S,, Ar) is the discounted return for the MDP with reward function T (s,a d') = 1 if = and a! = a, and zero otherwise.
where 13
I |āx, dze + +27tt (7)
L
max LE(0....HH-1]
5

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
Using
union
bound
the fact that 2 exx -[S||AT (<)))) <
and
Pr E A(S). Let ZH.* be the random vector with compo- nents (H, = 1 H Et (Sk, = s). It holds that,
P -dd dx,, e')
(Efroni et al., 2020, Lemma 16) we have that, with
[K(T) = ETx /
K
]
probability at least 1 - 8.
Σ
lim ZH H +00
K
|ake dr.// S 2 (1g((11000
max
@ f(us) = (To(T))
JE(UU....H11)
K
Substituting the result above in (7) yields our result.
where (a) holds because: (i) from the Ergodic theorem for Markov chains (Levin et al., 2006), ZH. - frr almost surely Ak E (1..... K]: (ii) since f continuous, also holds that J( ΣX= 2H,x)) - [(ux) almost surely; and (iii) from (ii) and the fact that ff is bounded, the bounded convergence theorem (Durrett, 2019, Theo. 1.6.7.) allows to simplify the expectation. We then generalize the result for the case of state-action dependent occupancies by con- sidering a Markov chain defined over S x A.
As shown above, for fixed H E N, the bound becomes arbitrarily tight up to factor of 2Ly" as we increase the number of sampled trajectories K; factor 2 is due to the bias of our estimator, which exponentially vanishes as H increases. However, the bound highlights a 1/v depen- dence on K, suggesting that for low K values the mismatch between (T)) and f [(dTK H) can become significant. Fi- nally, the upper bound does not get tighter as H increases, for fixed K E N.
The result above states that, under unichain GUMDPs with continuous and bounded f. all objectives equivalent. We now address the case of multichain GUMDPs, i.e., GUMDPs that are not unichain and, therefore, the Markov chain pd contains two or more recurrent classes.
In summary, our results under the discounted setting show that, indeed, a mismatch between fK and foe exists, as showeased in Theo. 4.1, where we provided GUMDP un- der which fK * for. and in Theo. 4.2, where we proved lower bound on the deviation between fK and fxx Fi- nally, Theo, 4.3 further analyses how f(dTx, H)) concen- trates around oo (T) depending on the number of trajecto- ries K, as well as the length of each trajectory H.
Theorem 4.5. If the average GUMDP M, is multichain, then it does not always hold that (TT)) = (T) arbi- trary π E II.-
Proof. We prove the theorem above by providing a GUMDP instance where fx (T)) j (T). We consider the GUMDP M (Fig. Ic), which is multichain. For simplicity, we let f and the occupancies depend only on the states. Thus, d = [d (d(so),d( d(ss), d(s2)). We let f(d) = d' Ad, where A is the identity matrix (hence, / is a strictly convex function). It holds that d, [0, T(ao(s)). =[a]|so)]. On the other hand, let K = 1. With probability (Taolso). the trajectory gets absorbed into 8I and T = (so. 81,,,,...,, yielding d = [0, 1, 0]. With probability T(a] (s0) the trajectory gets absorbed into $2 and T = (So. $2, .)). yielding d [0, 0, 1]. Let p =aoo(o)) and note that (( = 1 - For any non-deterministic policy, i.e., p E (0. 1). it holds that
4.2. The infinite-horizon average setting
We now study the mismatch between the infinite and finite trials formulations of GUMDPs under the case of average occupancies. Hence, we consider estimator dry as defined in (6) and dg davg.s- We always consider infinite-length trajectories. We investigate which properties of the GUMDP contribute the mismatch between infinite and finite trials.
We start by focusing our attention on unichain GUMDPs, i.e. GUMDPs such that, for all π E My the Markov chain with transition matrix ps has at most one recurrent class plus a possibly empty set of transient states. To prove the next result (full proof in appendix), we assume f is contin- uous and bounded in its domain. All objective functions in Fig. are continuous and bounded, however, for the case of the KL-divergence in M2 we need to ensure dp is lower- bounded to meet our assumptions.
(xx(T) = f(dz) = S((0, p, (1-P))
= [pp[0, 1, 0] + (1 (1-p) p))0 0, 1)) < <po 1, 0)) + (1 - (l. 0. 1)) = fk=I(T),
Theorem 4.4. If the average GUMDP My is unichain and I is bounded and continuous in its domain, then [x(TT) ( for any π E 1ls.
where the inequality holds since f is strictly convex.
The result above shows that, under multichain GUMDPs, (T( # (T) in general. The intuition is that each trajectory eventually gets absorbed into one of the recurrent classes and, therefore, multiple trajectories may be required so that drç = dz and, hence, f(dTk) N f(d)). Therefore,
Proof sketch. Consider the case where the occupancies are only state-dependent. For any æ E IIs in a unichain GUMDP, the Markov chain with transition matrix pr and initial distribution Po has a unique stationary distribution
6

---

The Number of Trials Matters in Infinite-Horizon General- Markoy Decision Processes
now further investigate the mismatch between the finite and infinite objectives by proving lower bound on the deviation between fx( and foo (T) while assuming f is e-strongly convex (full proof in appendix).
7
0.2
? 0.6
7 0.8
00.5
-1.0
Theorem 4.6. Let M, be average GUMDP with strongly convex f and K E N be the number of sampled trajectories. Consider also the Markov chain with state- space S, transition matrix P" and initial states distribution Po- Let R. be set of all recurvent states of the Markov chain and RR,...,RR, the sets of recurrent classes, each associ- aled with stationary distribution pt. Then, for any policy Ils, it holds that
-1.5
10
20
H
H
H
K
K
K 10
fol.)
Figure 2: Empirical study of I [id H)) for different K, H and y values under M
[K(TT) (T)
Intuitively, the result above shows that the gap between fk (T)) and (T) can be lower bounded by weighted sum of the variances of the probabilities of getting absorbed into each of the recurrent classes. Thus, we expect the gap to exist whenever the sampled trajectories can get absorbed into different recurrent classes. Also, we highlight the 1/ K dependence on the number of sampled trajectories. Finally, we note that, in the case of unichain GUMDPs, since the unique recurrent class reached with probability one, the lower bound above equals zero, agreeing with Theo. 4.4.
C
Σ Var Var
[
Σ
T[als)) mi(s), m)()))
2K
8 RERi DEA
where B ~ Ber (p) denotes that B is distributed according to Bernoulli distribution such that P(B 1) p and
Qq
lim IPS E So ~ po)
the probability of absoopption R₁ when Sn ~ Po-
Proof sketch. Let as, = lim (H(s where H- (s a) # Σ 1(S s, A, = a). Under a multi- chain GUMDP, (n( a) ~ (als)))) almost surely where Y, is a random variable such that: (i) if s is transient, P(Y, = 0) = 1; and (ii) if s is recurrent, Y, = (s) with probability ou(s) and Yg = 0 with probability - Od(())+ where ((s) denotes the index of the recurrent class to which state s belongs. Then,
4.3. Empirical results
We now empirically assess the impact of different param- eters in the mismatch between fK.H (T)) and foo for arbitrary fixed Under the discounted setting, we con- sider d'x,, as defined in (5). We also use d'x. Jt to study the average setting by letting H + oo and y + 1, since lim lim,--1 (5) = (6). We consider the GUMDPs de- picted in Fig. 1. Under My,1, =[eet||so) = (right) (0) = 0.5, and π (right(ss) x[eft] $2) 1; for M, and M t is uniformly random. We consider 100 random seeds and report 95% bootstrapped confidence intervals (shaded areas in plots). Complete experimental results are in the appendix. The code used can be found in the following repository.
fK(T) [T) -IETx [ f (ETT [dTx)
C (
| - da [01]]]
TK
Vart~Ga [s)
2K
sES,aEA
Discounted setting (r < 1) In Fig. 2, a set of plots dis- plays the average finite trials objective function, f(dT ,1),, in comparison to the infinite trials objective f(dx), under GUMDP M As can be seen, the results highlight that [(dTx, II) can significantly differ from S(dz). Also, for the displayed y values, both the trajectories' length H and the number of trajectories K need to be sufficiently high for the mismatch between f(d .H) and f(dx) to fade away. This is suggested by Theo. 4.3 since both K and H contribute to the tightness of the upper bound. We display the results for estimator dTTc..I under all GUMDPs in the appendix.
((als) [Ya]
2K
SES,
Var
B
((als)"(((s})
2K
SER, a
where: (a) follows from the c-strongly convex assumption; in (b) we used the fact that (s, a) - Y, almost surely and the bounded convergence theorem (Durrett, 2019, Theo. 1.6.7.) to simplify the variance term; and (c) follows from rewriting Y, using a Bernoulli random variable, noting that Var (Y.) = for transient states, and simplifying the resulting expression.
In Fig. 3a, we display set of plots comparing f f( (ddTx.Hmood) mooo) and f(z)) for the different GUMDPs, under infinite-length trajectories. As can be seen when ? < 1, even for H
LI

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
Mí
M2
M
M
M2
M3
-0.5
0.75
-0.5
0.6
0.4
[1d
0.1
0.50
0.4
-1.0
Sid
0.2
0.2
0.25
0.0
0.00
0.0
0.0
0.6 0.8
1.0
0.6
0.8
1.0
0.4
0.6 0.8 1.0
0.2 0.4 0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
(a) Standard transition matrices.
(b) Noisy transition matrices.
K
K 5
K 10
fid.)
Figure 3: Empirical study of I (d == for different K and y values, with H oc.
0o, [(TTg, -= can significantly differ from f(dx) if the number of sampled trajectories is low. Such results support the fact that K plays key role in regulating the mismatch between the different objectives for discounted GUMDPs and are in line with our theoretical analysis.
of noise to the transition matrices so that there is a non-zero probability of transitioning to any other arbitrary state. All GUMDPs now become unichain. In Fig. 3b, we display the results obtained for different values with trajectories of infinite length. As can be seen, for the discounted setting (y < 1). it continues to exist a mismatch between the objec- tives. However, under the average setting (? - 1), the gap between the objectives fades away for all GUMDPs. Such results are in line with Theo. 4.4, where we showed that the different objectives are equivalent for unichain GUMDPs.
Average setting (y + +1, H + oo) As can be seen in Fig, 3a, under M1,1 and MM,,, we have that the difference between f(dTT,
and (dz) fades away when y + However, this is not the case for M2 Under M₁,1 and M2.,, we obtain such results because, given the choice of policies, the induced Markov chains have single recurrent class. Hence, since there exists a unique stationary distri- bution, d/ == converges to d, irrespective of K and the different objectives become equivalent. However, under M and for the chosen policy, the induced Markov chain has two recurrent classes and, hence, there exist multiple sta- tionary distributions. Thus, low number of trajectories (K" value) does not suffice to evaluate the non-linear objective.
5. Related Work
To the authors' knowledge, Derman (1970, Chap. 7) was the first to highlight the mismatch between objectives that depend on empirical average occupancies in comparison to objectives that depend on expected average occupancies. The author notes that minimizing an objective function that depends on empirical average occupancies is distinct from minimizing an objective function that depends on expected average occupancies. However, the author does not provide concrete examples of this mismatch, nor characterizes the mismatch depending on different properties of the underly- ing GUMDP and the number of sampled trajectories.
Our results are in line with the theoretical results from the previous section. We note that all GUMDPs in Fig. 1 are multichain. Hence, from Theo. 4.5, it not always holds that [[=xx) = f(dx) in general. Our results for My,3 exemplify that such a mismatch can occur. Naturally, be- ing multichain does not imply that f(dTx, # fdx) for: (i) all policies; or (ii) any policy. For ()), take our re- sults under M₁ as an example. For (ii), consider M, For all policies except π ([eft((s)) = 1 (zero otherwise) and x (right]s²) = 1 (zero otherwise), the induced Markov chain has a single recurrent class and, hence, f(dTx. := = ((dz). However, under the policy just described, even though the induced Markov chain has two recurrent classes, one of them is unreachable given the distribution of initial states and, hence, it also holds that [(dTx. = f(dx). Thus, for f,2, the different objectives are equivalent for all policies.
Other works consider the case of empirical occupancies instead of expected occupancies. As an example, Ross & Varadarajan (1989; 1987; 1991); Haviv (1996) study aver- age MDPs with sample-path constraints where the empirical cost induced by a trajectory needs to be below a certain threshold with probability one. Other works further char- acterize the convergence of empirical average occupancies in MDPs (Altman & Zeitouni, 1994; Mannor & Tsitsiklis, 2005; Tracol, 2009).
More recently, Mutti et al. (2023) show that finite-horizon GUMDPs implicitly make an infinite trials assumption, i.e., knite-horizon GUMDPs implicitly assume the performance of given policy is evaluated under an infinite number of episodes of interaction with the environment. The authors introduce a modification of GUMDPs where the objective
Average setting (7 + 1, H + oo) with noisy transitions We consider the GUMDPs in Fig. 1, but add small amount
8

---

The Number of Trials Matters in Infinite-Horizon General-Utilit, Markoy Decision Processes
Table I: Are the infinite and finite trials formulations equivalent? (V= yes, X= no)
Discounted setting
Average setting
Objective function (f)
Unichain
Multichain
Linear
[Remark 3.1]
[Remark 3.1]
[Remark 3.1]
Non-linear
X [Theo, 4.1]
[Theo. 4.4]
X [Theo. 4.5]
function depends on the empirical state-action occupancy induced over a finite number of episodes. Under the intro- duced finite trials formulation, the authors show that the class of Markovian policies does not suffice, in general, to achieve optimality and that non-Markovian policies may need to be considered.
summarize our results in Table 1.
While we focused on the case of policy evaluation, we expect the mismatch between the finite and infinite trials to also impact policy optimization. For example, under generalized policy iteration scheme (Sutton & Barto, 201 8), we expect the mismatch between the infinite and finite trials formulations at the policy evaluation stages to impact the resulting optimal policies. Future work should study policy optimization in the finite trials regime.
In our work, we extend the work developed by (Mutti et al., 2023) by considering the infinite-horiie setting. We start by showing that, under the infinite-horina horizon, there still exists, in general, mismatch between the finite trials objective and the infinite trials objective. After establishing the exis- tence of the mismatch for both the discounted and average settings, we further provide upper and lower bounds that allow to better understand how such a mismatch depends on the number of sampled trajectories. We also elaborate on how our bounds and the mismatch between the finite and infinite trials formulations depend on certain properties of the underlying GUMDP. We are the first work to pro- vide lower bounds on the mismatch between the finite and infinite trials objectives, as Mutti et al. (2023) only prove upper bounds in the context of policy optimization. Also, while Mutti et al. (2023) show that, in general, there exists a mismatch between the finite and infinite trials formulations under
A Acknowledgements
This work was supported by Portuguese national funds through the Portuguese Fundação para a Ciência e a Tec- nologia (FCT) under projects UIDB/50001/2020 (INESC- ID multi-annual funding), PTDCICCI--CM/5506/2222 (RELEvaNT), and AI-PackBot (project number 14935, FED-200000-EDEE---000000000 Pedro P. Santos ac-
knowledges the FCT PhD grant 2021.04684.BD.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
settings, our Theo. 4.4 states that under certain conditions (the GUMDP being unichain), there ists no mismatch. Hence, the nature of our results and those in Mutti et al. (2023) greatly differ.
References
6. Conclusion
Abel, D., Dabney, W., Harutyunyan, A., Ho, M. K., Littman,
In this work, we provided clear evidence, both theoretically and empirically, that the number of trials matters in infinite- horizon GUMDPs. First, under the discounted setting, we showed that a mismatch between the finite and infinite trials formulations exists in general. We also provided upper and lower bounds to quantify such mismatch as a function of the number of sampled trajectories. Second, under the average setting, we showed how the structure of the underlying GUMDP influences the mismatch between the finite and infinite trials formulations: (i) for unichain GUMDPs, the infinite and finite trials formulations are equivalent; and (ii) for multichain GUMDPs there is, in general, mismatch between the different objectives. Finally, we provided a set of empirical results to support our theoretical claims. We
M. L.. Precup, D., and Singh, S. On the expressivity of Markov reward, 2022.
Achiam, J., Edwards, H., Amodei, D., and Abbeel, P. Varia- tional option discovery algorithms, 2018.
Altman, E. Constrained Markov Decision Processes. Chap- man and Hall, 1999.
Altman, E. and Zeitouni, O. Rate of convergence of em- pirical measures and costs in controlled Markov chains and transient optimality. Mathematics of Operations Re- search, 19(4):955 9744 1994.
Benito, Calculating the variance in Markov-processes

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
with random reward. Trabajos de Estadistica y de Inves- figacion Operativa, 33:73-85, 1982.
Mannor, S. and Tsitsiklis, J. N. On the empirical state-action frequencies in Markov decision processes under general policies. Mathematics of Operations Research, 30(3): 345-561,10 2005.
Chow, Y., Robbins, H., and Siegmund, D. Great Expec- lations: The Theory of Optimal Stopping. 1971. ISBN 9780395053140.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, L., Wierstra, D., and Riedmiller, M. Play- ing atari with deep reinforcement learning. Nature, 518 (7540):529 533, 2015.
Derman, C. Finite State Markovian Decision Processes. Academic Press, Inc., USA, 1970. ISBN 0122092503.
Durrett, R. Probability: theory and examples. Cambridge University Press, 2019.
Mutti, M., Santi, R. D., Bartolomeis, P. D., and Restelli, M. Convex reinforcement learning in finite trials. Journal of Machine Learning Research, (4(250):1-45 2023.
Dvoretzky, A., Kiefer, J., and Wolfowitz, J. The inventory problem: Ii. case of unknown distributions of demand. Econometrica, 20(3):450 466,-46666666 1952.
Osa, T., Pajarinen, J., Neumann, G., Bagnell, J. A., Abbeel, P., and Peters, J. An algorithmic perspective on imitation learning. Foundations and Trends in Robotics, 7(1-2):
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained mdps. CoRR, abs/2003.02189, 2020.
1-179, 2018. ISSN 1935-8261.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. Diversity is all you need: Learning skills without reward function, 2018.
Ross, K. and Varadarajan, R. Sample path theory for time- average Markov decision processes. Proceedings of the IEEE Conference on Decision and Control, pp. 2264- 2269, 1987.
García, J., Fern, and Fernández. A comprehensive sur- vey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437) 137--4480 2015.
Ross, K. W. and Varadarajan, R. Markov decision processes with sample path constraints: The communicating case. Oper. Res., 37(5):780-790 1989.
Geist, M., Pérolat, J., Laurière, M., Elie, R., Perrin, S., Bachem, O., Munos, R., and Pietquin, O. Concave utility reinforcement learning: the mean-field game viewpoint, 2022.
Ross, K. W. and Varadarajan, R. Multichain Markov deci- sion processes with a sample path constraint: A decom- position approach. Mathmmtics of Operations Research, 16(1):195-207, 1991.
Haviv, M. On constrained Markov decision processes. Op- erations Research Letters, 19(1):25-28, 1996.
Hazan, E.,, Kakade, S., Singh, K., and Van Soest, A. Prov- ably efficient maximum entropy exploration. In Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of P Proceedings of Machine Learn- ing Research, pp. 1681-2691, 2019.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M.. Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D. Mastering the game of Go without human knowledge. Nature, 550(7676):344355,, 2017.
Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C. Im- itation learning: A survey of learning methods. ACM Comput. Surv,, 50(2), apr 2017.
Sitar, M. Mean and variance in Markov decision processes. 2006.
Kallenberg, L. Linear programming and finite Markovian control problems, volume 148. 01 1983.
Sobel, M. The variance of discounted Markov decision processes. Journal of Applied Probability, 1944):794-802 1982.
Levin, A., Peres, Y., and Wilmer, E. L. Markov chains and mixing times. American Mathematical Society, 2006.
Stidham, S. Socially and individually optimal control of arrivals to a GI/M/I queue. Management Science, 24(15): 1598-1610, 1978.
Lillicrap, T., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. CoRR, abs/ 15090029,, 2016.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
10

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
Tracol, M. Fast convergence to state-action frequency poly- topes for MDPs. Operations Research Letters, 37(2): 123-126, 2009.
White, J. Further real applications of Markov decision processes. Interfaces, 18(5):55-61, 1988.
Zahavy, T., O'Donoghue, B., Desjardins, G., and Singh, S. Reward enough for convex MDPs. CoRR, abs/2106.00661, 2021.
Zhang.J.. J. Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. Variational policy gradient method for reinforcement learning with general utilities, 2020.

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
A. Empirical State-Action Occupancies
Given a random trajectory T' (So, Ao, S1, A.,...), we note that
(x = 8, A, = a/So ~ po) = Erwg, [1(5 = 8, A, = a)] - (+))(((8))) s, a),
where (T) denotes the probability of trajectory T (so, do, 81, (1,...) under policy
A.1. Discounted occupancies
Given random trajectory T (So, Ao, S1, A1,...... consider the estimator dr (s, a) defined
dr(s, (1- Σ
1(, s, =a)
(8)
t=
holds that, for all s and A.
20
BI [dr(s,a)] ETTST
(1 (1-7) Σ
1'1( = A
1=0
= -(1 Σ (T(
*1(s: 5,
1=0
= (1 -17)
Σ (
1=0
(1 7)
(P, s, s, also ~ Po)
dr (s,
ie., dr an unbiased estimator for dg. Given a set of K random trajectories Tx = [Ti..... Tk]. consider estimator
1 Σ (s,aa)
( a)
K
for dr. as defined in (8). We note again that, for all E S and a e A. and any e N.
ET ddr (d (s,aa)
Σ
ETK
K
k=1
BTense [dra(s,0)]
dx (8, a).
ie., the estimator drę is unbiased. We now show that estimator dr is also consistent.
Remark A.I. (dTx is a consistent estimator) For any s E and a E A, the estimator d (s, a) consistent in probability as) > e 0. Ve > 0. This is true because the estimator consists of
for as, i.e., lim IP (12rx (s. sample average of random variables du (8. a) = dr, (8, a) (we note that dr, a) is random variable since it is the result of applying function to the random trajectory Tk). In particular, since random variables du a) are i.i.d. and (s)(s = dg (s, a) < co, for all At the weak law of large numbers states that _k= du(s, a) converges in probability (s, a) when co.
K
12

---

The Number of Trials Matters in Infinite-Horizonn General-Utility Markoy Decision Processes
A.2. Average occupanctes Given random trajectory T' = (So, Ao, S1, AI,......) consider estimator dr a) defined
Ø-1
dr(,, lim 100000
Σ 1=0
1(, s, s, a).
(9)
H
holds that, for all and A,
H-1
Eywer (dr(s,,)) Branst
1
lim
1(; = 8, -
11000 H
1=)
H-1
(x(T))
lim
A, 1(S = 8, A, a)
H+000
H
1=0l
lim =
1
E5 (T(
H-1
Σ =(8
11
1=0
1 H-1
lim
(r))
(=0
H-1
lim
Σ
# H
1=0
= dwggr (8, (),
i.e. dr is an unbiased estimator for dagg.r. Given set of K random trajectories Tx (Ti...., TTk...,TT.... ). consider estimator
1 K
d (8, a) = K
as,
for dy as defined in (9). We note again that, for all S and a E A. and any K E EN,
K
ETx (2xx())))) ETK
Σ
drg
(2)
K
k=
Branso (5.
davg. (8, a):
ie., the estimator drp is unbiased. Finally, similarly to the case of discounted occupancies, the average occupancy estimator drw is also consistent, i.e., loo (dTT (s,a) - dx (s) >t) = 0, Ve > The line reasoning the same as that in Remark A.I.
B. Policy Evaluation in the Finite Trials Regime Assumption B.1. We say that f is c-strongly convex if there exists >> 0 such that
f(d:) 2 f(22) + ff(2)) (d1 d2) + C ||d1 - del12
(10)
2
for any di, d2 belonging to the domain of f. Equivalently, f is c-strongly convex if there exists 0 such that
v2 2 cl,
(1I)
for all d belonging to the domain of f, where is the identity matrix.
13

---

The Number of Trials Matters in Infinite-Horizonn General-Utility Markov Decision Processes
Remark B.2. Consider the objective function [(d) (og]o))))) It holds that f is c-strongly convex and any (0, 1]
satisfies (10) and (11).
Proof. It holds that f(d) diag((1/d(1), 1/d(2), ....) where diag(a) denotes the diagonal matrix with vector in its diagonal. From the strong convexity definition,
f(d(d cl, AA
f(d) d = 0, PA
A:(d) c 0, VA, PA
Amia (d) 2 c, PA
min
2 c, Ad,
d(i)
where (d) the eigenvalues of matrix V (dd. Since A(S A), holds that min; 2(3] and, hence, f is c-strongly convex with any c (0, 1] satisfying (10) and (11).
J > for any E A(S A)
where d3 is fixed. It holds that f is Remark B.3. Consider the objective function f(d) = KL(d|dg) = E, d(i) log (2(3)
e-strongly convex and any e (0, satisfies (10) and (11).
Proof. It holds that fd) diag( diagonal. Thus, similar to the case of the entropy function, holds that is c-strongly convex with any c (0, 1] satisfying (10) and (11).
diag((1/d() [1)d(1), 1/d(2), ....) where diag(a) denotes the diagonal matrix with vector in its
Remark B.4. Consider the objective function f(d) d Ad. If A is positive definite, i.e., Amin(() where Amin (A) denotes the smallest eigenvalue of matrix A, then is c-strongly convex. Furthermore, any (0, 2mmin()). (A)] satisfies (10)
and (11).
Proof. It holds that fdd(d) = -2A. From the condition for strong convexity,
f(d cI, Vd
2A - 2
2\, - c 0, Vi
24 2g Vi
2mmin (A) 2
where \; are the eigenvalues matrix A. If Xmin (A) 0. then any E (0, 2A (A)] satisfies the condition above.
B.1. Discounted setting
B.1.1. PROOF OF THEOREM 4.2
Theorem 4.2. Let M, be GUMDP with c-strongly convex f and e N be the number sampled trajectories. Then, for any policy Iss it holds that
fK(T) - (T) 2
Σ
Var Thce
(dT(s,a))
2K
SES
aEA
c(1
7)
Var T~cr
J Psnu
2K
SCS
aEA
where J2-- = Ee= (Sr,,((S,444 At) is the discounted return for the MDP with reward function (s,a('s s' = and a' = a, zero otherwise.
14

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
Proof. For any policy
[g it holds that
fx(T) (T) = ETx [((Tx) -f [ET (dric)
|dta - dx [
Exx
Σ (5)
TTx
&ES,BEA
c
Σ ETK
(d ds(,
sES,nEA
VarTx [aTx(3,a))
sES,nEA
1
Var (T...TT.
Σ
dra (s,
K
eES,
C
[dr(s,a)
Vart
2K
sES,aEA
c(1 71--))
Vart
Σ
Er1(S, =s A.A. a0)
2K
sES,aEA
1(=
c(1 712
Vart~Ge
2K
sES,aEA
where (a) follows from the strongly convex assumption and the fact that
+ f(x) ( - [[X]) + 2 x - E[X]1|
= E| [(EX)) S
where X is a random vector, We refer (Benito, 1982; Sobel, 1982; Sitar, 2006) for closed- form expression for the
calculation of Varr~<e
Tape
B.1.2. PROOF OF THEOREM 4.3
Theorem 4.3. Mr be a GUMDP with convex and I-Lipsshitz f. E N the number of sampled trajectories, each with length H N. Then, for any policy and 8 10, it holds with probability at least
(T)((T) - ((dxx. I (v
( [AS][A|(og(2111) + 27 EUpper (K, H). K
For fixed E N it holds that
lim
Eupper K, H.) 2
400
and for fixed K N
lim Eupeer (K, H) = oc. 40000
15

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
Proof. For any policy and H N. have
(TO(T)) H(
{((x) f(dTx.H))
M L d drc.HHl ||1
0
(1 -) H-1
16
(1 7) Σ
? yxxxt
Σ 7 dx,
1 - 7 t=
t=
1- #-1
8
Σ
7' (11- ) dz - dx.t)
+ (1 -17)
Σ
y d
1- /
WB
1-7
Σ
#-1
(11 (1 dx dx.t)) +1"
1
7'
1-1
#-1
1-7
[[11 (1 (1--"") 711 dz - dk.0// +
L
1-
1 1-7
([|āxc. - dmo//1 + 1-11"* (dd.eell)) + 7
L
1 1-
1-7
** ||dke dzs0// || + 22
17
1- 1=0
|dk,
-d.. ||| + +2
max (E(O....H-11)
where: (a) is due to the L-Lipschitz assumption; in (b) we used dz = (1 Ei= d'd where dz,, denotes the expected occupancy under policy и at timestep t, and dTx. (1 - 7)(11 > 7 ddx, where dx, denotes the empirical distribution induced by the K random trajectories timestep f; and (c), (d) and (e) follow from the triangular inequality. We aim to bound the last inequality above with high probability; do so, we note that
H
P
max (E(0....H-1)
|dx. da. > e
SP
|dx,e
d= >6
H
|dx,+
done 26)
PP
1=U
(b)
2 exp
(-2|ST|A| K(Et)))
1
2/SS|I K(6))))
2HH exp
where: (a) follows from union bound, and (b) from the fact that PP (112m: dx.a
> (c) S 2exp
(Lemma 16 in (Efroni et al., 2020)). Thus, it holds with probability at least 1 - 5
|dx. dr.. ||
2|5 All log (2H/6)
max BE 11
K
Given the above we conclude that, with probability at least 1
2| A log(211/0)
[~)( s(dTx. 5
+27
K
16

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
For the limits have, for fixed H N,
2/5||A (2g(2H/6)
lim Uppper (K, H) = lim L
+ +27
K K000
K000
K
2|5||AA| (2g/))/)))))))
L lim
+ +217
K
2L H
For fixed K E N,
||5||A|] (2H()
lim Eupper H) = lim L
+ 2
H H-500
11 1-000
K
|| log (2H/6)
= lim
2L lim H
H0000
K
H-+00
S|A
L
Vlog(2H/8) +0 11200
lim
K
1|S|AA
LV
lim log(211 +
K
H-400
||A||A
LV
+ 0
K
00
B.2. Average setting
B.2.1. PROOF OF THEOREM 4.4
Theorem 4.4. the GUMDP My is unichain and is bounded and continuous in its domain, then fx(x) = (T)(T) for any π lss.
We start by focusing on the case of state-dependant occupancies and later generalize our result for the case of state-action-dependant occupancies.
Proof.
For any E Iss in unichain GUMDP, the Markov chain with transition matrix px and initial states distribution contains a single recurrent class R, and a possibly non-empty set of transient states Z. Associated to the unique recurrent class is Na E ASS), the unique stationary distribution of the Markov chain, which satisfies ua (s) > 0 for s E R. and ua (s) = 0 for s E Z. Furthermore, the unique stationary distribution (er satisfies
Σ Pd (*)ss (s')) ps(ss), vs E
S'ES
(s) =1
SES
All aforementioned facts can be found in textbooks such as (Puterman, 2014).
Now, for a fixed policy æ E ls. consider the estimator
#-1 1(S = =),
dr(s) lim
Σ t=0
(12)
H
where 7 = (Sg, .)....) denotes a random trajectory from the Markov chain with transition matrix P and initial distribution Pp- Since there is a single recurrent class, independent of the initial state distribution, a random trajectory drawn from the Markov chain will eventually get absorbed into the unique recurrent class in finite number of steps. Hence:
17

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
for any transient state s E 2 of the Markov chain, we have that (s(s) 0 almost surely. From the definition of transient state, it holds that Et=o 1(S, 8) < oo with probability one, yielding
1 1s, 1(, 8)
dr(s)
lim H0000
lim H
Σ t=0
1(, =) =0 -))
H
H
1=0
for any recurrent state E R. belonging to the unique recurrent class of the Markov chain, we have that (s) = (s((s) almost surely. Recurrent classes within a larger Markov chain can be seen as independent Markov chains (Puterman, 2014). Let PR-sR denote the transition matrix for the states belonging to the recurrent class of the Markov chain. Then, since PR- is an irreducible Markov chain (any state reachable from any other state), from the ergodic theorem for Markov chains (Levin al., 2006) it holds that, for any initial distribution.
H
IP (dr(s) =Mx(s)) (s(())= =P
lim H H
Σ 1(, =)) -ma(()) ((5:=)))(((()) =1. 1. t=0
Now, the fact that estimator (s) converges almost surely to (s=(s) in order show the equivalence between fx (r) and Sox (T)) For now, we assume / is defined over state-dependant occupancies and later extend our analysis for the case of state-action-dependaee
occupancies. Let HH be the random vector with components ZH,, (s) 3 Ei 1Sk,, s). Since, for each E S and le {1...., }), it holds that (s) - (s(s) almost surely, have that random vector ZH Mr almost surely, for any & E {1, {1...., K]. i.c.,
lim ZHA = MT) M4)= =1, Ak E (1,..,.., K}. H-+00
By the definition of the finite trials objective (considering a state-dependant occupancy and objective function), it holds that
fx( - ETic [f(dTx)] ETw [
K
].
lim ZH.k
K
100000 A=
Since HH frr almost surely for any lt E {1, (1....,K K), it also holds that 1 =.k=1 Zh. or almost surely since the K trajectories are independently sampled. Assuming is continuous, it holds that f( + Σx= ZH,k) - f(w) almost surely. Since f is bounded in its domain by assumption it also implies that s (* Σx ZH. is bounded for any H E N. Thus, from the dominated/bounded convergence theorem (Durrett, 2019, Theo. 1.6.7.), it holds that
1==1=
] - =B(((>>)] [ff(+))] = f(ux),
ETK
lim ZH,
K
H 40000 k=1
where the second equality holds because /( Ex= 7H,)) converges almost surely to f(#z), which is a non-random quantity.
Finally, it remains to show that the result above also holds for the case of state-action occupancies. Consider second Markov chain, which we call the extended Markov chain, that has state space S = S x A², transition matrix P(s', a' a) (T(()
p(s'|s, a)x (a') (s'), and (o(s,a) a) = (s) (a) s). This Markov chain encapsulates both the transition dynamics p and the policy æ within the transition matrix P and it should be clear that a random trajectory from the extended Markov chain ((So Ao), (S1, A1)...) precisely describes a random sequence of state-action pairs when using π E IIs to interact with the GUMDP. It holds that the extended Markov chain has unique stationary distribution H. (s, a) = pt (s) This is true
We denote a state of the extended Markov chain with the tuple (8, a). However, to make notation simpler, we usually drop the parenthesis from the (s, a) tuple, thus writing po(s, a) instead of po ((s,, a)), P(s!, aal)s, a) instead of P((s', (((ss,a'))e (')) a)), pz(s,)) a) instead of pz ((, a)), etc.
18

---

The Number of Trials Matters in Infinite-Horizonn General-Utility Markoy Decision Processes
because Nr is stationary distribution for the extended Markov chain if it satisfies
(x a') = Σ
P(s', a'Is, (s),, Vs',a'
(13)
sES a
Σ
Pr (8,
(14)
BESaEA
Letting n (s, (n (s)) satisfies (13) since, when π (aals"') > 0.
((('')((')s'') = ΣΣ
sESREA
(=(d))(((1s))
ΣΣ
aES aEA
= un((') = Σ Σ
sEA
Mn(d)) = Σ (dd(ss))nr)),
SES
and the last equality above holds since Pr is the stationary distribution of the Markov chain with transition matrix pr, If <<a'ls)) then (13) also holds given that (s' a') μ (s')tT((aass'' = 0. Equation (14) is also straightforwardly satisfied. It also be seen from the equations above that the stationary distribution üu, is unique. Assume the opposite, i.e., there exist multiple stationary distributions for the extended Markov chain. This would imply that it also exist multiple vectors satisfying the last equation above, which we know it is not possible because the Markov chain with transition matrix pr has unique stationary distribution.
Consider estimator
H-1 = s,
(s)
lim
Σ 1=0
(15)
H-000
H
where 7 = (So, AI, denotes random sequence of state-action pairs from the extended Markov chain. Since there is single recurrent class (associated with the unique stationary distribution of the extended Markov chain), independent of the initial state distribution, random trajectory drawn from the extended Markov chain will eventually get absorbed into the unique recurrent class in finite number of steps. Hence:
if (a|s) 0 for some state-action pair (s, then a) is never visited in the extended Markov chain under any distribution of initial states and, hence, P (drr(s, = = 1.
for any state-action pair (s, a) such that π (als) 0, if (s, a) is transient the extended Markov chain (equivalent to being transient in the Markov chain P*), then IP (s, a) 0)
for any state-action pair (s, a) such that π (als) > 0, if (s, a) recurrent in the extended Markov chain (equivalent to 8 being recurrent the Markov chain P*), then from the Ergodic theorem for Markov chains (Levin al., 2006)
H-1
P -()(ss))))) F
lim H-
Σ
s, =
Thus, noting that (8, = p (8)x(((()) dx (s, a) and following the same line of reasoning as we did for the case of state-dependant occupancies, we can use the fact that estimator dr a) converges almost surely to d, (8, a) to show the equivalence between fK and (T).
Lemma B.5. Consider a Markov chain with finite state-space S and transition matrix P. Let Po E ASS) be the distribution of initial states of the Markov chain, i.e., So ~ Po, and afterwards S, ~ P(-)St-)), for all > O. Assume that the state-space can be partitioned into disjoint recurrent classes Ri.... RL and a set of transient states Z. For each recurrent state
19

---

The Number of Trials Matters in Infinite-Horizonn General-Utilig Markoy Decision Processes
E R1 U... RL, we let ((s) denote the index of the recurrent class which stale belongs. Let also ie denote the unique stationary distribution associated with each recurrent class Ri. It holds, for any S, that
H-1
P
lim H-000
1
Σ 1(S =0] =Y, =1,
H
where Y, is a random variable such that, i E then P(YY, = 0) 1, and if recurrent then
if = (s)s) ify= 0, 0, 0, otherwise,
(((s))
P (Y, = y)
and
(1(()) = lim P(S, E Ri(a))So ~ Po) t-000
denotes the probability of absortion into recurrent class Ri(s), i.e., the recurrent class to which recurrent state belongs, when the initial state So is distributed according 10 po and can be calculated in a closed-form manner (Kallenberg, 1983, Theo. 2.3.4.). In other words, lime--oc H describes the asymptotic proportion of time the chain spends any state s S.
1 Ei=0 1(S = 8) converges almost surely to random variable Y,, which
Proof. The state-space S of every sinite-state Markov chain can be partitioned into L disjoint recurrent classes RI...., Rr and set of transient states Z. For each recurrent state E R₂ U... URL. we let L(s)) denote the index of the recurrent class to which state s belongs. Every recurrent class R2 can be treated as an independent Markov chain, associated with a unique stationary distribution fr,, which satisfies (r(ss) > 0 for all s E R2 and (s(s) = 0 for all & R2 (Puterman, 2014). Once absorbed into a given recurrent class, the chain cannot leave the recurrent class and will visit every state in the recurrent class infinitely often.
Let (s) limw-xo H EE (S: s) denote the asymptotic proportion of time the chain spends in any state E S. It holds that:
for any transient state 8 E of the Markov chain, we have that (s) almost surely. From the definition of a transient state, it holds that Ei 1(S, = s) < oo with probability one, yielding
#-1
dr(s)= lim
Σ
1(: s) s)
lim #
I s) s) =)
H
H
t=U
t=
for each recurrent class R2, if the Markov chain gets absorbed into R₁ then it holds that
# Σ 1(S = s) )m(=m)))) = for s Rrs
lim H H
i.e., the asymptotic proportion of time the chain spends in each state E R, converges almost surely to pr(s) for all s E R, This result follows from the ergodic theorem for Markov chains (Levin et al., 2006).
for each recurrent class R2 if the Markov chain gets absorbed into another recurrent class I' # I then it holds that ds)(s) 0 for all Ri since, once absorbed into class Ry the chain cannot leave the recurrent class (by definition).
Therefore, the chain starts in an arbitrary state So ~ Po and eventually gets absorbed with probability one into a given recurrent class Rr. Once absorbed into R₁, the chain behaves as an independent Markov chain defined only on states R₂ and: (i) the chain cannot leave the recurrent class, hence dr(s)) = for
& R,; and (ii) dr((s converges almost surely to (s) for every $ E R2, Thus, it holds that lim - H Σn 1(5, = 8) can be described, in the almost surely sense, by a random variable Y, such that: (i) if s E Z then Y, = 0 almost surely; (ii) if s E R2, i.c., if s belongs to some recurrent class RR, and the chain gets absorbed into Rr, then Y, = (s) almost surely; and (iii) 8 Ri but the chain gets absorbed into
20

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
other recurrent class Ry, then Y. 0. Therefore, the probability density function of Y, can be described follows: if E 2, i.e., if is transient, then P (Y, = 0) = 1. On the other hand, if s is recurrent
ai(s):
if y = (+)=
P PYY, y)
a(()).
y 0,
0,
otherwise,
where
(n(s) lim P(S, E R1(a))So ~ Po)
t-000
is the probability of absorption to recurrent class Ri(s), i.e., the recurrent class to which recurrent state 8 belongs, when
So ~ and can be calculated in closed-form manner (Kallenberg, 1983, Theo. 2.3.4.)
Lemma B.6. Consider GUMDP with finite state-space S. finite action-space A, transition probability function p S x A + ((S), and let po E ((S) be the distribution of initial states. For any fixed stationary policy π E IIs, the interuction between the policy and the GUMDP gives rise to a random sequence of state-action pairs So, Ao, S1, At,... Consider also the Markov chain with state space S, transition matrix pa (s'(s) = EoEA p(s' po(sssss,, (a)ss, and initial distribution po- It holds, for any E S and E A, that
H-1 Σ 1, =Ysr(ale)= =1,
P
lim H-000
-YTT(ass)
H
where Y, is the random variable defined in Lemma B.5 by considering the Markov chain with transition matrix PR
Proof. For a given fixed policy π E Iss, consider two Markov chains:
(a)s)))))))))))))))))))))))))( (all)) and po as defined the the first Markov chain has state space S, transition matrix P* P(ss
original GUMDP. Assume this Markov chain can be partitioned into L disjoint recurrent classes ..,..., Rr and set of transient states Z. For each recurrent state R1 U...U RL, we let ((s) denote the index of the recurrent class to which state belongs. Let og denote the probability of absorption to recurrent class R, given Po- Every recurrent class R, can be treated as an independent Markov chain, associated with unique stationary distribution 14, which satisfies (x) > 0 for all 8 E R, and (+(s) = 0 for all & R2 (Puterman, 2014).
the second Markov chain, which we call extended Markov chain, has state space S = S x A (hence we denote with the pair (s, a) a given state of the extended Markov chain), transition matrix P(s', aalss, a) p(s'|s, (a'(s'))") and (s a) = po(s) yr (a|s). This Markov chain encapsulates both the transition dynamics p and the policy x within the transition matrix P. should also be clear that a random trajectory from the extended Markov chain precisely describes random sequence of state-action pairs when using Пs interact with the GUMDP. Assume we can partition the extended Markov chain into L disjoint recurrent classes R1. Rr and set of transient states 2. For each recurrent state (s,a) E R2 U...U R.. we let i(s, a) denote the index of the recurrent class to which state (s, a) belongs. Let also on denote the probability of absorption to recurrent class R2. Every recurrent class R2 can be treated as an independent Markov chain, associated with a unique stationary distribution ju, which satisfies (8, a) > 0 for all s R2 and (4 a) = for all é R₂ (Puterman, 2014).
(S,,
We are now interested in understanding how the long-term behavior of both chains is related, for fixed π E Ils. We make the following remarks:
1. if π (als) for some state-action pair (s, a). then (s, a) is never visited in the extended Markov chain for any distribution of initial states Po-
2. For each (s, a) such that (a]s)) > O, if (s, a) is transient, then all states (s, a') for a' A such that <(a)ss) > 0 are also transient. This is true because if some pair (s. is only finitely visited (from the definition of transient state) it implies that state is also finitely visited and, therefore, all pairs (s, a²) for a' E A such that π ma'ls) > 0 need also to be finitely visited. For each (s, a) such that (als)) > O, if (s, a) is recurrent, then all states (s, a') for a' E A such that T (aa (a'lss) > are also recurrent. This is true because, if some pair (s, a) is infinitely visited (from the definition of a recurrent state) it implies that state s is also infinitely visited and, therefore, all pairs (s, a') for a' E A such that r (Taals)) > need also to be infinitely visited.
21

---

The Number of Trials Matters in Infinite-Horizonn General-Utility Markoy Decision Processes
3. A given state transient for pa if and only if states {(s,a) <<lss) 0} are transient for P. A given state is recurrent for pa if and only if states ((s, a) π (a]s) 0} are recurrent for P.
4. Two states s and s are reachable from each other for pa if and only if all states in {(s,a) i(aas) 03 and all states in {(s', a) < (alss)) > 0} are reachable from each other for P.
5. Given the point above, a given set of states is communicating for p", p", i.e., all states in C are reachable from each other according to PM, if and only if the set of states {(s,a) E C and i (a]s) > 0} is communicating for P.
6. A communicating class C closed for P* i... is impossible leave C, and only if the of states {(s, a) :
C' and ={ass) 0} is closed for P.
7. Since a recurrent class is a set of states that is communicating and closed, given the two points above, there exists a one-to-one correspondence between the recurrent classes R....., RS and R....., Rr. In particular, Ri {(s, a) R₁ and (a]s)) > 0} and R2 {s (s, Rí and ((ass) 0}-
8. The probabilities of absorption into any of the recurrent classes are the same for both Markov chains, i.c. aq = âi for all E [l...., L}. Let as denote the probability of absorption into recurrent class R₁ in the Markov chain Pa when the initial state is 8, and ( denote the probability of absorption into recurrent class R, in the extended Markov chain when the initial state is (s, a). It holds, for any / {l...., L). that
01 Σ Po(s)
(16)
and
ōj Σ
E
pals, a))(sa))
sES aEA
Σ Σ aESaEA
(()))
It should also be clear that Oss, = EaEA (als))ā(s given the one-to-one correspondence between the recurrent classes of both Markov chains. Replacing dxa,1 = LaeA ((ass)ā ())(a.))) in (16) yields ār and, hence, ot âg. We refer to (Kallenberg, 1983, Theo. 2.3.4.) for a closed-form expression to calculate the probabilities of absorption into each recurrent class.
9. For every recurrent class R, of the extended Markov chain it holds that (r a) = (s))T)((a)s) s). This is true because A is a stationary distribution for the extended Markov chain if it satisfies
in ,a) = ΣΣ P(s', a al,,allss,)atl ()),s Vs'ad'
(17)
SES aEE
1= ΣE ())s,)).
(18)
sESaEd
Letting a)) (((s) satisfies (17) since, when (Talls') 0.
m(s')T(a'15)> (0 T(ass) P(s d'ls,
m(8))((d1))))) = ΣΣ
aEA
pi((') Σ Σ
aEA
m(()) Σ (=((ss))p((),,
and the last equality above holds since μ4 is the stationary distribution of the Markov chain with transition matrix pr, If (<<a(<s)) = O, then (17) also holds given that (i(s',, aa)ssa') = (u((s')((() (sd) = 0. Equation (18) is also straightforwardly satisfied. It can also be seen from the equations above that the stationary distribution ü is unique.
22

---

The Number of Trials Matters in Infinite-Horizon General-Utilit, Markov Decision Processes
In summary, the limiting behavior of the extended Markov chain can be described by the Markov chain with transition matrix pa since the recurrent classes of both Markov chains are intrinsically related (with the same probabilities of absorption), and the stationary distributions for each of the recurrent classes R₃ of the extended Markov chain satisfy (s a) (s)))r((ass)
Thus, for the extended Markov chain and any (s, a), according to Lemma B.5, it holds that
H Σ
P
lim
1(;
A, =a) =Y(s,)) = 1,
H H
H
t=0
where Y(s.a) is a random variable such that, if (s, a) E then P(((a.)) = 0) = 1, and if (s, a) belongs to recurrent class R2
if y (s a),
P (F(sa)) =y)
if y 0, otherwise,
0,
and
ã lim P(S E Ri ~ Po)
++000
denotes the probability of absortion into recurrent class RS when the initial state So is distributed according to pn. Since there exists a one-to-one equivalence between the sets of recurrent classes both Markov chains, the probabilities of absorption into each recurrent class are the same in both Markov chains, and (r, a) = (s) s). holds that random variable Y(s. (s.a) can be equivalently described by (als), where Y, the random variable defined Lemma B.5 for the Markov chain with transition matrix pd
B.2.2. PROOF OF THEOREM 4.6
Theorem 4.6. Let M, be average GUMDP with e-strongly convex / and K E N be the number of sampled trajectories. Consider also the Markov chain with state-space S, transition matrix pr and initial states distribution po. Let R be the set of all recurrent states the Markov chain and R,...., Rr, the sets of recurrent classes, each associated with stationary distribution μa. For each s E R, let I(s) denote the index of the recurrent class to which s belongs. Then, for any policy ı Nss holds that
(xx
C
Σ malss) (p)())())
Var [B],
2K
B~Ba((aut))
SER
aEA
where B ~ Ber (p) denotes that B is distributed according to Bernoulli distribution such that PPB = 1) = p and
Ci((s) lim P(S Ri(Sy)So po)
the probability of absorption to recurrent class R((e) when So ~ Po-
23

---

The Number of Trials Matters in Infinite-Horizon General-Utility Markoy Decision Processes
Proof. For any policy
Hg it holds that
[K(TT) [xx(T) = =ETx [ddTw)] - - [aTTe]
No 2 ETK
(1)
JuTxx - dz 1
c ET
Σ ( 2
sES,aEA
Σ ETK ( - dz(0, (
27
aES,EEA
(Tx(ss1)))
VarTk
sES,aEA
K
C
Vary
1
Σ km
dr (8, (s,
2
K
aES,aEA
[dr(s.a)]
Varr
2K
sES,aEA
ETwCa [dr(s,a)²] - BT-cn (dr(s.u]²²)
2K
sES,aEA
where (a) follows from the strongly convex assumption and the fact that
x + V T (x - E(x)) + C | E[x]1
2
S(E + SE - E
where X is random vector.
Focusing on the term BT~C, [(rr(s_a)) we have that
(imm 1 H-1
27
RIace (ār(s) EIace
Σ 1(S ((=))=
H-20 H
( Ey, (HoT(al)))
= 2rr, [Y?]]
1(S = a). Step (a) above holds because: (i) from Lemma B.6 it holds that Let Zy = H1 I
(lim ZH (aaass)) 1, Zμ + (a)s)) almost surely (note also that ZHl S 1 for all H E N); (ii) since g(x)= = x² is continuous holds that g(Zx) + (als)())s) almost surely (note also that [g(Z < for all H E N); (iii from the bounded convergence theorem (Durrett, 2019, Theo. 1.6.7.) it holds that E, [g (lim Zμ)] Ey, (a(s)) Also in (a), Y, is distributed according to the probability density function defined in Lemma B.5.
For the term Exnç, [dy ]
2
via similar arguments, it holds that
Erwe, [(rr(s,a))]* ====_. BBy, ((S Talls) [(Y2))²
24

---

The Number of Trials Matters in Infinite-Horizonn General-Utility Markoy Decision Processes
Replacing both terms in our original lower bound yields
fk (T) - fT)(T) 2
Σ
A(als)2
Ey, [ Ey, ((G))²)
2K
sES,aEA
Σ
T Var [Ya]
2K sEB,
[(ass) Var (Y
2K
RER
(b)
T(als) (eeooooll((ppaa)))))))) (s)
2K
SER
Var Bar(a))
[B] Σ
((ass))H(s))
2K
SERI aEA
where in (a) we let R. denote the set of all recurrent states for the Markov chain with transition matrix pa and the equality holds because if s is transient then P(Y, = 0) = 1 and, hence, Var [Y,] = In (b), the equality holds since we can rewrite random variable Y, using a scaled Bernoulli random variable.
C. Empirical Results
In Algorithm we present the pseudocode of the sampling scheme used to approximate the different GUMDPs formulations, under both discounted and average occupancies. The different objectives can be approximated, for sufficiently large number of iterations N, by running Algorithm with the desired K, H, and parameters. Under the discounted setting, we vary parameters K, H. and y. Under the average setting, we vary K while setting & = and H = cc. Under both the average and discounted setting, we set K xo and H co to compute the infinite trials objective.
Algorithm 1 Estimating fK.H (T) via samples.
1: Inputs: N N (num. of iterations), K N (num. of trajectories), H E N (trajectories' horizon), and y (discount factor).
2: fo 0
3: for in {1...., N) do
4: (TI...., [i.....TK] ~ ST
5: (x) I-7 K
1-7 K
DHT 7 1'((s,, 8, an = a), Vs,
2k==
6: f + [ldx)-
N
7: end for
8: Return: FN
C.1. Empirical results for the GUMDPs in Fig.
We consider the GUMDPs depicted in Fig. I, representative of three tasks in the convex RL literature. Under MG we let ((eff] (s) (rightt|s,) 0.5, (right((s; 1 (zero otherwise), and π ([eff]|s>) s2) 1 (zero otherwise); for both M, and My,3 we let be the uniformly random policy. Figures 4, and 6 display the results obtained under the different GUMDPs illustrated in Fig. 1 for different y, K and H values. Figure 7 displays the results obtained for the three GUMDPs for different K and y values with H 00.
C.2. Empirical results for the GUMDPs in Fig. 1 with noisy transitions
We consider again the three GUMDPs illustrated in Fig. 1, but add small amount of noise the transition matrices of each GUMDP so that there is non-zero probability, at each timestep, of transitioning from given state to any other arbitrary state. Under Mf.1 we let π (left]ss) = π (rightt[so) = 0.5, (rright(s1) (zero otherwise); for both M and M we let æ be the uniformly random policy. Figures 8, 9, and 10 display the results obtained under the different GUMDPs illustrated in Fig. 1 for different y, K and H values. Figure 11 displays the results obtained for the three GUMDPs for different and y values with H oc and noisy transitions.
(zero otherwise), and π ([eff])s) (2) = 1
25

---

The Number of Trials Matters in Infinite-Horizonn General-Utility Markoy Decision Processes
7 = 0.2
= 0.6
= 0.8
-0.5
[ddrss
-1.
-1.5
10 H
20
20
0
10
H
H
K
K
[(4+)
Figure 4: (M standard transitions) Empirical study of f(dTx, .H) for different K, H and y values under GUMDP M with policy (1eft((8)) 0.5, <rright|s)) 0.5, π (right((s1) = 1, л (left[(2) = 1. The results are computed over 100
random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
7. 0.2
7 = 0.6
7 = 0.8
1.0
[(dTx.H)
0.5
0.0
0
10
20
0
10
20
10
20
II
II
II
K
K 2
K
K
10
f(d.)
Figure 5: (M22,, standard transitions) Empirical study of (d .H) for different K, H and y values under GUMDP M with a uniformly random policy. The results are computed over 100 random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
7
0.2
Y 0.6
7 0.8
0.75
(dTxx.t)
0.50
0.25
0.00
10
20
0
10
20
10
20
H
K
2
K
K
10
f(d))
Figure 6: (M, standard transitions) Empirical study of f (ddkk .t) for different K, H and y values under GUMDP f with uniformly random policy. The results are computed over 100 random seeds. Shaded areas correspond to the 95% % bootstrapped confidence intervals.
26

---

The Number of Trials Matters in Infinite-Horizon General-Utiliye Markoy Decision Processes
M f1
M 52
M
0.6
0.75
-0.5
f(dTs. HI H1000)
0.4
0.50
-1.0
0.2
0.25
0.0
0.00
0.2 0.4 0.6 0.8
1.0
0.2 0.4
0.6
0.8
1.0
0.2
0.4
0.6 0.8 1.0
K
K 2-2
K
K 10
f(d,)
Figure 7: (Standard transitions) Empirical study of (dTx == ) for different K and values with H = oc. The results are computed over 100 random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
0.2
2 = 0.6
0.8
-0.5
F(dTx. (1)
-1.0
1.5
0
10
20
10
20
0
10
20
H
H
H
K = 1
==2 K
K = 10
f(d.)
Figure 8: (M,.1, noisy transitions) Empirical study of fddrx .H) ) for different K, H and values under GUMDP M
with noisy transitions and policy =(left) so) = 0.5, (right 8o) = 0.5, (rightt|s)) = 1, (left) 82) = 1. The results are computed over 100 random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
7.
0.2
7 0.6
7 = 0.8
1.0
[(dTx.H)
0.5
0.0
0
10
20
0
10
20
10
20
II
II
II
K
K
2
K
K = 10
f(d.)
Figure 9: (M,.., noisy transitions) Empirical study of [( ,H) for different K, H and y values under GUMDP M, with noisy transitions and a uniformly random policy. The results are computed over 100 random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
27

---

The Number of Trials Matters in Mefnite--Horizon General-Utility Markoy Decision Processes
7 = 0.2
0.6
7
0.8
0.75
[( HI
0.50
0.25
0.00
10 H
20
0
10
20
10 H
20
H
K
1
K =
K
K 10
f(d.)
Figure 10: (M2.3. noisy transitions) Empirical study of fd H)) for different K, H and values under GUMDP M with noisy transitions and a uniformly random policy. The results are computed over 100 random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
M f11
M₁2
M
0.6
-0.5
0.4
f(dTa 1I o0)
0.4
-1.0
0.2
0.2
0.0
0.0
0.2 0.4 0.6 0.8
1.0
0.2 0.4 0.6
0.8
1.0
0.2 0.4 0.6 0.8 1.0
K
K=2
==5
K 10
f(d.)
Figure 11: (Noisy transitions) Empirical study of (dix. mm for different K and y values with // = oo and noisy transitions. The results are computed over 100 random seeds. Shaded areas correspond to the 95% bootstrapped confidence intervals.
28


Reviews:
[{"review_id": "h7HvTcUG4S", "reviewer": "Reviewer_EP7E", "summary": "This paper analyzes infinite-horizon GUMDPs, highlighting the critical role of the number of sampled trajectories in policy evaluation. The authors theoretically and empirically demonstrate that, unlike standard MDPs, GUMDP performance metrics significantly depend on the number of trials, presenting theoretical lower and upper bounds for both discounted and average settings. They establish conditions under which finite and infinite trial objectives mismatch, particularly emphasizing multichain versus unichain structures.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and concerns raised. We answer below the questions/concerns raised:\n\n- *\"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: \n   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.\n   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.\n\n- *\"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?\"* \n   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.\n   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.\n\nWe hope our answers addressed the reviewer's main concerns.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The paper assumes strongly convex and continuous utility functions with bounded domains. While mathematically convenient, realistic utility functions might violate these assumptions, potentially limiting theoretical findings’ practical relevance.", "experimental_designs_or_analyses": "Experiments rely solely on illustrative toy scenarios with deterministic and artificially simplified state-action transitions. This makes the empirical validation questionable for practical GUMDPs in complex environments.", "relation_to_broader_scientific_literature": "The paper extends and significantly clarifies the conditions under which finite versus infinite trials matter in GUMDPs, directly complementing prior theoretical work. It effectively highlights differences in utility evaluations across trial conditions, an issue previously underexplored in the literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "See other parts.", "other_comments_or_suggestions": "See other parts.", "questions_for_authors": "1. 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?\n\n2. 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H8w80Zk7aC", "reviewer": "Reviewer_EizD", "summary": "This paper focus on General-utility MDP (GUMDPs) generalizes the MDPs framework by considering convex objective functions $f$ of the occupancy frequency $d$ induced by a given policy.  The authors analyze the discrepancy between the finite-trials formulation $f_K$ and the infinite-trials formulation $f_\\infty$ in the context of infinite horizon discounted GUMDPs and average GUMDPs extending prior research by [1] that focus on finite horizon. \n\nReferences: \n\n[1] Mutti, Mirco, et al. \"Convex reinforcement learning in finite trials.\" Journal of Machine Learning Research 24.250 (2023): 1-42.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and concerns raised. We answer below each of the questions/concerns raised:\n- *\"(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].\n\n    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.\n\n    \n    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.\n    \n    We commit to clarify in the final version of the article the novel aspects of our work in comparison to [1].\n\n- *\"(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.\n\nWe hope our answers addressed the reviewer's main concerns.", "claims_and_evidence": "The claims made in the submission seems to supported clearly based on the proof sketch and their experiment.\n\n(1) **Remark 3.2**, analogous to Theorem 1 of [1], establishes that for a convex function $f$, the finite $f\\_K$ and infinite $f\\_\\infty$ trials formulations differs for both discounted infinite GUMDPs and average criteria GUMDPs. This result is derived using Jensen’s Inequality: $f\\_\\infty(\\pi) = f( \\mathbb{E}[ \\hat{d}\\_{\\mathcal{T}\\_K} ] ) \\leq \\mathbb{E}[ f(\\hat{d}\\_{\\mathcal{T}\\_K}) ] = f\\_K(\\pi)$. Furthermore, **Theorems 4.1** and **4.5** use GUMDPs example (1c) to demonstrate that for multichain GUMDPs with a strictly convex objective function $f$, the inequality $f_K > f_\\infty$ holds strictly for infinite horizon discounted GUMDP and average GUMDP respectively.\n\n(2) **Theorem 4.2** extends remark 3.2 assuming c-strongly convex function $f$ for infinite horizon discounted GUMDPs, to provide a lower bound on $f\\_K - f\\_\\infty$ via Jensen's gap bound.\n\n(3) **Theorem 4.3**, extending Theorem 2 of [1], considers infinite-horizon discounted GUMDPs with an L-Lipschitz function $f$. It establishes a high-probability upper bound on the difference between the practical finite $K$-trail $H$-horizon value function and the true infinite-horizon value function $| f\\_\\infty - f(d\\_{\\mathcal{T}\\_K,H}) |$ with Boole's and Hoeffding's inequality.\n\n(4) **Theorem 4.4** in contrast to Remark 3.2, proves that when the average GUMDP is unichain and the continuous objective function $f$ is bounded then $f\\_K = f\\_\\infty$.  This result is validated using the Ergodic theorem and properties of expectation.\n\n(5) **Theorem 4.6** extends Lemma 3 of [1] to average GUMDPs, providing a lower bound on $f_K - f_\\infty$ for c-strongly convex function $f$. The bound is expressed as the sum of the variance of the Bernoulli distribution of the recurrent states' probability.\n\nReferences: \n\n[1] Mutti, Mirco, et al. \"Convex reinforcement learning in finite trials.\" Journal of Machine Learning Research 24.250 (2023): 1-42.", "methods_and_evaluation_criteria": "The authors support their claims with three simple GUMDP examples. The example in Figure 1c is well-explained, and Theorems 4.1, 4.5, and Figure 3 effectively illustrate the discrepancy between the finite and infinite trial formulations with this example.\n\nHowever, the purpose of Figures 1a and 1b is unclear. While the figure caption states that all GUMDPs have deterministic transitions, the states in Figures 1a and 1b appear to have two distinct transitions each, raising ambiguity about whether these transitions correspond to different actions. Additionally, the authors assert that all GUMDPs in Figure 1 are multichain, but this is not explicitly justified. Providing a clearer explanation of what Figures 1a and 1b represent would help readers better understand their purposes.", "theoretical_claims": "It is unclear how the Hoeffding style inequality in the proof sketch and the full proof of Theorem 4.3 follows from Lemma 16 in [1], that proves the feasibility of the optimal policy. A more explicit explanation or a clearer connection between these results would help clarify the derivation.\n\nReferences:\n\n[1] Efroni, Y., Mannor, S., and Pirotta, M. Exploration-exploitation in constrained mdps. CoRR, abs/2003.02189, 2020.", "experimental_designs_or_analyses": "The authors' experiments primarily focus on simple tabular examples with varying values of $K$ trails and $\\gamma$ discount, and these seem to be correct. However, the analysis is limited to small problems, and it would be beneficial to see how the value function mismatch in larger domains.", "relation_to_broader_scientific_literature": "Although this work is similar to [1], which focuses on finite-horizon GUMDPs, it provides valuable insights into the convergence properties of infinite-horizon discounted GUMDPs and average GUMDPs.\n\nReferences: \n\n[1] Mutti, Mirco, et al. \"Convex reinforcement learning in finite trials.\" Journal of Machine Learning Research 24.250 (2023): 1-42.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Other Weakness:\n\n1. Note that this paper is an extension of the finite horizon work in [1] to analysis of infinite horizon discounted and average GUMDPs. The main weakness of the paper lies in its novelty, as it appears quite similar to [1] and uses many of the same techniques to derive its theorems. The paper does not clearly specify which aspects of the extension from [1] are particularly challenging.\n\nOther Strengths:\n\n1. The paper does offer a new insight in Theorem 4.4, showing that unichain GUMDPs satisfy $f\\_K = f\\_\\infty$ in average GUMDP.\n\n2. The paper is well-written, with good structure and readability.\n\nReferences: \n\n[1] Mutti, Mirco, et al. \"Convex reinforcement learning in finite trials.\" Journal of Machine Learning Research 24.250 (2023): 1-42.", "other_comments_or_suggestions": "The paper would be in a stronger position if it explicitly specified which aspects are identical to [1] and which parts of the extension present significant challenges. As it stands, it closely resembles [1] and applies similar techniques to extend the analysis from finite-horizon to infinite-horizon discounted and average GUMDPs.\n\nReferences: \n\n[1] Mutti, Mirco, et al. \"Convex reinforcement learning in finite trials.\" Journal of Machine Learning Research 24.250 (2023): 1-42.", "questions_for_authors": "Please address the questions :\n\n(1) Which aspects are identical to [1] and which parts of the extension present significant challenges.\n\n(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.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "avVYcqu1dv", "reviewer": "Reviewer_3gey", "summary": "The paper continues work in the area of the so-called general utility MDPs. The main contribution is the clarification that infinite horizon criteria will not close the \"finite vs infinite trial gap\" contrary to a suggestion by Mutti et al. (2023) who studied the gap in the finite horizon setting.\n\nSpecifically, the setting is as follows: Consider a decision maker who wants to pick a policy such that in $K$ independent trials, the expected utility assigned to the average of the empirical occupancy measures underlying $K$ infinitely long trajectories is maximized. Formally, if $d_k$ is the empirical occupancy measure (discounted or average) underlying trajectory $1\\le k \\le K$, \n\n$\\bar{d}_K = (d_1+\\dots + d_K)/K$ \n\nand the goal is to maximize $\\mathbb{E}_\\pi[ f(\\overline{d}_K) ]$ by choosing an appropriate policy $\\pi$. Here, $f$ maps distributions over state-action pairs to reals. One motivation to study this problem is to model risk-sensitive decision makers whose objective can be captured by a utility assigned to a state-action distribution.\n\nAs $K\\to \\infty$, since under $\\mathbb{P}_\\pi$, $d_1,\\dots,d_K$ are independent, by the law of large numbers, \n\n$\\bar{d}_K $ converges to\n\n$\\mathbb{E}_\\pi[ d_1 ]$ \n\nwith probability one as $K\\to \\infty$. Hence, by Taylor series expansion, when $f$ is smooth, $f(\\overline{d}_K)$ converges to \n\n$f(\\mathbb{E}_\\pi[ d_1 ])$ \n\nwith probability one as $K\\to\\infty$. The gap that the paper refers to is the difference between $\\mathbb{E}_\\pi[ f(\\overline{d}_K) ]$ and this latter expression.\n\nThe first result concern the discounted setting. Here, the first main result (Theorem 4.2) shows that the gap is lower bounded by an $\\Omega(1/K)$ term for $f$ strongly convex. The second main result (Theorem 4.3) shows that even if we truncate trajectories after $H$ steps and $f$ is convex Lipschitz, the gap is upper bounded by $O(\\sqrt{1/K}+\\gamma^H)$. The first result only applies to stationary policies.\n\nIn the average cost setting, focusing on stationary policies, the first result (Theorem 4.4) shows that the gap is zero for unichain MDPs provided $f$ is continuous and bounded. Next, the authors point out this does not necessarily hold for multichain MDPs (Theorem 4.5) and finish up with a general lower bound on the gap that is similar to Theorem 4.2 that applies to multichain MDPs (Theorem 4.6).\n\nFinally, empirical results illustrate the theoretical findings.\n\n## update after rebuttal\nMy assessment did not change after the rebuttal. The paper answers a well-defined question, asked in a previous paper, and is well-written. It is of interest for the community in the sense that the precursor paper hinted at some answer and this paper clarifies in a rigorous fashion whether that hint was correct. Yet, this question raised in the previous paper does not feel like a well thought out question -- as I explained it beforehand. Because of the merits of the paper, I still recommend weak accept -- take the paper if there is enough room.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and concerns raised. We answer below the questions/concerns raised:\n- *\"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.\n    \n    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.\n\n    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.\n\n- *\"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.\n\n- *\"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.\n\nWe hope our answers addressed the reviewer's main concerns.\n\n[1] - Zahavy, T., O’Donoghue, B., Desjardins, G., and Singh, S. -  Reward is enough for convex mdps. CoRR (abs/2106.00661), 2021.\n\n[2] - Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley \\& Sons, 2014.", "claims_and_evidence": "The general claim is that just because the horizon is infinite, the gap will not disappear. Theorems 4.2 and 4.6 make this precise. In addition, the empirical study also suggest that the gap exist. I think overall the evidence is strong.", "methods_and_evaluation_criteria": "The empirical study is reasonable and the results do make sense in the context of the paper.\nOne small methodological remark is that the authors somehow say they ran experiments with $H=infty$. How can this be? I suppose this was just approximated by taking $H$ large. Is this convincing? Well, Fig 2. suggests that this is a reasonable approach, but ultimately, I think it is better to admit that there is no way to study this empirically (or am I missing something)?", "theoretical_claims": "The claims are precise, they are believable. Theorem 4.3 (upper bound for discounted setting) is quite predictable; the strength is in the lower bounds. None of the results are surprising, but the lower bounds required some careful calculation. Skimming through the proofs of these, I believe they are correct.", "experimental_designs_or_analyses": "No issues; it is OK to run on these small MDPs; the plots are reasonably chosen.", "relation_to_broader_scientific_literature": "There is a sequence of papers studying these problems and the literature is very well cited as far as I know.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "**Originality**: Fair. The results have not been known, published. I guess the lower bounds are neat.\n\n**Significance**. Questions I would ask:\nQ1) Should we care about the finite trial objective?\nQ2) Should we care about the gap described?\nQ3) Are we surprised that there is this gap?\n\nOn Q1: While the finite trial objective with finite-horizon problems moves things closer to realism, the finite trial objective with infinite-horizon problems lacks realism: Making infinitely maps in the MDP is just not something that is going to happen in our world with finite resources and fixed speed execution. So why study this problem? Of course, the follow-up to this is to ask why study the infinite horizon setting to start with and the answer there is that the infinite horizon setting is chosen for elegance, generality, insight, and is an idealization and as such it has its own role. Yet, idealization moves against realism, so we get a contradiction.\n\nAnother answer to Q1 (and answer to Q2, as well) is that the finite trial objective appears to lead to \"hard\" problems. It is OK to point this out, but is this very exciting? Will we get algorithms that perform significantly better under the finite trial objective than if we instead consider the infinite trial objective? I have some doubts; the results show that under reasonable conditions the algorithms in the latter category will pay a price of size $1/\\sqrt{K}$. The constant may be large here, but it is hard to imagine practical scenarios where $K$ is small and the decision maker knows enough to run their finite trial optimizer to do significantly better than what is predicted by this gap.\n\nOn Q3: The gap is not too surprising. It is not hard to realize that infinite length trajectories will often \"do not wash out all randomness\". I am guessing Mutti et al. thought of the one nice case when this happens, hence their comment. Is it worth clarifying this? In as much as we care about the finite trial objective, yes.\n\n**Novelty**: The results are definitely novel; the tools used in the proofs are what one expects to see. Again, the lower bounds are a bit more interesting.\n\n**Clarity**: The paper is superbly well written, except for skipping over the questions raised above on why should we even care given that the infinite horizon setting is not even realistic and how can you even run experiments in this setting (this second is a very minor issue).", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M8YnP6h2VF", "reviewer": "Reviewer_dxJG", "summary": "This paper analyzes the impact of the number of sampled trajectories on the estimation of the return for infinite-horizon MDPs with a general utility function. The classical MDP setup corresponds to linear utility, and in this case there is no bias induced by considering only a finite number of sampled trajectory - the main result of this paper is to show that this does not hold for the case of general utility. The paper highlights this situation for the case of policy evaluation, and provides numerical experiments.\n\n## update after rebuttal\n\nI thank the authors for taking the time to respond to my comments. My overall assessment of the paper is positive and I will keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review, comments, and concerns raised. We answer below the questions/concerns raised:\n- *\"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.\n- *\"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. \n- *\"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.\n- *\"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.\n- *\"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.\n- *\"Recall the definition of $\\zeta_\\pi$\"*: We thank the reviewer for the suggestion. We will incorporate it into the final version of our manuscript.\n- *\"Line 212: is the convergence $f_{K,H}  = f_K$ as $H \\rightarrow \\infty$ uniform over $\\pi$\"*: Yes.\n\nWe hope our answers addressed the reviewer's main concerns.\n\n[1] - Zahavy, T., O’Donoghue, B., Desjardins, G., and Singh, S. -  Reward is enough for convex mdps. CoRR (abs/2106.00661), 2021.\n\n[2] - Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley \\& Sons, 2014.", "claims_and_evidence": "The proofs of the claims of this paper are sketched in the main body of the paper. More detailed proofs are provided in appendices.", "methods_and_evaluation_criteria": "The numerical experiments are restricted to a very simple setup (an MDP instance with a handful of states, as illustrated in Figure 1) but it suffices to provide a clear picture of the effects studied in this paper.", "theoretical_claims": "I checked the sketch of the proofs in the main body and they appear correct.", "experimental_designs_or_analyses": "As detailed above, I am fine with the numerical experiments. Perhaps it would have been nice to have studied a more structured/realistic MDP instance but the paper already does a great job on the theory side.", "relation_to_broader_scientific_literature": "This paper is related to the growing literature on general utily MDPs. The paper does a good job at providing a concise literature review. To some extent the paper is based on demonstrating that a suggestion from another paper (Mutti et al. 2023) is wrong (line 61:  *Finally, the authors suggest that the difference between finite and infinite trials fades away under the infinite-horizon setting*.)", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "* Strengths: well-written, mathematical sound, good literature review\n\n* Witness: the scope of the topic covered in the paper is quite restricted - only policy evaluation, and only the impact on the number of trials. Some findings appear trivial when stated in English, e.g. line 78: ``*We show, both theoretically and empirically, that the agent’s performance may depend on the number of infinite-length trajectories drawn to evaluate its performance*”.", "other_comments_or_suggestions": "* Why is there a minus sign in the definition of the expected discounted cumulative reward $\\langle d_{\\gamma,\\pi}, -r\\rangle$? Why not defining the optimization program on page 2 (arg min …) as a maximization? Is it because you’ll use convex functions $f$ afterward? Also, it should be $\\pi* \\in \\arg \\min$ instead of $\\pi^* = \\arg \\min$ since $\\arg \\min$ is the set of all possible optimal policies.\n\n* Redundant definition of item (i) before and after equation (3)\n\n* In equation (3), is the minimum always attained, even among Markovian policies $\\Pi_{M}$? Shouldn’t it be an $\\inf$? Also, can you provide refernece here again for the optimality of stationary policies for the case of discounted GUMDPs + average unichain GUMDPs?\n\n* Please recall the definition of $\\zeta_\\pi$ (line 194 + 200 + 210).\n\n* Line 212: is the convergence $f_{K,H} = f_{K}$ as $H\\rightarrow + \\infty$ uniform over $\\pi$?", "questions_for_authors": "N/A --- see my comments above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZV6mYzipCs", "reviewer": "Reviewer_u79Y", "summary": "The paper analyzes the impact of the number of trails in estimating the objectives for GUMDPs. For both the discounted and average settings, it is shown by examples that there are mismatches between the finite-trial estimates and the actual infinite-trail objectives. Bounds on the mismatches are provided, with numerical results supporting the theoretical claims.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review, comments, and concerns raised. We answer below the questions/concerns raised:\n- *\"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).\n\nWe hope our answers addressed the reviewer's main concerns.", "claims_and_evidence": "- Theorem 4.1 shows by an example that there is mismatch for the discounted setting in general.\n- Theorem 4.2 and 4.2 provide lower and upper bounds on the mismatch for the discounted setting.\n- Theorem 4.4 claims that there is no mismatch in the average setting if the problem is unichain under any policy.\n- Theorem 4.5 shows by an example that there is mismatch for the average setting in general.\n- Theorem 4.6 provides a lower bound on the mismatch for the average setting given the set of recurrent classes.\n- The existence of mismatches and their trends are illustrated in the numerical results.", "methods_and_evaluation_criteria": "Proofs are provided for the theorems.", "theoretical_claims": "The proofs and proof sketches in the main text seem correct, though not checking all details in the supplementary.", "experimental_designs_or_analyses": "Three simple GUMDPs are considered in the numerical experiments. Although they are simple problems, the results illustrate the mismatches in objective estimations. The noiseless vs noisy results provide an interesting observation for convergence and non-convergence of the mismatches when the problem is unichain or not.", "relation_to_broader_scientific_literature": "From the results of this work, we should be cautious when doing finite-sample policy evaluation.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "In Fig 3b, it looks like there are some discontinuities in the performance of $M_{f, 3}$ around $\\gamma=0.9$ 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yQXLToWfts", "reviewer": "Reviewer_ntsy", "summary": "This paper investigates how the number of trials affects policy evaluation in infinite-horizon general-utility Markov Decision Processes (GUMDPs) for both the discounted and average cases. For the discounted case, the authors demonstrate that a mismatch generally exists between the finite- and infinite-trial formulations and provide lower and upper bounds to quantify this discrepancy. For the average case, they show that the structure of the underlying GUMDP also influences the mismatch. Finally, experiments on three simple GUMDPs validate the theoretical findings.\n\n### update after rebuttal\nThe authors' rebuttal has addressed my questions. I keep my positive rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review, comments, and concerns raised. We answer below the questions/concerns raised:\n- *\"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.\n- *\"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.\n\nWe hope our answers addressed the reviewer's main concerns.", "claims_and_evidence": "The claims made in the paper are well supported by clear proof and the experiment results.", "methods_and_evaluation_criteria": "The proposed methods and benchmarks make sense for the problem.", "theoretical_claims": "I briefly checked the proof of Remark 3.1, 3.2, Theorem 4.1, 4.2 and 4.3. They look correct to me.", "experimental_designs_or_analyses": "The experimental design follows previous work (e.g., the choice of GUMDPs), and the results align well with the theoretical findings.", "relation_to_broader_scientific_literature": "This work contributes to the study of GUMDPs, providing the first analysis of the impact of the number of trials.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "**Strengths:**\n- This paper is very well-written, easy to follow, and self-contained. Sections 2 and 3 provide extensive background to prepare readers for the later derivations, and Section 4 is clearly structured to present the main results.\n- This work makes novel contributions to the study of GUMDPs, providing the first analysis of the impact of the number of trials.\n- The experimental results align well with the theoretical findings.", "other_comments_or_suggestions": "* 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.  \n* Line 425 (left): It would be helpful if the authors could demonstrate how the equality holds for $\\mathcal{M}_{f,2}$.", "questions_for_authors": "Please see comments to above questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers uniformly agree that this is an original, well-written, and novel work. There are no concerns about the correctness of the work. The only concerns are relatively minor. I urge the authors to address the concerns about the works significance when preparing the final version of the work.
Decision: Accept (spotlight poster)