Solving General-Utility Markov Decision Processes in the Single-Trial Regime with Online Planning
Authors: Pedro Pinto Santos
Alberto Sardinha
Francisco S. Melo
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement learning
Convex reinforcement learning
Markov decision processes
Sequential decision-making
Primary area: reinforcement learning

Abstract: In this work, we contribute the first approach to solve infinite-horizon discounted general-utility Markov decision processes (GUMDPs) in the single-trial regime, i.e., when the agent's performance is evaluated based on a single trajectory. First, we provide some fundamental results regarding policy optimization in the single-trial regime, investigating which class of policies suffices for optimality, casting our problem as a particular MDP that is equivalent to our original problem, as well as studying the computational hardness of policy optimization in the single-trial regime. Second, we show how we can leverage online planning techniques, in particular a Monte-Carlo tree search algorithm, to solve GUMDPs in the single-trial regime. Third, we provide experimental results showcasing the superior performance of our approach in comparison to relevant baselines.

Published as a conference paper at ICLR 2026
SOLVING GENERAL-UTILITY MARKOV DECISION PROCESSES IN THE SINGLE-TRIAL REGIME WITH ONLINE PLANNING
Pedro Santos
INESC-ID & Instituto Superior Técnico
Lisbon, Portugal
pedro pitro.ppnnto.o santtcsssnsttttttenntttt. ul ulisbba..p.......
Alberto Sardinha
Francisco S. Melo
PUC-Rio
INESC-ID & Instituto Superior Técnico Lisbon, Portugal fmelo8 inesc-id.
Rio de Janeiro, Brazil
sardinhaß inf. puc-rio.br
ABSTRACT
In this work, we contribute the first approach to solve infinite-horizon discounted general-utility Markov decision processes (GUMDPs) in the single-trial regime, i.e. when the agent's performance is evaluated based on a single trajectory. First, we provide some fundamental results regarding policy optimization in the single- trial regime, investigating which class of policies suffices for optimality, casting our problem as particular MDP that is equivalent to our original problem, as well as studying the computational hardness of policy optimization in the single-trial regime. Second, we show how we can leverage online planning techniques, par- ticular a Monte-Carlo tree search algorithm, to solve GUMDPs in the single-trial regime. Third, we provide experimental results showcasing the superior perfor- mance of our approach in comparison to relevant baselines.
INTRODUCTION
Markov decision processes (MDPs) have found wide range of applications in different domains such as inventory management (Dvoretzky et al. 1952). queueing control (Stidham 1978), or op- timal stopping (Chow et al. 1971). MDPs are also of key importance in the field of reinforcement learning (RL) Sutton & Barto (2018), where the agent-environment interaction is usually modeled by resorting to the framework of MDPs. In addition, recent years have seen significant progress in applying RL techniques to different domains (Mnih et al.] 2015) Silver et al.) 2017] Lillicrap et al., 2016), attesting the flexibility of the MDP framework with respect to jjjective-speciffcatio
However, despite providing a flexible framework concerning objective-specificatiin, previous re- search has shown that multiple relevant objectives cannot be easily expressed within the MDP framework (Abel et al.] (2022). Such objectives include, but not limited to, imitation learning (Hus- sein al. 2017 Osa et al. (2018), pure exploration problems (Hazan et al. 2019), risk-averse RL (Garcia et al. (015), diverse skills discovery (Eysenbach et al. 2018 Achiam et al. 2018). con- strained MDPs (Altman 1999 Efroni al., 2020), and adversarial MDPs (Rosenberg & Mansour 2019). All aforementioned objectives can be cast under the framework of general-utility Markov decision processes (GUMDPs) (Santos et al. (024).. GUMDPs generalize the framework of MDPs by allowing the objective be non-linear function of the occupancy (the frequency of visitation of state-action pairs induced when running a given policy on the MDP). Recent works unified such objectives under the GUMDP framework and proposed algorithms to solve GUMDPs with convex
objectives (Zhang et al. 2020 Geist et al. 2022 Zahavy et al. 2021).
Unfortunately, in GUMDPs, the performance of given policy may depend the number of trial- s/trajcctories drawn to evaluate its performance (Mutti et al.) (2023] Santos et al.) (024). In fact, the standard formulation of GUMDPs implicitly assumes the performance of given policy is evaluated

---

Published as a conference paper at ICLR 2026
over infinite number of trials/trajectories of interaction with the environment. This is problem- atic because: (i) the infinite trials assumption is violated in many practical application domains where the objective function depends on the empirical occupancy induced by small or finite set of trajectories; and (ii) in general, the optimal policies produced by algorithms from prior research may perform poorly when evaluated on limited number of trajectories, demonstrated by |Mutti iet al. (2023). To overcome this issue, previous research introduced a finite-trials formulation for GUMDPs where the objective function depends on the empirical occupancy induced by a finite set of trajectories (Mutti et al. 2023; Santos et al. 2024). Unfortunately, in the finite-horizon setting, Mutti al. (2023) show that computing optimal policies for the finite-trials formulation of GUMDPs computationally challenging, being significantly harder than its infinite trials counterpart. Specif- ically, the authors demonstrate that the problem can be reformulated as an "extended MDP" where the agent must keep track of the history of state-action pairs observed up to each timestep. MMutt] itt al. (2023) present preliminary results showing that optimal policies for the extended MDP, com- puted via dynamic programming techniques, outperform their infinite-trial counterparts. However, the state space of the extended MDP grows combinatorially with the horizon, limiting the scalability of the approach very small problem instances.
In this work, we introduce the first approach for solving GUMDPs in the single-trial regime, i.e., when the agent's performance is evaluated based on a single trial/trajectory. We consider an infinite- horizon discounted setting, which has been greatly adopted by previous research in the field (Zahavy) ctt al. 2021, Hazan al., 2019) and has found important applications in different domains where the lifetime of the agent is uncertain or infinite. We focus our attention to environments with dis- crete state and action spaces. Our key contributions are threefold. First, we establish fundamental results on policy optimization in the single-trial regime, addressing: (i) which class of policies suf- fices for optimality; (ii) how the problem can be cast as an "occupancy MDP" that is equivalent to our original problem; and (iii) the computational complexity of policy optimization in the single- trial regime, Technically, our results differ from Mutti et al. (2023) due to the inherent differences between -hoiite- discounted occupancies and the Emite-horizon occupancies considered by the previous work. Moreover, our occupancy MDP refines the extended MDP from Mutti et al. 2023), preserves optimality guarantees, and is better suited for practical implementation. Second, we introduce a Monte-Carlo tree search (MCTS) algorithm to solve the occupancy MDP, effectively solving the GUMDP in the single-trial regime via online planning. Our approach provably retrieves the optimal action at each timestep for a sufficiently high number of iterations. Third, we present experimental results showcasing the superior performance of our approach over relevant baselines across diverse tasks and environments.
BACKGROUND
2.1 MARKOV DECISION PROCESSES
MDPs (Puterman 2014 provide a mathematical framework to study sequential decision making and are formally defined tuple .M = (S, A, (Pa
A). c) where: S is the finite state space; A is the finite action space: (Po : a E A) is a set of transition probability matrices Pa, one for each action a E A: Po E ASS) the initial state distribution; and e : S x A + E is the cost function. For a given action a E A. each row of matrix P satisfies pd(s -) E ASS), encoding the probability of transition from state at the present timestep to any other state at the next timestep when choosing action a. The interaction takes place as follows: (i) an initial state Su is sampled from Po: (ii) at each step t, the agent observes the state of the environment St S and chooses an action .AA. Depending on the chosen action, the environment evolves to state St+1 E S with probability pa (st. and the agent receives a random cost o with expectation given by c(8s, a+); and (iii) the interaction repeats infinitely.
A decision rule ne specifies the procedure for action selection at timestep t. A non-Markovian decision rule n., at each timestep f, maps the history of states and actions to probability distribution over actions, i.e., ne : S x (S x A) - ((AA. A Markovian decision rule does not take into account the entire history and, instead, maps the last state in the history to distribution over actions, i.e., ne : S + (AA). Both non-Marte Markovian and Markovian decision rules can be deterministic if they consist of mappings of the type n, S (8 x A) + A n, : S - A, respectively.
2

---

Published as a conference paper at ICLR 2026
A policy ( ... is sequence of decision rules, for each timestep. If, for all timesteps, the decision rules are Markovian or non-Markovian, we say the policy is Markovian non-Markovian, respectively. Similarly, if the decision rules are deterministic or stochastic for all timesteps, we say the policy is deterministic or stochastic, respectively. We denote the class of non- Markovian policies with NN,, the class of Markovian policies with Tw, the class of hon-Markovian deterministic policies with 1KM and the class of Markovian deterministic policies with UM Finally, the class of stationary policies, 1ls, contains all policies such that the decision rule is the same for all timesteps. We let Iīş denote the class of stationary deterministic policies.
For given policy E IIN.. the interaction between the agent and the environment is a random process (so, ag, $1, a1....). We let h = (So, S0, ....... :.t) .ee) denote random history up to (in- cluding) timestep 1. We also denote with h4 = (80; 0o; 81, 01 8t)
(S x A) particular
satisfies: (i) TP 8o 8) = Po(s); (ii) P [s:+1 s' [h, ar] = pa (st, s'); and (iii) [a = a [1]] Ty. (a)))))) Let (2, F, Px) be the probability space over the sequence of random variables (so, 80, a!....) that satisfies conditions
history up to timestep f. The random sequence (So, ao. S1, 01,
(i)(íii) above (Lattimore & Szepesvári_ 2020), where F a sigma algebra. We write specific tra- jectories w E S2 with w (Su, Go $1, $1,01,.. ........... We denote with Px jst 8, also pul the probability of state-action pair (s, a) at timestep under policy x.
The infinite-horizon discounted setting. The discounted cumulative cost objective (x) E 1Σ:- 7'c(se, ax)], where E (0,1) is the discount factor and the expectation is taken over the random trajectory of state-action pairs (sn, äg, (1, generated by the interaction be- tween and the MDP. It is well-known that the class of stationary policies suffices for optimal- ity (Puterman 2014 Theo, 6.2.10) and, hence, we aim to find the optimal policy, x², such that arg min (T). The discounted state-action occupancy under policy is
(1 Σ P ist s, also Po).
The expected discounted cumulative cost of policy x can be written as (T) = c. dz, where d = [d= 4o),..., dz ($|s), ([Ai)]T and c [c($o, c(s)ss) [A)i) Then, the problem of computing the optimal policy becomes '- = arg min c dr. which can be formulated as linear program (Puterman 2014).
2.2 MONTE- CARLO TREE SEARCH
MCTS (Bronne al. 2012 Silver et al. 2017) is sample-based planning algorithm to approx- imate optimal policies in MDPs through sequential tree-based search. The search tree alternates between decision nodes, representing agent actions, and chance nodes, representing stochastic envi- ronment transitions. At each iteration, MCTS builds and refines a search tree by alternating between the selection phase, the al-
four phases: selection, expansion, simulation, and backpropagation. policy, often based on upper gorithm recursively selects actions at decision nodes according to tree confidence bounds, and samples successor states at chance nodes according to the environment's dynamics, until it reaches node that has not yet been fully expanded. Then, in the expansion phase, a new child node corresponding to an unvisited state- acte-nction pair is created. In the simulation phase, rollout policy (typically random heuristic) generates trajectory from the expanded node to estimate a Monte Carlo return. Backpropagation then updates the statistics (e.g., mean value, visit counts) along the path traversed during the selection phase. MCTS converges asymptotically the optimal action at the root under mild assumptions (Kocsis & Szepesvári] (006). [Shah et al. (2020) and Cömer al. (0255) establish polynomial regret concentration for MCTS- algorithms.
2.3 GENERAL-UTILITY MARKOV DECISION PROCESSES
The GUMDP framework generalizes seliit--seecfiiatiinn by allowing the objective of the agent to be written in terms of the visitation frequency of state-action pairs. This in contrast to the MDP framework, where the objective of the agent is encoded by the cost, function of acatin pairs.
We define an infinite-horizon discounted GUMDP as a tuple My = (S.A, (Pa : a E A}, Pa- f) where S, A. (Pa E A), and po are defined in a similar way to the standard MDP formulation.
3

---

Published as a conference paper at ICLR 2026
The objective of the agent is encoded by f A x A) + R, as function of state-action discounted occupancy d, as defined in equation 1 The objective is then to find
arg min f(d,). rT
We highlight that, when f is linear function, convex, then we are under the convex MDP setting (Zahavy et al. (021). In this work, we con- sider three different tasks, each associated with a particular (convex) objective function: (i) maxi- mum state entropy exploration (Hazan et al. 2019). where f(d) = d log(d); (d); (ii) imitation learn- ing (Abbeel & Ng 2004). where f(d) induced by behavior policy /3; and (iii) adversarial MDPs (Rosenberg & Mansour, 2019), where f(d) = (1...( d' C2 and {ci,..., CK} is set of K cost vectors satisfying ea E RISIIA), Nevertheless, our results apply any task that be modelled using the GUMDP framework. We refer to Zahavy et al. (2021) for a comprehensive list of the different objectives considered by previous works.
under the standard MDP setting; if f is
d dal and dg A(S AA is the occupancy
2.4 GUMDPS THE SINGLE-TRIAL REGIME
In this work, we consider a different objective from the one introduced in equation 2 While equa- tion depends on the expected discounted occupancy, d,, the objective we herein introduce depends on the empirical discounted occupancy induced by running a given policy on the GUMDP. This is particularly important, as practical applications often require identifying the policy that performs optimally when evaluated based on single trajectory of interaction with the environment (Mutti ctt al.
2023 Santos et al.) 2024). Furthermore, as we shall explain next, in GUMDPs the perfor- mance of given policy may depend on the number of trajectories or trials used to evaluate it (Mutti et al. 2023 Santos et al., 2024).
Discounted empirical state-action occupancies We consider the setting in which the agent inter- acts with its environment over a single-trial, i..,, single trajectory. For a given policy л E INN. we introduce the random vector d= f2 A(S A), which corresponds the empirical discounted state-action occupancy associated with the probability space (0,,F, P,,,, defined as
(s) Σ (1( 8, a, a).
where 1 is the indicator function. It holds that d₂ E[d"], for dx as introduced in equation | In practice, it is common to truncate the trajectories of interaction between the agent and its envi- ronment. We denote by H N the truncation horizon and let the empirical truncated occupancy, d= :Ω A(S x A), be defined as
#
d (s, a)
1-7
Σ 1=
11((s
8, - a).
(4)
1
H
Single-trial formulation for GUMDPs We now introduce objectives for GUMDPs that depend on empirical discounted state-action occupancies. The single-trial objective is defined as
(T R
(5)
and we aim to find x" arg min (T)) where II is arbitrary policy class we specify later. The single-trial truncated objective is defined as
(T, = E [f(d
(6)
We note that the single-trial truncated objective is more general than the single-trial objective. In particular, Fi, is equivalent to F, as H + 0o. The infinite trial objective, Fso. is defined as
Foo (T) f(dz) = f (E [d"]),
and we aim to find To = arg min Fo (T). We note that Foo is equivalent to the objective in equation 2 which depends on expected occupancies. The fact that Hy suffices for optimality follows from results on the possible state-action occupancies induced by different classes of policies (Puterman] 2014).
We call For the infinite trials objective because, the number of sampled trajectories/trials approaches infinity, the mismatch between GUMDPs that depend empirical and expected occupancies fades away.
4

---

Published as a conference paper at ICLR 2026
The mismatch between F1 and Foe Previous works pointed out important differences between the single and infinite trials formulations for GUMDPs (Mutti et al. 2023; Santos et al. 2024). In particular, it has been shown that, in general, the performance of given policy under the single and infinite trials formulations differs and, consequently, the optimal policy for each objective may also differ. This occurs because, since f may be non-linear, it happen that (x E [f(da) * f (E [d]))= = (TO We refer to Santos et al. (2024) for explicit lower bounds on the performance difference between Fi and Foo. Naturally, when linear, as is the case in standard MDPs, then the single and infinite trials formulations become equivalent due to the linearity of the expectation. However, due to the mismatch between the single and infinite trials formulations. and given that the single-trial formulation is particularly relevant in practical applications where policy performance is assessed based on single trajectory of interaction with the environment, we focus in this work on finding (approximately) optimal policies for the single-trial objective, F1.
3 POLICY OPTIMIZATION IN THE SINGLE-TRIAL REGIME
In this section, we establish the fundamental results that underpin the development online plan- ning algorithms to solve GUMDPs in the singletrril regime. Specifically, investigate: (i) which class of policies suffices for optimality; (ii) how we can focus on the truncated single-trial objective, Fi, to compute approximately optimal policies for the single trial objective, F1: (iii) how cast our single-trial GUMDP problem as an MDP in which the agent keeps track of the accrued occu- pancy at every timestep of the interaction with the GUMDP: and (iv) the computational complexity of policy optimization in the single-trial regime. We let Gap(T) = Fi (TT) m ETTxa Fi (T') be the optimality gap of an arbitrary policy π E ΣNN with respect to the single-trial objective troduced in equation Intuitively, the optimality gap measures how suboptimal a given policy л is compared to the best policy. Throughout our work, we make use of the following assumption.
Assumption 1. The objective function f is L-Lipschitz with L E Rt, i.e. [f(d)) f(d2)) S L||d] d for any di, d2 E A(S x A).
We refer to Appendix A for the Lipschitz constants the objective functions considered.
3.1 NON-MARKOVIANITY MATTERS
We start by investigating which class of policies suffices for optimality. We have the following result (proof Appendix B.I.
Theorem 1. There exists GUMDP M, with E (0, and L-Lipschitz convex objective such that (lower better):
1. F. (TS)) > (TTM) for some TM E II and any RT.. E IIs.
2. (T(M)) > (TTM) ( for some TNM E TNN and any TM E II--
The result above shows that, in general, the class of stationary policies is strictly dominated by the class of non-stationary policies, which is, in turn, strictly dominated by the class of non-Markovian policies. Hence, non-Markovianity matters, and must focus attention history-dependent policies. Our Theo. [ extends the result in Mutti et al. (2023), which considers finite-horizon GUMDPs, to the infinite- discounted setting.
3.2 COMPUTING (APPROXIMATELY OPTIMAL POLICIES BY RESORTING TO Fi.H
The result below (proof in Appendix B.2) establishes that the optimality gap OptGap(T) of any policy ΠNN can be upper bounded, up constant, by the optimality gap of policy for the single-trial truncated objective.
Proposition 1 (Optimality gap decomposition). For arbitrary π. E INN it holds that OpIGap(#) S FT,H(T))
min
(FT,)(TT)) H
xn Enlls
OptGap
where OptGap (TT) is the optimality gap of policy n under the single-trial truncated objective with horizon H.
5

---

Published as a conference paper at ICLR 2026
Intuitively, the proposition above shows that resort to the single-trial truncated objective, as introduced in equation 6 to find an approximately optimal policy for the original objective defined in equation [ up to any desired tolerance. In particular. if is the optimal policy for the single-tring truncated objective, i.e., OptGap (T)) = O, then it holds that OptGap(z) S 8 " which can be made arbitrarily small by tuning truncation horizon H. Therefore, focus attention finding
arg min (T) = arg min E [f(d
(8)
*ellon
*
in order to keep the truncated optimality gap term OptGap, (T) low, which we investigate in the next section.
3.3 THE OCCUPANCY MDP: CASTING My AS STANDARD MDP
To derive our planning algorithms for solving GUMDPs in the single-trial truncated setting, we derive finite-horizon MDP based the original GUMDP. In particular, we consider the occupancy
MDP defined by the tuple Mo state space and
Ao, (Po), Po.o. co, H). where So = S x O is the discrete
1-1
= OOERISIAA: :
=
1=
(so, 00, 81) ES (8 A) 1I.IS O/
We denote state of the occupancy MDP with the tuple {s, o), where E S is state from the original GUMDP and o E is dimenninlll vector that keeps track of the running oceu- pancy of the agent up given timestep. Intuitively, the running occupancy records the empirical occupancy, as defined in equation 3 observed by the agent up to any timestep. We let Ao = A be the action space. We define Pn,o such that Po,o((s, o)) (s() if
[0, 1o, and zero otherwise. The dynamics are as follows: (i) component St+1 ~ pa (-(se) evolves according to the dynamics of the original GUMDP: and (ii) the rumning occupancy evolves deterministically as oc+-1 (s, a) = 7f + oz(s, a) if = and ar, and 0t+1(s, a) = or(s, a) otherwise. We emphasize that we not need incorporate the timestep in the state of the occupancy MDP since it can be inferred from the running occupancy by summing its entries. Finally, H E N denotes the horizon of MDP and the cost function co S O + defined as
if H, if = H.
co(fs, o}) =
Stationary policies To Ils for Mo are mappings of the type mo SX ((A). We let the cumulative cost under Mo be
Jo( = E Σ co((fs,
= E [c(o((ss,
(9)
where the expectation above is taken with respect to the random sequence of states ((so, (s }) under policy no. We let Jū min Jo(TO) be the optimal cumula- tive cost for Mo. We also note that the occupancy MDP possesses well-defined (optimal) value and action-value functions, which can be shown to satisfy standard Bellman equations (Appendix B.3).
We present the following result, relating states in Mo to histories in M, (proof Appendix B.4.. Proposition 2 (One-to-one mapping between histories in .M and states in Mo). There exists one-to-one mapping between histories lu (so, do, 81, (1, st) E S (S x A)' in Ms, with 0 5 1 H 1, and states {8,0) ) E x O in My.
An important conclusion that follows from the result above is that there exists a one-to-one mapping between non-Markovian policies for M2 and stationary policies for Mo. This holds because every state in Mo is uniquely associated with particular history in M, (and vice versa). With this in mind, we now state the following result (proof in Appendix B.5). which connects the problem of solving the occupancy MDP and the problem of solving the single-trial truncated GUMDP objective.

---

Published as a conference paper at ICLR 2026
Theorem 2 (Solving My is "equivalent" to solving Mo). The problem of finding policy E INN satissying OptGap (T) I for any BB. can be reduced the problem of finding policy To E ITs satisfying Jo( - Jo I c. In particular, if T = arg min Jo(To), then the corresponding non-Markovian policy π in M, satisfies OptGap (T)) = O. Finally, holds that Opt Opt = Jo(=o) - J where To is the stationary policy for Mo associated with the non-Markovian policy π for M₁-
Intuitively, the result above tells us that it suffices to search for an approximately stationary optimal policy for Mo. since such a policy corresponds to a non-Markovian policy that is approximately optimal for My. In particular, an upproximately optimal policy for Mo can be seen as non- Markovian policy for M that compresses the history up to any timestep into a running occupancy. This result demonstrates that maintaining the running occupancy up to any timestep is sufficient to achieve optimal behavior in the single-trial
sorccated-horzoon regime equation
Remark 1 (Deterministic policies suffice for optimality). Since the class of policies 1I2 suffices for optimality in standard MDPs (Puterman 2014), we know that at least one stationary deterministic policy To E Iº for Mo satisfies To) Jo = 0. i.e. To is optimal for Mo. In light of Theo. 2 and Prop. 2 this implies that the corresponding non-Markovian policy E INM for M, which is deterministic, satisfies OplGapn = O, i..,, π is optimal for M,. Thus, we can focus our attention on deterministic non-Markovian policies when solving M, with objective Fi,H, i.e, for any GUMDP and horizon H N. it holds that milx (T) mingens, (T).
Given Theo. 2 we consider planning algorithms solve the occupancy MDP. Unfortunately, solving the occupancy MDP poses some challenges: (i) the cost function of the occupancy MDP is rather sparse since it only non-zero at the last timestep: (ii) the size of the state space of the occupancy MDP grows combinatorially with H since every state in the occupancy MDP is associated with a possible history in My; and (iii) every state in the occupancy MDP is visited at most once per trajectory. Therefore, before investigating how we can solve the occupancy MDP in Sec.El we take a closer look at how hard it is, from a worst-case perspective, to compute the optimal policy in GUMDPs in the single-trial regime.
is worth noting that the occupancy MDP is conceptually related to the extended MDP proposed by Mutti et al.] (2023) for the case of undiscounted finite-horizon GUMDPs. While the extended MDP explicitly tracks the full history up to the current timestep, we show that this information can be compressed into rumning occupancy without sacrificing optimality guarantees. Since there exists a one-to-one mapping between states of the occupancy MDP and histories, the size of the state space of both formulations is equivalent. However, the compressed representation used by the occupancy MDP is more amenable to practical implementations since the running occupancy can be incrementally updated
the agent interacts with its environment. Despite these similarities, a key distinction lies in the setting: Mutti et al. (202)) consider the finite-horizon undiscounted setting, whereas we focus on the discounted setting. Discounting plays crucial role in our analysis (e.g.. Proposition 2 and it remains unclear whether similar results hold in the undiscounted case. This highlights a fundamental difference between our work and that of Muthi et al. (2023).
3.4 HARDNESS RESULT FOR POLICY OPTIMIZATION IN THE SINGLE-TRIAL REGIME
In the previous section, we established that it suffices to search over the class of policies T in order to attain optimal policies for any GUMDP and horizon H E N with respect to ob- jective (T))
E []] We now show that there exist GUMDPs for which solving T = arg min Fi,H(m (TT) can be computationally hard. More precisely, prove that the prob- lem of deciding whether there exists policy π E IPM such that Fi, (T) & X, where À E R is a threshold value, is Narda
Theorem 3 (NP-Hardness of policy optimization in the single-trial regime). Given a GUMDP with objective Fi,H H and a threshold value À E R, it is Na-d to determine whether there exists a policy T E M satisfying FT,H(T) S X.
Proof sketch. (Complete proof in Appendix B.6) We reduce the subset sum problem to the policy existence problem in GUMDPs with objective Fi, The subset sum problem asks whether, given set N (No, Bi,..., 1 of N non-negative integers and target sum k E N, there exists
7

---

Published as a conference paper at ICLR 2026
subset of N whose elements sum to k. We map every instance of the subset sum problem GUMDP such that at each state s,. for E {O.....N .N 1), the policy т E IRM needs to decide between selecting: (i) Ginclude thereby including n, in the sum; or (īi) Onoe include. thereby excluding n, from the sum. Then, we set H 2 N and let f(d) = (n d - k)) where d denotes a discounted occupancy that captures information regarding the actions selected by the agent each state 8;- We construct vector
RISIIA such that n d equals the sum of the numbers selected by the policy. With this construction, the objective satisfies f(d) = if and only if the sum of the selected numbers equals k. By setting
O. we are asking whether there exists a policy such that Fi, .r (T) 0. Since f(d)- = 0 if and only if the selected numbers sum to k, the reduction is complete.
We note that the objective function f used in the proof of the result above is Lipschitz and (strictly) convex. Thus, result shows that, even for smooth convex objectives, the computational hardness of computing the optimal policy in the single-tria trial regime is NP- Mutti et al. (2023) present a hardness result for the single-trial optimization problem in the case of undiscounted finite-horizon GUMDPs. Our theorem extends this result to the discounted case. In addition, our proof is signifi- cantly simpler- a one-step reduction compared to the NP-hardness argument in MMutti al. (2023), which relies on complexity results for partially observable MDPs. Furthermore, our result is more informative, as shows that the hardness persists even when the objective is smooth and convex.
With the above hardness result in mind, we next explore how to develop practical planning al- gorithms for our problem. Naturally, in a worst-case sense, these algorithms may require a non- polynomial number of steps to retrieve the optimal policy. Nevertheless, our results show it is possible to develop practical algorithms that are superior in comparison to relevant baselines.
4 ONLINE PLANNING FOR GUMDPS IN THE SINGLE-TRIAL REGIME
In this section, we investigate how we can solve the occupancy MDP introduced in the previous section by resorting to online planning techniques.
As previously shown, solving a GUMDP in the single-trial setting is closely related to solving a corresponding occupancy MDP. This connection allows us to employ an online planning approach in which, at any timestep t E {o..... H 1} of the interaction with the occupancy MDP, the algo- rithm receives the current state {st, o: ). The online planner then expands look-ahead search tree where the root node corresponds to state {st, o.). After a given number of iterations, the planning algorithm selects action to execute in the environment; depending the selected action, the vironment evolves to a new state, and the process repeats until timestep H. This online planning strategy is particularly effective, as it allows computational resources to be focused on computing (approximately) optimal actions only along the specific trajectory experienced by the agent. This avoids the prohibitive cost of computing an optimal policy for every state of the occupancy MDP.
4.1 MONTE- CARLO TREE SEARCH FOR GUMDPS IN THE SINGLE- TRIAL REGIME
We employ MCTS algorithm to solve the occupancy MDP, As described in Sec. 2.2 the search tree of the online planning algorithm comprises decision and chance nodes. In the context of the occupancy MDP, each decision node corresponds an action A, while each chance node corre- sponds to a given state {s. o} E S x O of the occupancy MDP. At timestep of the interaction, the MCTS algorithm builds planning tree rooted the current state (st, (st,o.). following the four phases outlined in Sec. 2.2 at each iteration. We provide the following two remarks, which further charac- terize the convergence and regret of our proposed MCTS based approach for solving GUMDPs in the single-trial regime. To derive the two results below, we make the following assumption.
Assumption 2. The objective function satisfies Smin < fdd S fmmxx. for any d E A(S x A).
Remark 2 (Convergence). Under Assumption 2 for any horizon H E N, the MCTS algorithm provably solves the occupancy MDP as the number of iterations of the algorithm per timestep grows to infinity. More precisely, for any horizon H E N, we have that OptGap (MCTT)) = 0 as the number of iterations of the algorithm per timestep grows infinity, where we let TMCIS be the policy induced by the MCTS algorithm at each timestep. This result follows follows from our Theo, 2and Theo. 6 in Koesis Szepesvári (0066) by rescaling the objective function lie in the [0, 1] interval. Thus,
from Prop. / OptGap( MCTS)) S 8 8 Tmm
8

---

Published as a conference paper at ICLR 2026
61
Qu
Ro
61
90
RD
0
0.5
(oo, u5))
Lay doe
(ay
(zp oo)
Cos nsl
(a) M, (Entropy max.) and M,3 (Adversarial MDP)
M,, (Imitation learning).
(b)
(c) M costs (Adversarial MDP).
Figure 1: Illustrative GUMDPs. M₁, and M share the same dynamics but differ in the objective
function. In all GUMDPs, the chosen action succeeds with 90% probability and, with 10% probabil- ity, the agent randomly moves to any of the states. The behavior policy for M, 2 3( (0) = 0.8 and ((00 $1) 0.2. In (c), we plot the three cost functions, Ct, C2 and c3, of the adversarial MDP.
Remark 3 (Regret bound). For a given number of episodes nt and a sequence of policies OpiGap(T:) be the expected regret for the sequence =1 OpıGap n ( the truncated expected regret for the se- of policies and Ru(11, (m nn) 2 for any horizon H. there exists an MCTS-based -arss- algorithm quence of policies. Under Assumption such that, when applied solve the occupancy MDP with n expansion steps, yields a sequence Furthermore, from Prop. RiTI...... :T)) < O(1/vn + 7 This result follows from our Theo. and the works of Shah ee al. (2020) and Cömer et al. (2025), particularly Theo. 1 in Shahh et al. (2020) and Theo. 1 in Cömer et al. (2025), which establish polynomial regret bounds for MCTSS-ased algorithms.
(T.,.... m.), let (TI....,,
of policies (Ti::...; Rn) satisfying Ru (TI...., < =(1/v/l)
5 EXPERIMENTAL RESULTS
In this section, we empirically assess the performance of the proposed MCTS- based algorithm for solving GUMDPs in the single-trial setting. Below, we provide brief description of the considered tasks and environments. We refer to Appendix [ for a complete description of our experiments.
Tasks, environments, baselines, and experimental methodology We consider three tasks: (i) maximum state entropy exploration (Hazan et al.) 2019); imitation learning (Abbeel & Ng 2004); and (iii) adversarial MDPs (Rosenberg & Mansour (209)) We consider two sets of environments.
The first set consists of the illustrative GUMDPs depicted in Fig. each associated with one of the tasks. The second set of environments come from the OpenAl Gym library (Brockman et al. 2016). We consider the FrozenLake (FL), Taxi, and mountaincar (MC) environments. The framework of GUMDPs defined over discrete state spaces; hence, we discretized the MC environment using 10 10 grid with equally-spaced bins. For the FL, Taxi, and MC environments, the task of imitation learning consists in imitating an approximately optimal policy. We let = 0.9 and set H 100 for the illustrative GUMDPs and и 200 for the other environments. We perform 10 runs per experimental setting. We consider two baselines: (i) a random policy, TRandomi and (i) the optimal policy for the infinite trials formulation equation 2 T calculated by solving constrained optimization problem with objective f via a standard optimization solver. We denote the policy induced by our MCTS algorithm as TMCTS and consider 4000 iterations per timestep (results with other numbers of iterations in the Appendix C. Our code can be found here
Experimental results discussion We present our experimental results in Tab. As seen, across nearly all experimental settings, MMTS outperformed the baselines, showcasing the superior perfor- mance of our approach (the only exception is for the Taxi environment under the imitation learning task where the performance of TMсIS is similar to that of Toovve)) We highlight the gains attained by TMCTS in comparison to the infinite trials policy, To
6 CONCLUSION & LIMITATIONS
In this work, we contribute with the first approach to solve infinite-horizon discounted GUMDPs in the single-trial regime. In Sec. we provided the fundamental results underpinning policy optimiza-

---

Published as a conference paper at ICLR 2026
Table 1: Mean single-trial objective, Fi, (T), obtained by different policies, across tasks and envi- ronments. Values in parentheses correspond to the 90% mean conf. interval. Lower is better.
Adversarial MDP
Maximum state entropy exploration
Imitation learning
Policy
Mf,1
Fl.
Taxi
MC
M,,
F1.
Taxi
MC
Mr,
0.12
0,51
0.65 1001 mint)
0.72
0.05
0,07
0.08
0.18
1,23
Thtrddm
(096x130
(00 H000)
600 mui:;
(B01 s0on)
c 4000)
0.05
0.48
0.63
0,70
0.02
0,05
0.05
0,07
1.17
(002/482))
(001,001)
4000,
contan0))
(000,000))
0000 40003)
(801
c410.000)
0,01
0.40
0.59
0.61
0.002
0.02
0.05
0.04
(401,400
(00,0/0
(012,000)
(90014000)
(400 (000))
(800
(4000 +0000
tion in the discounted single-trial regime. Then, in Secs. aad to online planning techniques, in particular MCTS, to solve discounted GUMDPs the single-trial regime. Our work takes first step towards a broader application of GUMDPs in real-world settings where the agent's s performance is typically evaluated under a single trial. The key limitations of approach to solve GUMDPs in the single- trial regime simulator of the environment to sample transitions; and (ii) the size of the matrix that keeps track of the running occupancy may be impractical for GUMDPs with large state and action spaces. We believe such limitations should be addressed by future work, for example, by investigating methods compress the running occupancy.
we explored how can resort
(i) the MCTS algorithm requires
ACKNOWLEDGMENTS
This work was supported by Portuguese national funds through the Portuguese Fundação para a Ciência a Tecnologia (FCT) under projects UID/50021/2025 and UID/PRR/50021/202 (INESC- ID multi-annual funding), as well as Al-PackBot (project number 14935. ASSBOA2030-FEDER 00854700). Pedro P. Santos acknowledges the FCT PhD grant 2021.04684.BD. Alberto Sardinha acknowledges the CNPq Research Productivity Fellowship (PQ), with reference 31 312699/2025-5. The authors also thank the lab managers GAIPS for the support provided when running the com- putational experiments of this work.
REFERENCES
Pieter Abbeel and Andrew Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty-Firsh FFrst International Conference on Machine Learning, ICML '04, pp. 1, 2004.
David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward, 2022.
Joshua Achiam. Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms, 2018.
E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. CoRR, abs/1606.015500 2016.
Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in Games, 4(1):1 43, 2012.
Y.S. Chow, H. Robbins, and D. Siegmund. Great Expectations: The Theory of Optimal Stopping- 1971. ISBN 9780395053140.
Can Cömer, Jannis Blüml, Cedric Derstroff, and Kristian Kersting. Polynomial regret concentration of ucb for non-deterministic state transitions, 2025.
10

---

Published as a conference paper at ICLR 2026
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. The inventory problem: li. case of unknown distributions of demand. Econometrica, 20(3):450 466, 1952.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploiaaton constrained mdps. CoRR, abs/2003.02189, 2020.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function, 2018.
Javier García, Fern, and o Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):143711400 2015.
Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Olivier Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: the mean-field game viewpoint, 2022.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2025. URL https: www.
gurobi com
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum en- tropy exploration. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 2681-2691, 2019.
Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Comput. Surv., 50(2), apr 2017.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML 2006, pp. 282-293, 2006.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/9781 108571401.
T. Lillicrap, J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. CoRR, (bb//159.0099/// 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. Nature, 518(7540): 529-533, 2015.
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Convex rein- forcement learning in finite trials. Journal of Machine Learning Research, 24(250):1-42, 2023.
Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J. Andrew Bagnell, Pieter Abbeel, and Jan Peters. An algorithmic perspective on imitation learning. Foundations and Trends in Robotics, 7(1-2); 1-179, 2018. ISSN 9931-8261.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley Sons, 2014.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. CoRR, abs/1905.07773, 2019.
Pedro P. Santos. Alberto Sardinha, and Francisco S. Melo. The number of trials matters in infinite- horizon general-utility markov decision processes, 2024.
Devavrat Shah, Qiaomin Xie, and Zhi Xu. Non-asymptotic analysis of monte carlo tree search, 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui. Laurent Sifre. George van den Driessche, Thore Graepel. and Demis Hassabis. Mastering the game go without human knowledge. Nature, 550(7676):354-3555 2017.
Shaler Stidham. Socially and individually optimal control of arrivals to a gi/m/l queue. Management Science, 24(15):1598-161 1978.
11

---

Published as a conference paper at ICLR 2026
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
Inc. Wolfram Research. Mathematica, Version 14.2. Champaign, IL, 2024.
Tom Zahavy, Brendan O'Donoguue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. CoRR, abs/2106.00666 2021.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities, 2020.
12

---

Published as a conference paper at ICLR 2026
A LIPSCHITZ CONSTANTS
Table 2: Common objective functions found in the GUMDPs literature. In (f) we assume d is lower bounded by satisfying < <
Task
Objective (f(d))
I Lipschitz constant (T.)
MDPs/RL
d c,
CE RISIAA
max,,a (c(s,a)
Pure exploration
d' log(d)
llg((t) + + (t)
Imitation learning
||d d3l de A(S A) maXke (I.....)) KY d C₁
Adversarial MDPs
maxke (l...( {max., Iox (s,
Objective function f(d) c_ d It holds that (f(d,) - =
|c" (d) d2) = Σ [s(s,a))ld dd) S max [c(s, a)lldd dzll1-
max
s,a
8,0
Objective function f(d = d log(d) We assume is lower bounded by c, i.e., d(s, a) 2 c with 0 <E - for all E S A. We let ((d) Ex,a g(d(s, a)), for g(x) log(ar). We note that, g'(x) log(z) 1 and holds for any x [e, 1] that (x)x) s log(()) + 11. Thus, for any
$1 (, we have that
|| (manttrrr))
1g(z1) g((22)
I (xx)dx
min((s))2)) I ('(x)d
max )
maaxtusma))
19'(z)) dx < min(211z2) min(21122)
(log(e) + 1 dr
[log(() + 1| 22/.
Thus, for any d1, d2 E ASS x AA) lower bounded by 0 10<<< holds that
lf(d) f(d:)) Σ (o(d)(s) ( o(d2(s,
Ig(di a)) - g(d2(s,a))
8,0
Σ log(c) + +
(d, +
- - ds)
8,a
[log()) | d2llı
were (a) follows from the triangular inequality.
Objective function f(d) = I|d de holds that V f = 2(d - d3). Now,
| 2 max |d d 2 max ||: dell 4. ((E((AAA
dEA(SxA)
dEA(SxA)
Since the function f is continuous and differentiable over the simplex, which is compact, holds that L is valid Lipschitz constant it corresponds to upper bound the maximum magnitude of the gradient of ff over A x A).
B SUPPLEMENTARY MATERIALS FOR SEC. 3
B. PROOF OF THEOREM I
Theorem I There exists a GUMDP M, with y E (0, 1) and L-Lipschitz convex objective such that:
13

---

Published as a conference paper at ICLR 2026
1. F1(TT) Fi (TTM), for some TM E IM and any iTy E IIs.
2. (AMM)) > (TTM) for some TNM E NNN and any TM E IIM-
Proof. To prove our result, we consider the GUMDP depicted in Fig. 2 To simplify our proof, we consider state-dependent occupancies and denote an occupancy for the GUMDP above with the vector d = [d((s), d(s'), d(s²)]. The objective function is f(d) = d Ad, where A = diag((O, 1)), which is Lipschitz (over A(S) and convex. Under any trajectory it holds that 4-22 Hence, it holds that, under any trajectory, d(s*) + d((s)) = d(s") = (1 --7 Ei= 220+1 T-
1 4-21
1-72 1-7 Thus, we focus our attention to the value of the occupancy at state s', d(s"),
and let d((5)) 1-3 - d(ss). With this, we can define our objective as function of d(st)) only by
letting f(d(s=)) d( + ( d(s)))²
a²
1-6
Figure 2: Illustration of the GUMDP used in the proof of Theo. with S {sa, s' s²} and A
{a a²). The distribution of initial states is po(s") = 0, (u(s') = e, Pu())) = e, where we set 1/2.. All transitions deterministic and in states s and s² any of the actions takes the agent back to state s
For the first part of the Theorem it holds, for any my E IIs, that
Fi(T)) = E [f(
ao (s0))
(c) E
Tg fd
20, (s!))
si 1/00o (-1so..) iirss (1182).
pus (1122) ( (119g)
(b)
E
E
20,0000000000000 30 $1, 11.1 (87))
so so ( (-luu)
pnd (1100), m ( (
(- (1158) ( (oa)
(taa (o9))
(c)
E
E
f (1- 7) Σ 11(sst = =0t + + Jas
(it)
s0 pas (o
ao (
(a (xa)  or ood doaee oe ( )) tu Ps
1=
) 1)
(4)
E
(1 (1- Σ
11(ss =s') + 75 do
as.... (s!)
sompan (-1 (116)).. (....
(1
(oy) )oarril
te 1e
t=0
f (1- 7) (1(80- 5²) + +- 2 = =²) + 1144 (1444=5)) =)
E
11(s = = ( 10m (160)).. 1)
+ 7)B Σ
21 Pno (00) ( sempos (es))
5=
E f (1- 7) (1(so- = 5²) + 2 = st) + + 1 = st))
76
5 00- s 8 (100)))s))))
+ (1 (1sa) 1150 1 1-
s (les)
where in (a) we emphasized that the random vector d depends on random variables So, ag, S1, .... (b) follows from the fact that $5 = 5d with probability one for trajectories drawn from the GUMDP, i.e., for any trajectory the state timestep 5 is always s", and thus we can
14

---

Published as a conference paper at ICLR 2026
split and simplify the expectation. In step (c), we let d be the random vector defined as in equa- tion 3 for the GUMDP depicted in Fig. 2 but where Po(s") = and zero otherwise. Step (d) follows from Jensen's 's inequality since, for any values (so, an. $1 di...., 84, 04) E (S x A) the random variables of the outer expectation can take, it holds that E[g(d=))] 2 ((E where we
let g(x)) = [((1 - 7) Ei= (st 8²) + 72r), which is convex. Finally, step (e) follows from the fact that
(st = 8*) (129)
7 Pas [ = =']
sompro (-) (-10))) (f") )_._.
=0 7 m 1s0) + .07 0+ " (s(a"\s") +
= =s(("1>") (7 + +
=s(a"13") 221
t=
70
= =s(aa|s") 1-22
We can now explicitly write the expectation in the last step above, yielding, for any E IIs and while letting c = 1/2,
1 (111 (7) (1 ( (1- +- + =s(aa1s0)
76
(Ts) 2 2 (ss(a'1300
1
1-
76
+ + (1-17)) 72 +ッ* + 1s0
1 (-92)
7
T (s (a'al f (1 (1-7) 1 [ + Ts(a 1sa))
+ 2
1-
(1 (1- 1 + 74 Ts(a" =s(aa1s0) -
76
(1 (1-)) 3- (1*+ = 100)
+ f
1
1-
70
+ f
(1 (1- + T - 7-
+ 2 (1 -ss f ((1 1 [ (30) 100) 70 72
70
I (1--))) (
160)
1 1-
In summary, (I(T)) is lower bounded by the expression above for any policy Ts E Iss. Since f a quadratic function, the lower bound above is also a quadratic function with respect to variable ms((+115). Thus, we can calculate the minimizer of the lower bound above by computing the gra- dient with respect to =s(a²1s") and setting it to zero. It can be checked that, for any 7 E (0, Ts(a")s* 1/2 minimizes the lower bound above (we provide below snippet of Mathematica code that supports this claim). This implics that, for any Ts E IIs, Fi (TT) is lower bounded by the expression above evaluated IT (s0) 1/2, i...
2 2 2n² + 2x 27 + 27 - 2y 7
F (TT) 2
7)
Now, consider the non-stationary policy TM E Im that deterministically selects al at timesteps t = 3,,7,11 11,,,,, and deterministically selects a² at timesteps t = 1,5,9. It holds that
(TMM) = E [dd
15

---

Published as a conference paper at ICLR 2026
E [ (1 - Σ
t=0
= = -
+ [10-00/(0000000000--000000--0000
+...))
[+ Σ u+4 ) + (1- c)f (1- Σ 144
=f (1->) 7)
1=
1=
2 (u- |1
1
1 7
74 ))
+ 2 ( (1- 7)n*)
1 (
(4-2/²)
(1-
1 1+ - +78 (1 (1+ ??)2?
where in (a) we let e = 1/2 and simplified the sums.
To conclude, it holds, for any Ts E Ils and 7 E (0, 1). that
(TT) 2 272 + 2 2n + 27 - 20 + +2
1 1+ 122²
120--77+00 +
Fi (TM))
2(1 + 7)
(1 72)
which can be verified using a software for symbolic/algebraic computation such as Mathematica Wolfram Research). We provide snippet of the Mathematica code we used below.
Snippet of Mathematica code support the proof that Fi (TT) F1 (TM), VTT.
[nn]: tlo., q.l I- o'2 + Rin - g1/C - g-2:1 "1
(tal: hix 1. :- (1
g) (1 + g" g"4 xx 6/11 g22011, el
fCe ei (g'2 gh4 5/
g2251), g]1
0/211 x) 8) g12-- g-2 x=1g"6/11 g2211) 4)
Fro gi (1 g'4 4 1x111"6/11 -0"001---22233 922133, gl
e gi (9"2 1 (1 g"231,, g]
ti (g'6 xx1g6//1 -922),,,
0/21x x1 1f12) 8) xx g910)), 1
ELG - qi (x-10"6/12- e22011, gll
[In]: Simplsty SolieyyySoooeeeee Dihix, gl. x) -- 0. x11
[0m:1: Hix -> 1/251
[In]: alg_] (1/2)) g1-11 g'0/11 d'01), 8) (/2))2/11 10-104//11 o"01), s)
[nn]: Reduselaig] h11/2, gll
[Ou:1: g < 11 3 < 11921
For the second part of the Theorem holds, for any TM = (To; TI, .2....) E IT, that
Fi (TM) = EE [d
(a) E
f(
TM
(s)))
srop (-) (lpp) nitt (-161) sgupan (+1s1) (1gs1))ag (1192)...
samopo sa soratol (-1a0)
soroeo sam.p0.000 noo (180)) (80):
(b)
E
E
20.0000
(st))
ag
(115")
te boadrree ( (eu) wit (11)) perree
(1|8) ia ata ( (aa)
E
f
IE
to. B0, B1.... (8)))
simppss (-10)) 1
ieseeree (aaa o trndtnitt// (8a)
tir (oso) ( Doe- ro tey on
yooo (os,
(111)
~ is ///
didcoe yorooo (aa)) (oo)
E
f
E
(1 - 7) Σ
7t 11(s = =2t)
ag (-19), somppns (- (100)
pocdd (f oo ) mie (1911 ).
End.i tel J. met (ag)
t=0
I.
(1 7)
1(50 = 8²) + 1 1S2 = s²)
s1 (- iit (-1ss). 1)
Σ 7 1(s = 80) (3
+ E
(11
sg pan (111))ag (1192)
where in (a) we emphasized that the random vector d TM depends on random variables So, ag. S1, ....... Step (b) follows from the fact that Sq = S with probability one for trajecto- ries drawn from the GUMDP, i.e., for any trajectory the state at timestep is always 8", and thus
16

---

Published as a conference paper at ICLR 2026
can split and simplify the expectation. Step (c) follows from Jensen's inequality, following similar steps as those for the first part of the Theorem. Now, it holds that
E
(st = 8t)
(
PP TM [st = s4]
se )
3
0 0 + TT (s(aa11") + 0+ m t...
12T22 22 22 (s'1s").
For any policy TM, it holds that Ee 72th T2l 1 (a'1s |so) [0, |ا Hence, if we replace expression
asmitaa: 20), E Eiss 1s: = 8²)
with e, 1-2 for c E [0, 1], and show that
72
samp (-15
E ((a->)) (1660= +') = 8²) 7d
1- ))
so sompao (o 81 (-le (cleu) ( (-161),
pa (-10) (12)))))a
is strictly lower bounded by Fi (TNM) for given TNM E IINM, for any no, TI, E IIs and E [0, 1]. this implies that Fi (TTNM) is strictly lower than that of any possible π E Il.. For any no, TT, n2 Ils and E [0, 1). the expectation in the expression above can be simplified as
f (1 (1- [((00 = s') + 1($2 = s')+ +
?
))
80 mom a (: (a1)) semupns (11s1) (221) (s2)
1 1-72
= (a- (1 (1- 1 + 12 + c 1-7 73
7a
+e(1 () (s))) (1-7) 1 1 1 1-72
(1 )) (1 (1-7) (7 1-
74
(1 e)(1 (1 (s))f (1 (1)
(1-
(a)
TT (a>)9))) (s (1- 7) [1+7² + 0 74
0²= 74
(1-7)
T-
2 (1 क (a (()) (s (1--))
74
722 )) + ))
(1 7) ( (
74
1 [
where in (a) we let c = 1/2.
Now consider the non-marken markovian policy TNY E ПNN that: (i) if so s² then at timesteps t 1,5,9, 9, deterministically selects action a² and at timesteps = 3, 11.1.... deterministically action at: (ii) if 8g = s², then at timesteps t = 1,5, 9, ... deterministically selects action al and at timesteps & = 3, 7, 11, deterministically action a². We have that
Fj (TNM) E [f [d]
(1 (1-7) 7) Σ 1 =
E
+ +(1-e)f (11 (100000+++000+000000+++0+0000110 + - +...))
8 (1 (1
of
Σ
+ +(1 (1- c)f
(1- Σ
7 1042
1=0
(
+ 1
(1 (1
1-
17

---

Published as a conference paper at ICLR 2026
where in (a) we let e 1/2 and simplified the sums.
We now need to verify that, for any nı (aaalls)) E [0, 1l, CE [0, 1] and y E (0,
1 . (1 (1-7) (1+ + 7t T-73 ) + ss (1 (1-7) 72 + 1-
74
Tt (a (a'1>")
2
1 (5 (1-))) (1+
1 72 )) + (1 (1 (
+ -
n (a')s0))
2
(61)
1 f
1
+ 1 2 (4-2)1² (TNM).
As can be seen, the expression the left-hand side of the inequality above corresponds to weighted combination (with weights mi (a+|x²) and - Ti (a*))")) of components (i) and (ii). By re- sorting software for symbolic/algebraie computation such Mathematica (Wolfram Research) it can be shown that (i) /
+ H (4-)2")
Fi (TNM) and (ii) > 2
(TNM) for any E [0, and 7 E (0, 1). We provide the snippets of the Math- ematica code we used below. This implies that the weighted combination satisfies the inequality above for any n (a! [s9) [0, 1] and the conclusion follows.
1 (4
Snippet of Mathematica code to attest that (1) > Fi (TTM).
[Io]: fle.. 9_1 :- 0'2 (C 9)/(1 9g2)) -2
[inl min 9.1 (F/
-g)+(1 g'2 on 922133, gl
CCC ggx ox1g44/2 9'2)1), 911
[al] als_l io (/2) 4//0 4"4),, 91 (1/215E110 2110 9749, g2
[inl meduneinle, gl > nlg]l
1eg
le 1/2 (a 11 < 2259900111
11
to 162 lg < -1 1xgg6 01)
Snippet of Mathematica code to attest that (ii) > Fi (TTN))
[ill: flew
o'2
9)/11 9"21) 0)
[al] mlea q.l oe ( 91x 1x1g44/ 9(21)), 9f
fl(l - (ex (22))1, a]l
[In]1 nlg_l in (/2)-1(1 (1 (C-- 974), al (1/21-5111) 21101 2'4), a2
[aal:
[out]: inte,
atgil
<-1
-1-1
Ic 1/2 is ta < -1 -1 11<g
to 1/2 as la 41 -1
B.2 PROOF OF PROPOSITION II
Lemma 1. For any w E S2 TNM and H E N it holds that [{d))) s(d S 2I
Proof. For any w E Ω 1NN and e N holds that
(a) < L
-(d)))((d)) [l
T
d
F. l|1
(1-7) #-1
h
L
(1
Σ
wit 1- 1 1=0
w,
1
(1 -
80
= L
Σ
7' ((1 7 Hd d
+ (1 >) Σ / d
1 1- "|
t=
(1->) #-1 1-
(c)
Σ
7 [| - 2 )a - d d + + - 7) Σ
> || ||
t= H
18

---

Published as a conference paper at ICLR 2026
Ø-1 > | + Ly
L
where: (a) is due the T--L.ischitz assumption; in (b) we used d -1-) 1) d'd where d d (s,, a) (ss 8, at a) is the empirical occupancy induced by the trajectory timestep t and d = - (111-)/(11-0 - Ei=o " Step (c) follows from the triangular inequality.
Lemma 2. If is L-Lipschitz then it holds, for arbitrary x E INM and E N, that
[F((z) (T, S 2T
Proof. It holds that, for arbitrary NN and H N,
P [F)()) (T)
EE [[[[d=]] EE [f(d).))]
IE [s(dd) s(d
E []f(dd) -f(dm.))]
Σ P+ (w]l(()))) - l(d
WER
(b)
< 2
where: (a) follows from [E[X]| S B| and (b) due to Lemma
Lemma 3. For every GUMDP My with L-Lisschitz and H N, if arg ee Fi (TT), then it holds that OptGap(T*) S 4Ly".
Proof. As shown in Lemma 2 Fi (T) (T,)(T)) 2 for arbitrary и. From such inequality,
infer that (T) 2L I Fi (IT), VT INN. i.., function Fi, (T)
2L lower
bounds function (1)... We provide visual illustration of F1 and F1H H in Fig.
3 Le
arg min, (T. It holds that
( min (T)( 2L S min (1(T) S F1 (T7).
(b)
(T)((T)) - -((""")>"""__) min
where (a) follows from the fact that (T) 2L lower bounds F1 (T); and (b) from the fact that min, (T) S Fi(7), Va' (from the definition of minimum). We illustrate the inequalities above in Fig. Finally, we note that
(Fi,H(TT)) ((F'))(FF.n(TT)) 2 = Fi(TT) (T,H( + 22 Fi(=')
< [1F((=)) (T)H((T)) )1 2L
< 4L
The above implies that
OptGap(z*)= =F((=') min Fi(x) S 4LA",
as illustrated in Fig.
Proposition I
Optimality gap decomposition). For arbitrary π E I it holds that
OptGap(T) S (T) min Ellss (FI.(TT)) 4
(10)
OptGap
where OptGap (T)) is the optimality gap of policy n under the single-trial truncated objective with horizon H.
19

---

Published as a conference paper at ICLR 2026
(i(T))
(T) + 2
Fi.H (T)
Fi (x*)
} OptGap ()t)Gap(*)) (x*)
FI,H(T) (T) 20,
min, Fi(
447
Fi, - -
NNM
π
Figure 3: Illustration of objectives Fj and Fi,H, as well as the relation between different quantities of interest for the proof.
Proof. Let zh = arg min NETTM (T. THe is optimal with respect to the truncated objective. It holds that,
OptGap(T) = E [f(d")] - min E [(dr')]
ETNM
[
B[f(d")] min
Ellsa
B [[(dd) E [(a= + |B [(a
[(ar)]]
- min
x Elll
IA3
[If(d=) E (((d)t) || +44
IA3 IAG IA3
[Bf(dd)] E [f(a || | [f(d EE [((d)i)) + +447"
2L," R + E [(( - E (( +4L7
E [f(a E f(d + [ - E [(ar))) + 661"
E [f(dm.")] E [(drir) +8
E [](dt.))]
min {R [f(d=m.H)] } 8T,
#lls
(T) min ElllI
(Fi.H(TH)++8) + 8L
where (a) follows from adding and subtracting E [dd))) and applying the triangular inequal-
ity; (b) follows from Lemma 3 (c) follows from adding and subtracting E [d) and apply-
ing the triangular inequality: (d) follows from Lemma 2 (c) follows from adding and subtracting
[ddri }] and applying the triangular inequality; and (f) follows from Lemma
B.3 THE OCCUPANCY MDP: VALUE AND ACTION-VALUR FUNCTIONS
For a given policy To E Ils, the interaction between the agent and the occupancy MDP gives rise to random process ((so, ) ao, (si, ) a ai...., (SH, (SH, ) such that:
1. IP [ss0 )o} (so, ) po.o (50, 0o))
2. IP [18+11, 0++1 = (8', o') 0o), ao. ao...., ......,,s,, (st, or), = Po (1), (6,,)
3. IP [a, = altsu, ) ag ..... (s,, o. = To(aa oz))
We let Fo, ) be the probability space over the sequence of random variables (fsn, ) ap, {sr, o1). aj.... {sn, on that satisfies conditions 1-3 above. We write specific tra- jectories wo fo. with wo = ((so, ) on (11,0)), a1, ....... {8H, 0n)) We highlight that the
20

---

Published as a conference paper at ICLR 2026
probability of given trajectory wo Gg under stationary policy To Ily be calculated mg (wo) po.0({50. )o)) to00al(s0. oo)) ((so, oo), (si, 01))
10 0H-1)) Po" (($H-1,-0-11 {S 0z)).
To streamline notation introduce the mapping evolution of component o of the state, defined as
8 0 A O that describes the
(o(s,a)+7*
if =f otherwise,
[a(s, o, (0. (((s,a)
where lo]s,,' denotes the value of entry s', for vector o, i... [ols o(s',a))
The value function under Mo. for any E {O..... HJ. is defined as
H
(fs,(s = Em
Σ
colfse, or ost oit -
(11)
= Eo [Co((SH, 0N
(x)) (s), 0.) =s,,
(12)
and the optimal value function, for any I E (o,...,,H. H). as (1,, o)) = min men (f8, The action-value function under Mo. for any E (0, (O..... H 1}. is defined as
H
(1s, = Emo Σ
colfsr or }) {se, o.} = (s.
-Ero [Co((S,, on }) 0.) = 08, aa
and the optimal action-value function, for any t E (O...., H - 1}. as (is o). = min ({s, a). We emphasize again that subscript & can be dropped from V, (ts, o)), ((,, o)), (T o), a) and (is o), a) as can inferred from o. Finally, we note that value functions, optimal value functions and optimal oction-value functions satisfy the following set of Bellman equations:
(T Σ To(a)(s,0))
Σ ('(ssss) P (P()::))((((l)lloo..o.)))) e (O...., ..... H 11
aEA
WESS
min aEA
(' P(( We (O. H
(i(1s,0),a) Σ pa (
(O... -1
x'ES
((((),0),a) Σ
pa (s'sss min
(ft We e (O...., H -}.).
d'd
S'ES
B.4 PROOF OF PROPOSITION
Lemma (Linear independence of exponential functions over E). For any x RR, L N, IR, and distinct Ao...., At-1 E IR, if Et-) crede 0 then eo = Ci = CL-1 = ie., the exponentials edaz @22-1 are linearly independent over R.
Proof. Let f(x) = Ei- Ge It holds that tiate f to obtain the following set of equalities:
Ih- cedRedee We can repeatedly differen-
Ge Ar Ar = 0,
I-
Σ
Ar Ar =====0 0,
1=
21

---

Published as a conference paper at ICLR 2026
T-1
Σ G=
L-1 Σ
c
1-
- O.
1
The set of equations above can be rearranged as follows
1
A
X
Ag
GetR
X
X
X
o2e
(13)
X
X
CL-1C
The square matrix above is known as the Vandermonde matrix and, since all Ao...., A are distinct, the matrix has a non-zero determinant (hence it is invertible). Therefore, multiplying the equality above by the inverse of the Vandermonde matrix on the left we obtain
cpe
(14)
C1-1cAR-110
Since functions ed 1 are always positive, we have that cp = 61 =... Cr.-1 =0
Proposition 2 (One-to-one mapping between histories in My and states in Mo). There exists one-to-one mapping between histories lu (50, ags $1, 01 ..,,,, E S (S x A)' in M,, with O and states {8, 0} E S x O in Mo.
Proof. For a given history h4 (sp, ao; $1, .1...., .1) S (Sxx) in M₁, with < H consider the mapping defined below that associates h4 to given state (s E S x O for Mo by letting
1-1 st and ass = - s. vs A.
(15)
We aim to show that the mapping above is bijection between the set of possible histories in M, and the discrete state space O in Mo. Clearly, from the mapping above defined, each history hu in M, is associated with unique state in Mo- Thus, what remains is to show that any two states {81, } and {52, 02) for Mo are equal under mapping equation 15 if and only their associated histories h and h² are equal. We now make two observations. First, for given state {s, o} in Mo. component s is directly related, through mapping equation 15| to the last state in the history hy Second, each history hı (so, ao $1, .1,..., .i) will yield through mapping equation 15
running occupancy o satisfying E., o(s, a) = :-²:: thus, histories fy with different lengths will yield different o-vectors. Hence, we only need to show that two running occupancies and o2, associated with histories h and 1.2 (both of length 1), respectively, are the same if and only if their histories up to timestep - I are the same:
If histories h' and h of length are the same, then it should be clear that their respec- tive running occupancies, as defined through equation [5] are also the same.
If two running occupancies O₁ and O2 are the same, then their associated histories are also the same. prove this implication, we focus our attention to given entry (s, of the vectors and 02. Running occupancy
is associated with arbitrary history h1 (s) ap $1 ...a......)) running occupancy Og is associated with an arbitrary history 2 (Sp, ag. s .........5.). If og then, for any S, E A. (8, a) 02(s, a)
22

---

Published as a conference paper at ICLR 2026
1-1
1(s = s, =a)
-
7'(( = =, = = a)= = 0
1=0
7 (1(s) = = aa) 1ss s. a)) =0
t=0
na= = 0,
where in (a) we let o E {-1,0, 13. Now, the only solution to the last equation above is Co Ci ... q-1 = 0, which implies that (s; 5, s,a; =a) 1(s 8, aa = a)
for all 0 < < 1
and hence, the histories are the same. The fact that co = Ci =
Qt-1 = is the only solution the equation above follows from Lemma by letting L
x = 1, and X = In())t (which implies that all X are distinct for y E (0,1))
Thus, we conclude that there exists a one-to-one mapping, as defined in equation 15 between every possible history in MM up to timestep H - 1 and states in Mo.
B.5 PROOF OF THEOREM 2
Theorem 2 (Solving My is "equivalent" to solving Mo). The problem of finding a policy π E NNN satisfying OptGap (T) I c, for any e E Bÿ. can be reduced to the problem of finding a policy wo E Iy salisfying Jo(mo) J0 S t. In particular, if T arg minm Jo(To), then the corresponding non-Markovian policy π in M, satisfies OptGap, (T) = O. Finally, it holds that OptGap (T) = Jo( - Jo. where To is the stationary policy for Mo associated with the non-Markovian policy ι for M₁-
Proof. We start by showing that, for any horizon H E N and policy E 1INM. it holds that
(T, Jo(To),
for (I.:(T) as defined in equation and (TO) as defined in equation 9 where To is the stationary policy for Mo associated with the non- Mon-Markovian policy ι for My.
For any H E N. finite-horizon random trajectories (so. ag. $1, S a4-1) in My are associated with the probability space F.P.). We write specific trajectories as w E Ω with = (so, 0o, 81, ,1;...,,811 8,-1, a1)) We highlight that the probability of given tra- jectory w E Ω under policy क E ПNN can be calculated as Pz [M) = po(so) T(a ho) pao (1) I(a
(s1, ... s... Pun-2 8H-1) hand, random trajectories (fso, )o), ao, (s1, 0,,, al...... {SH. oн}) in Mo are associated with probability space (Ro, Fo, We write specific trajectories as wo E lo. with wo (150, ) ao, ( ......, (.., ).
((a=-1hxx-])
On the other
We start by noting that, for any trajectory wo (170, on), do, 01,, ai...., (SH, on}) So.
po [wo] = Po.o(1so, )0 mo(ao 00)) 003) P ( ((90, ) (si, 01})
To To (ftp::/----..p.otssssssooo.o.--
(0 op) P 1(0 = o(so, on, ao))
(s0)
1(0, = [0. () (00o--.00))000000(((333
To 7o(0n-119=-1100--11 pma- |bg
1 = = QH
(50)
1(0 [0. [0.................. ( ho) p (r) .1 1 [ 0o) on)) ....
T - pmd (s 1( =
-
[w] pan 1 (|H 1 (0, (0...., 0)) 1(0 = a 0o. 00, an))
1 1( = a a 0g - -= 1))
where in (a) we note that component o of the state is initialized as a zero vector and then determin- istically evolves according to σ; any sequence of o-vectors that does not evolve according to a has
23

---

Published as a conference paper at ICLR 2026
zero probability under probability measure Po In (b) used the fact that any stationary policy To IIs for Mo can be mapped to a particular non-Markovian policy æ E Ιlx in My. In (c) recall that, for w (Sn. ag: 81, ................................ - 11,,,, F7 [w] Po(so) (aaoloo) P 81)
a (as h1) pe: (21, pa (8 - 811-111)
Now, for any stationary policy To E Ils, it holds that
(o)) [co((SH, on
Σ po colsss
WoEfo
Σ woEflo
Pr [ eed 18H-11881) 1(00 (o,....0)) 1(o: o(50, Oo, 00, ao))
1-7
=
( - 0H
Pr [w] pan- (8111,881) 1 ().....)) 1(0= (80, 00. 00. on))
1( = o 0H 01 az (d
Pr [ (d
Σ Σ (SH-1,
On.01
EO #8
1(00 = (0....0))) 0]) 1(0 = on, ..... 1(o = 0(5H-1100-1,
P. ( f (d
WEN
[f(d=
(T).
where in (a) we noted that, for any wo E Go, f (1 = (1. In (b), we split the sum f
over wo E 2g as sum over ss Ω2 sum over each possible vector O across all timesteps, and sum over the final state ви S (not included in wi. We also rearranged the sums by noting that some terms do not depend on some the sums. In (c) we note that the inner sums over the o-vectors and & equal one.
Hence, we have proven that, for any H N and क E INN, (T)) = JO(TT) holds, where, in light of Prop. 2 mo is the stationary policy for Mo associated with the non-Markovins policy for My. Given this result, and due to the one-to-one mapping between non-Markovian policies for M, and stationary policies for Mo. it holds for any INN that
OptGap,r(1 (T) (T.
min (F)H((TH)] Jo( min Jo(T(o). 7
Tx ENsa
and the conclusion follows.
B.6 PROOF OF THEOREM
3
Theorem (NP-Hardness of policy optimization in the single-trial regime). Given a GUMDP with objective FI,H and a threshold value À E R. it Ha-Hard to determine whether there exists a policy E 11M satisfying (T. < X.
Proof. We reduce the subset sum problem to the policy existence problem in GUMDPs with objec- tive Fi... The subset sum problem asks, given a set N = {no, ni...., N of N non-negative integer numbers and target sum & E N. whether there exists subset of the numbers such that the sum of the elements in the set is k. The policy existence problem is: given GUMDP with objective Fi. and a threshold value À E IR, does there exist policy
NM such that Fi, (T) < X.
We map every instance of the subset sum problem as a GUMDP as follows: (i) the state space is S = (80, 81,...,8M1 (ii) the action space A (Oinclude, Gnoe include ); (iii) pa (8441l8)) 1 and
24

---

Published as a conference paper at ICLR 2026
zero otherwise for any A and i {0.............. .0.....N. 1}. and (sNss(sN) 1 for any E A: (iv) Po(5o) = 1 and zero otherwise. We provide an illustration of the GUMDP in Fig. We describe a discounted occupancy for GUMDP above defined with the vector
d = [d[[ 50, Oinclude): , d( (noot-incuue)) ), d(81, (include), ) d(81, (not-include)
d(s - Oinclude), ), d(s N 1-1 Onot-include ), d(sN, Ginclude), ), d(s,, anox-inctude]]
Then, we set H 2 N and let f(d) (n T k)) where
H no, 0,
1 - -
1 1
(1 (1-7)7 n,, O, (1 "1N1,,=""N-110000000
It holds that
min F1. min E [[((d)H))]
= Σ Plulf(d WER
+ TETTR SM
TET Not
For given policy E INM only one trajectory w E Q has non-zero probability. The vector d associated with such trajectory can be described as follows, for any 8; E {O...., - 1]: (i) if state 8i, selects ainclude then entry d (s;, Ginclude) -- and d (st, (nox-inctude) 0; (ii) (sk,
if at state St, πT selects Gget-include then entry d.. (st, Ainctude) = 0 and entry d5." (ss, Qnot-imclude) = 1 The action selected at is irrelevant since it does not affect the objective value. The intuition behind the GUMDP above defined that, each state 8; for i E {o,..., N 1}, the policy needs to decide on whether to select action Oinelude and, therefore, include term n,, in the sum, or select action Guot-include and, therefore, not include term n, in the sum. We build the vector to reflect such behavior, where each entry in associated with the state and action Ginetude has normalizing constant of 1->" (I- account for the fact that the occupancy is discounted, as introduced in equation 4 Thus, it can be seen that every policy E IIRM will induce particular trajectory w E 52 with probability one and the sum of the numbers selected by the policy is given by dg. Finally, the objective is such that fdd 0 if and only if the sum of the selected numbers equals k. The policy existence problem then asks whether there exists a policy π E IN such that Fi,H (ι) < X. By setting À we asking whether there exists a policy such that Fi, Fi, (T) I 0. Since f(d)- = 0 if and only if the sum of the selected numbers equals k we completed our reduction from the subset problem to the policy existence problem in GUMDPs with objective Fi.H-
O
Ginchurla
Ginchtdde
Ginelurle
I
2
N
@nottinccuude
Goattinccade
Guoo-inncuucl
Figure 4: GUMDP instance used in the NP-Hardness proof.
C SUPPLEMENTARY MATERIALS FOR SEC. 5
C.I TASKS AND ENVIRONMENTS
We consider three tasks: (i) maximum state entropy exploration (Hazan al., 2019). where the objective is to visit all state-action pairs as uniformly as possible; imitation learning (Abbeel & Ng 2004). where the objective is to imitate a given behaviour policy; and (iii) adversarial MDPs RRoeebeer & Mansour 2019). where an adversary player selects the cost function that yields the highest cost. We refer to Sec. 2.3 for the exact definition of the objective function for each of these tasks. We normalize all objective functions to lie in the [0. 1] interval. We consider two sets of environments. The first set corresponds to the illustrative GUMDPs depicted in Fig. [ each associated with one of the tasks. The second set of environments come from the OpenAl Gym library (Brockman et al., 2016). We consider the FrozenLake (FL), the Taxi, and the Mountaincar (MC) environments. For the MC environment, spaced bins (we consider 10 bins per dimension). For the FL, Taxi and MC environments, the task of imitation learning consists in imitating and approximately optimal policy.
partitioned the original state space using equally
25

---

Published as a conference paper at ICLR 2026
C.2 EXPERIMENTAL METHODOLOGY, BASELINES, AND HYPERPARAMETERS
We perform 10 runs per experimental setting and report the 90% bootstrapped confidence interval. We let 0.9. We consider two baselines. The first baseline is the random policy, TRandom- The second baseline is the optimal policy for the infinite trials formulation equation 2 "olverr that we calculate by solving constrained optimization problem with objective using the Gurobi optimizer (Gurobi Optimization. LLC 2025). More precisely, to compute "oover we first solve the following optimization problem:
d' = arg min f(d), DED
D E SIAI d(s,a) 20,s Σ d(s a) (1-))po(s) + Σ Pe((sss)a(sss As}
Then, we let 7 (als) = ds) En d' a'). For the illustrative GUMDPs we directly use the respective initial states distribution, Po, and the transition probablity matrix, pa For the case of the OpenAI Gym environments we rum samling procedure to first estimate and P and then we feed the estimated quantities the optimization solver.
We denote the policy induced by our MCTS algorithm as TMCTS. We use 4000 as the default number of iterations of the MCTS algorithm, but we also provide results for 10, 20, 50, 500, 1000, (0000,3000 4000 iteration steps. We submit our code in the zip file with our submission.
Our experiments required modest computational resources, with each experimental setting running under an hour on a CPU cluster.
C.3 COMPLETE EXPERIMENTAL RESULTS
C.3.1
MAXIMUM STATE ENTROPY EXPLORATION, MY,1
0.15
MCTS planner
0.6
0.15
Fints)
0.10
0.2
0.05
0.0
0.00
0.00
Random
Random
Expansion steps
(b)
(c)
Figure 5: Maximum state entropy exploration, My (a) Mean single-trial objective Fi. (T) obtained by different policies. Error bars correspond the 90% mean confidence interval. (b) Dis- tribution of the single-trial objective Fi, (π) obtained by different policies. (c) Mean single-trial objective (T) obtained by the MCTS- algorithm function of the number of expansion steps. Shaded areas correspond to the 90% mean confidence interval. Across all plots, lower is better.
26

---

Published as a conference paper at ICLR 2026
C.3.2
MAXIMUM STATE ENTROPY EXPLORATION, FROZENLAKE
0.55
0.5
MCTS planee
0.7
0.50
0.45
0.45
0.40
0.35
1000
2000
3000
4000
Titusdon
Expansion
(a)
(c)
Figure 6: Maximum state entropy exploration, FrozenLake: (a) Mean single-trial objective (T) obtained by different policies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single-trial objective (T) obtained by different policies. (c) Mean single-trial objective Fi,H (π) obtained by the MCTS-basee algorithm as a function the number of expansion steps. Shaded areas correspond to the 90% mean confidence interval. Across all plots, lower better.
C.3.3 MAXIMUM STATE ENTROPY EXPLORATION, TAXI
0.68
planner
0.08
0.66
0.64
0.62
0.62
0.00
0.60
1000
2000
3000
4000
mire
Expansion steps
(c)
Figure 7: Maximum state entropy exploration, Taxi: (a) Mean single-trial objective FI.H ob- tained by different policies. Error bars correspond to the 90% mean confidence interval. (b) Dis- tribution of the single-trial objective Fi, (i) obtained by different policies. (c) Mean single-trial objective Fi.s (T) obtained by the MCTS- (CTTS-based algorithm function of the number of expansion steps. Shaded areas correspond to the 90% mean confidence interval. Across all plots, lower is better.
27

---

Published as a conference paper at ICLR 2026
C.3.4
MAXIMUM STATE ENTROPY EXPLORATION, MOUNTAINCAR
0.80
MCTS planner
0.75
0.75
0.70
0.70
0.70
0.63
0.65
1000
2000
3000
4000
Expansion
(c)
Figure 8: Maximum state entropy exploration, Mountaincar: (a) Mean single-trial objective (T) obtained by different policies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single-trial objective (i. obtained by different policies. (c) Mean single-trial objective Fi,H (π) obtained by the MCTS- algorithm as a function the number of expansion steps. Shaded areas correspond to the 90% mean confidence interval. Across all plots, lower better.
C.3.5
IMITATION LEARNING, M22
MCTS planner
0.06
0.15
Fie(e)
0.10
0.01
0.04
0.05
0.02
0.02
3000
4000
Random
Random
steps
a
(c)
Figure 9: Imitation learning. y2: (a) Mean single- objective Fi. (I) obtained by different
policies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single- trial objective Fi,H (л)) obtained by different policies. (c) Mean single-trial objective Fi. (T)
obtained by the MCTS- baased algorithm as function of the number of expansion steps. Shaded
areas correspond the 90% mean confidence interval. Across all plots, lower better.
28

---

Published as a conference paper at ICLR 2026
C.3.6
IMITATION LEARNING, FROZENLAKE
0.08
0.125
0.25
MCTS planner
0.100
0.20
0.00
F1.0
0.073
0.15
0.01
0.030
0.10
0.06
0.00
0.025
0
1000
2000
3000
4000
Expansion
(c)
Figure 10: Imitation learning, FrozenLake: (a) Mean single-trial objective Fi,H (TT) obtained by
different policies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single-trial objective Fi,s (ιT) obtained by different policies. (c) Mean single-trial triglltriall objective (.)(()) obtained by the ACTTSbased algorithm as a function of the number of expansion steps. Shaded areas correspond the 90% mean confidence interval. Across all plots, lower is better.
C.3.7 IMITATION LEARNING, TAXI
0.09
MCTS planner
0.070
0.10
0.065
0.07
0.060
0.06
0.069
0.06
0.05
2000
400K
stops
(a)
(b)
(c)
Figure 11: Imitation learning, Taxi: (a) Mean single-trial objective Fi,H (I) obtained by different
policies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single- trial objective Fi,H(2 (π) obtained by different policies. (c) Mean single-trial objective Fi. (T)
obtained by the MCCTS-based algorithm as function of the number of expansion steps. Shaded areas correspond to the 90% mean confidence interval. Across all plots, lower better.
29

---

Published as a conference paper at ICLR 2026
C.3.8
IMITATION LEARNING, MOUNTAINCAR
0.3
MCTS planner
0120
0.05
0.15
0.2
Fla(#)
0.04
0.10
0.1
0.05
0.02
0.0
0
1000
2000
3000
4000
Expansion
(c)
Figure 12: Imitation learning, MountainCar: (a) Mean single-trial objective Fi, (T) obtained by
different policies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single-trial objective Fi,x(T) (Tt) obtained by different policies. (c) Mean single-trial triglltrial objective Fi.H (T) obtained by the MCTS- algorithm as a function of the number of expansion steps. Shaded areas correspond the 90% mean confidence interval. Across all plots, lower is better.
C.3.9
ADVERSARIAL MDP
1.30
1.5
planner
1.25
1.25
1.1
1.20
1.20
1.3
1.15
1.15
1.10
1.10
1000
2000
3000
4000
== Random
==
Random
m/
Expansion stops
(c)
Figure 13: Adversarial MDP: (a) Mean single-trial objective FT.H(T) obtained by different poli- cies. Error bars correspond to the 90% mean confidence interval. (b) Distribution of the single-trial objective Fi (r) obtained by different policies. (c) Mean single-trial objective Fi. obtained by the MCTS-bast based algorithm as a function the number expansion steps. Shaded areas corre- spond to the 90% mean confidence interval. Across all plots, lower is better.
30


Reviews:
[{"review_id": "HX6QUX2LTh", "reviewer": "Reviewer_m7hG", "summary": "This paper tackles single-trial optimization in infinite-horizon discounted general-utility MDPs (GUMDPs), where the objective $f$ is possibly a non-linear function of the discounted state-action occupancies. The paper establishes some fundamental results for the problem. It formally proves that non-Markovian policies can strictly outperform stationary and Markovian policies for the single-trial regime. Then the paper introduces the occupancy MDP (OMDP), which is a finite-horizon MDP whose states augment environment states with the running discounted occupancy $o$. The authors establish a one-to-one mapping between histories and OMDP states and characterize equivalence. Based on this connection, they show that solving the OMDP reformulation with stationary policies corresponds to solving the original problem with non-Markovian policies. Despite this, it turns out that policy optimization with smooth convex utility functions is NP-hard.", "questions": "As the authors delineated the connection to occupancy MDPS with stationary policies, would it be possible to design an algorithm with a provable performance guarantee, such as regret bounds and convergence to an optimal policy?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper provides some fundamental theoretical results comparing stationary, Markovian, and non-Markovian policies for the single-trial regime. Moreover, the paper characterizes the connection between the original GUMDPs and their truncation to finite-horizon MDPs in terms of regret. The paper also proves that the GUMDPs with non-Markovian policies are equivalent to occupancy MDPs with stationary policies. These theoretical findings are novel and provide interesting insights for the single-trial regime of general utility-based MDP formulations.", "weaknesses": "Although the paper empirically tests the computational performance of the MCTS-based algorithmic framework presented in this paper, it lacks its theoretical analysis. The NP-hardness of computing an optimal policy should not prevent us from deriving a finite convergence guarantee to an optimal policy ($1/\\epsilon$ versus $\\mathrm{log}(1/\\epsilon)$). However, there is neither a regret bound nor a convergence guarantee.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "3SxOgA9jKj", "reviewer": "Reviewer_PZ7T", "summary": "The paper aims to solve infinite-horizon discounted general-utility Markov decision processes (GUMDPs) in the single-trial (trajectory) evaluation setting. In particular this means that they consider a (non-linear) function $f$ of the empirical discounted occupancy of one trajectory $\\mathbb{E}[f(d^{\\pi})]$, compared to previous work that considered the expected discounted occupancy $f(\\mathbb{E}[d^{\\pi}])$. The intuition is that if we consider a non-linear objective and apply standard RL techniques, there is a gap between training and evaluation, since the objective it is being trained on is an upper bound of the true objective.  \n\nThey achieve this by proving three theorems: (i) non-Markovian policies are necessary for optimality in the single-trial objective; and (ii) reduction of the single-trial problem and solution to a finite-horizon occupancy MDP; and finally (iii) they show the NP-hardness of the policy optimization in the specified regime.\n\nThe authors propose to solve the occupancy MDP with MCTS, which guarantees convergence in the infinite iteration regime. Finally the method is tested on illustrative toy and OpenAI Gym environments, showing improvement over baseline random and infinite-trial solver policies. All the proofs and experiments are conducted for discrete state and action spaces.", "questions": "- What is the core difference between GUMDPs considered in this work and Convex MDP? It seems there is no difference if theoretical results follow a convex $f$. \n- The random policy already shows decent performance for some of the environments. Could you include harder environments to show the strength of your method?\n- Explain the size of the uncertainty in table 1. They seem to vary significantly between environments and policy, the $pi_{MCTS}$ Taxi has even 0 uncertainty, indicating that the uncertainty is most likely underestimated.\n- Consider rephrasing lines192-206 on the “Single-trial formulation for GUMDPs” to a list for easier readability. \n- Consider using a “hat” the empirical observables to distinguish them clearly from the expected values.\n- Mention that you work with discrete state action spaces in the introduction already.\n- Introduce examples of use cases of single-trial evaluations.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper clearly delineates the single-trial from the infinite-trial formulation and establishes a solid method to reformulate the GUMDP as an occupancy MDP that can be solved with well established planning methods. The paper shows clear improvement over previous methods, albeit on simple domains. Overall, the authors identify a subtle problem when considering alternate MDPs with non-linear objectives.", "weaknesses": "It is not entirely clear what the main theoretical contribution of the work is, since the single-trial setting is a special case of the multiple-trial setting from Santos et, al. ICML 2025. \n\nEmpirically, the method was only shown for very small state and action spaces where even a random policy achieves reasonable performance.  It should ideally be further tested on more complicated and larger environments, and particularly one a specific use case where single-trial evaluation is required by its nature (e.g. stock market predictions, robotics). \n\nThe use cases of single-trial evaluation would exclude the existence of a (reliable) simulation. This is a serious limitation of the proposed method that relies on a planner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "kkVp7amqS7", "reviewer": "Reviewer_LDEZ", "summary": "The authors propose a novel method for solving infinite-horizon discounted general utility MDPs in the single-trial regime. This includes some analysis showing how online planning techniques can be used to solve general utility MDPs, as well as empirical results which show that the proposed method yields superior performance when compared to prior methods.", "questions": "- Did the authors consider whether there are any assumptions needed to ensure that the occupancy measure is well-defined (i.e, that it exists and is unique)? For instance, some MDP-based methods require that the induced Markov chain / MDP has ergodic properties.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The writing quality and presentation of this paper is outstanding. In particular, the analysis performed is well-motivated and presented in a clear and easy-to-read manner. The empirical results are encouraging.", "weaknesses": "I have no major concerns with this paper, and it is more or less in a publishable state.\n\nHere are some minor concerns/suggestions for the authors:\n\n- The notation related to the occupancy measure is a bit confusing. In particular, the notation of d_pi in equation 1 vs d_^pi in equation 3 onwards makes it unclear how these two terms are related. \n- Lines 173-174: the claim that 'practical applications often require identifying a policy that performs optimally when evaluated based on a single trajectory' is not supported. In particular, the authors need to formally prove/motivate this, or cite a prior work that does so.\n- Theorem 1: The use of cost instead of reward may confuse the reader here. In particular, most readers may incorrectly interpret F_1(pi_s) > F_1(pi_m) as indicating that F_1(pi_s) is better than F_1(pi_m) (since most readers are familiar with the reward-based formulation). I would suggest adding some form of clarification in the theorem to avoid this potential issue (or perhaps removing the > altogether and instead only use words).\n- I strongly encourage that the authors use the extra page of content allowed during/after the reviews to include more plots related to the empirical results (such as the ones in Appendix C).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Kwtz073lJu", "reviewer": "Reviewer_bm8h", "summary": "The paper investigates the setting of discounted infinite-horizon general-utility MDPs under the single-trial regime, and proposes a set of theoretical results on the policy class needed to represent the optimal solution, the complexity of achieving such optimum and a methodology to cast one such problem into an equivalent, finite horizon, standard MDP. Finally, an online planning method based on MCTS is proposed, achieving better performances than existing solutions on GUMDP formulation of existing problems.", "questions": "- I think that, at the end of page 2, the symbolism for non-deterministic stationary policies $\\Pi^D_S$ and deterministic stationary policies $\\Pi_S$ are swapped?\n\n- On line 112, what is $\\mathcal{F}$? It is not defined anywhere in the following.\n\n- \"*However, the compressed representation used by the occupancy MDP is more amenable to practical implementations since the running occupancy can be incrementally updated as the agent interacts with its environment.*\" What do you mean precisely here? That, in practical implementations, you can maintain the histories and incrementally update it with the new \"pieces\"? Why this could not be done with full-length histories as well in pretty much the same way?\n\n- You say that discounting plays a significant role in your proposed formulation, and reference Proposition 2 as one of those. However, while I do agree that indeed your formulation relies on the fact that you are addressing the infinite-horizon discounted setting, I do not see where discounting is playing a role in such proposition. While, conversely, this is very clear in Proposition 1, that allows you to resort to truncated histories at the price of a constant term (depending on the discount factor $\\gamma$) in terms of regret.\n\n- Line 428: GUMDPS $\\rightarrow$ GUMDPs\n\n- Results of $\\pi_{\\text{Solver}}^*$ are a bit surprising: this is using an exact solver in the infinite-trial regime, and as such I would have expected to find a better solution than the method based on MCTS under the single-trial regime (in principle, the solver should be able to always achieve the optimal solution, given enough computational time and resources). Is there any limitation imposed on such solver, like a limited computational time? Could you please discuss on the gap in performance between the optimal solver and your proposed method a bit more?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The investigated problem is interesting: standard MDPs are known for being limited in what class of utilities they can represent, and the GUMDP framework allows us to overcome such limitation. However, this setting is much less investigated, and new solution techniques are welcomed. The paper is very clear and rigorous in how it guides the reader through its contributions, always being clear in drawing relevant connections with previously defined concepts and results. As a non-expert in general-utility MDPs, I found it very easy and clear to read. Also, the derived results are sound, and can serve as a good basis for future research in the direction of the single-trial regime. Theory builds up the fundamental pieces until the practical methodology based on MCTS is provided in a clear way.", "weaknesses": "I do not have any particular weakness to highlight. The only criticism that can be moved to the current version of the paper is the limited size of the experiment (an aspect the authors have been earnest upfront): the current small experiments are not really telling us much on how the proposed framework would scale to larger setting which are now common in RL (even though the results on the Gym environments are going in this direction a bit). However, I do not feel this is an invalidating weakness, as I appreciate that the nature of the work is mainly theoretical, and the proposed empirical results are still convincing enough to draw interest on this methodology anyway.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)