Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?
Authors: Hao Liang
Jiayu Cheng
Sean R. Sinclair
Yali Du
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning
Exogenous Markov Decision Processes
Regret Analysis
Linear Function Approximation
Exploration-free
Primary area: reinforcement learning

Abstract: Exogenous MDPs (Exo-MDPs) capture sequential decision-making where uncertainty comes solely from exogenous inputs that evolve independently of the learner’s actions. This structure is especially common in operations research applications such as inventory control, energy storage, and resource allocation, where exogenous randomness (e.g., demand, arrivals, or prices) drives system behavior. Despite decades of empirical evidence that greedy, exploitation-only methods work remarkably well in these settings, theory has lagged behind: all existing regret guarantees for Exo-MDPs rely on explicit exploration or tabular assumptions.
We show that exploration is unnecessary.
We propose Pure Exploitation Learning ($\texttt{PEL}$) and prove the first general finite-sample regret bounds for exploitation-only algorithms in Exo-MDPs. In the tabular case, PEL achieves $\widetilde{O}(H^2|\Xi|\sqrt{K})$. For large, continuous endogenous state spaces, we introduce $\texttt{LSVI-PE}$, a simple linear-approximation method whose regret is polynomial in the feature dimension, exogenous state space, and horizon, independent of the endogenous state and action spaces.
Our analysis introduces two new tools: counterfactual trajectories and Bellman-closed feature transport, which together allow greedy policies to have accurate value estimates without optimism.
Experiments on synthetic and resource-management tasks show $\texttt{PEL}$ consistently outperforming  baselines. Overall, our results overturn the conventional wisdom that exploration is required, demonstrating that in Exo-MDPs, pure exploitation is enough.

Published as a conference paper at ICLR 2026
Is PURE EXPLOITATION SUFFICIENT IN EXOGENOUS MDPS WITH LINEAR FUNCTION APPROXIMATION?
Hao Liang'; Jiayu Cheng", Sean R. Sinclair)) Yali Du
DDepartment of Informatics, King's College London 2Independent Researcher
DDeparteent of Industrial Engineering and Management Sciences, Northwestern University 'The Alan Turing Institute
haoliang. research@gmail com, jiayucheng31 com, sean.
edu, yali.uukkcl.........m duwkcl. acc.c.ll.............. ac.uk uk
ABSTRACT
Exogenous MDPs (Exo-MDPs) capture sequential decision-making where certainty comes solely from exogenous inputs that evolve independently of the learner's actions. This structure is especially common in operations research appli- cations such as inventory control, energy storage, and resource allocation, where exogenous randomness (c.g.. demand, arrivals, or prices) drives system behavior. Despite decades of empirical evidence that greedy, exploitation-on oonll methods work remarkably well in these settings, theory has lagged behind: all existing regret guarantees for Exo-MDPs rely on explicit exploration or tabular assumptions. We show that exploration is unnecessary. We propose Pure Exploitation Learning (PEL) and prove the first general finite-sample regret bounds for exploitation-only algorithms in Exo-MDPs In the tabular case, PEL achieves VV where is the horizon, E the exogenous state space, and K the number of episodes. For large, continuous endogenous state spaces, introduce LSVI-PE, simple iinear-approximation method whose regret is polynomial in the feature dimen- sion, exogenous state space, and horizon, independent of the endogenous state and action spaces. Our analysis introduces two new tools: counterfactual trajecto- ries and Bellman-closed feature transport, which together allow greedy policies to have accurate value estimates without optimism. Experiments on synthetic and resource- ssource-management tasks show PEL consistently outperforming baselines. Overall, our results overturn the conventional wisdom that exploration is required, demonstrating that in Exo-MDPs, pure exploitation is enough.
INTRODUCTION
Sequential decision-making under uncertainty is central to a wide range of domains, from inventory control and energy storage cloud resource management and supply chains (Madeka al. 2022 Yu al. 2021: Sinclair et al. 2023b Oroojlooyjadid et al.) 2022). In these applications the system dynamics are shaped by controllable endogenous states and exogenous inputs that evolve indepen- dently of the agent's actions. Exogenous Markov Decision Processes (Exo-MDPs) formalize this setting by partitioning states into endogenous and exogenous components, where actions only affect the former (Mao et al.) 2018 Sinclair et al. 20236). This separation models many practical settings where randomness is external (e.g. demands, arrivals, or prices) yet crucial for optimal control.
A striking empirical observation across these domains is that pure exploitation works extremely well. Classical approximate dynamic programming (ADP) and OR techniques repeatedly solve, act, and update from observed trajectories without deliberate exploration, and are deployed at industrial scale. Existing results show these schemes can converge in structured settings. For example, /ascimenno Powell (2009) prove convergence for lagged asset acquisition under concavity, demonstrating that pure exploitation can even outperform e-greedy exploration. More broadly, PPwell] (2022) highlights post-decision states and trajectory-based evaluation as foundational principles enabling effective
"Corresponding author.

---

Published as a conference paper at ICLR 2026
exploitation-drin learning in practice. However, the theoretical guarantees in this line rely heavily on structure such as concavity or piecewise linearity.
In contrast, the reinforcement learning (RL) literature provides strong statistical guarantees for Exo-MDPs but almost always through explicit exploration. (Sinclair et al. (2023b) develop hindsight- and replay-based methods that reuse exogenous traces, and Wan et al. (002)) establish connection to linear-mixture models with regret bounds depending only on the exogenous cardinality. While these results underscore the power of exogenous structure, they either require exploration, assume tabular endogenous spaces, or rely on optimistic planning. This creates fundamental mismatch with practice in operations research, where exploitation-hest -haavy methods dominate. Hence a central question remains:
and
Can pure exploitation strategies achieve near-optimal regret in Exo-MDPs under linear function approximation at scale?
OUR CONTRIBUTIONS.
Pure exploitation learning paradigm. We introduce PEL (Pure Exploitation Learning), a unified exploitation-oni) framework for Exo-MDPs in which the learner repeatedly fits value approximations from observed trajectories and then acts greedily with respect to them. Prior ADP results are largely asymptotic or depend on problem-speciffe concavity, while existing RL guarantees for Exo-MDPs typically assume tabular structure, impose optimism, or reduce to linear mixtures, none of which address simple greedy methods under function approximation. A key structural observation that in Exo-MDPs the exogenous process evolves independently of the agent's actions, so every trajectory provides unbiased information about all policies. This enables powerful data reuse. A single exogenous trace can be replayed to evaluate any policy's performance, eliminating the need for deliberate exploration. We resolve this gap by leveraging this philosophy and giving the first general finite-sample regret guarantees for PEL in Exo-MDPs with linear function approximation (LFA).
Exo-bandits and tabular Exo-MDP. To illustrate the core philosophy of PEL, we first analyze multi- armed bandits with exogenous information and tabular Exo-MDPs. In both settings we establish regret guarantees for pure exploitation, complementing and simplifying prior exploration-be babeee approaches. These results form the basis for our extension Exo-MDPs with LFA. Classical optimism-based analysis fails for PEL, and we propose a new regret decomposition and counterfactual analysis to derive a sublinear regret independent of endogenous space and action space size.
Extension to LFA. We then propose and analyze LSVI-E PE (Least-Squares Value Iteration with Pure Exploitation), a backward value-iteration procedure that (i) builds empirical models of the exogenous process, (ii) constructs regression targets using post-decision states that disentangle action choice from exogenous randomness, and (iii) fits linear value approximations using data gathered entirely from greedy trajectories. Two technical ideas drive our analysis: (a) counterfactual trajectory construction that enables reasoning about the value estimates produced under alternative endogenous traces, and (b) an anchor-closed Bellman-tram transport condition that controls how approximate Bellman updates propagate through the fitted linear representation. The resulting regret bounds are polynomial in the feature dimension, exogenous state cardinality, and horizon, and critically demonstrate that explicit exploration is unnecessary because exogenous data reuse suffices.
Necessity of Exo-MDP structure for PEL. The Exo-MDP assumptions are not only sufficient and realistic, but also necessary for PEL to work. If either the endogenous transition or the reward function is unknown, the problem no longer fits the Exo-MDP class, and exogenous traces cannot be reused for counterfactual evaluation. In such settings, any PEL algorithm necessarily incurs linear regret, showing that pure exploitation succeeds only under Exo-MDP structure.
Paper organization. Section reviews related work and Section 3 formalizes the Exo-MDP model. Section 4 Janalyzes pure exploitation in the tabular setting, and Section S introduuss LSVI-PE with its regret analysis under linear function approximation. Section reports empirical results. Section 7 concludes the paper. Proofs are deferred the appendix for space considerations.
RELATED WORK
We briefly review the most salient related works here and refer to Appendix for more details.
2

---

Published as a conference paper at ICLR 2026
Exo-MDPs. Exogenous MDPs, sub-class of structured MDPs, were introduced by Powell (022)
and further studied in an evolving line of work (Dietterich et al. 2018 Efroni et al. 2022 Sinclair
et al. 2023b Powell| 2022). For instance, Dietterich et al. 20]8); Efroni al. (2022) considered
factorizations that filter out the exogenous process, simplifying algorithms but yielding suboptimal
policies since ignoring exogenous states may discard useful information. [Sinclair et al. (2023b)
analyzed hindsight optimization, showing that its regret can be bounded by the hindsight bias, problem-dependent quantity. Most closely related to our work, Wan et al. (2024) establish statistical connections between Exo-MDPs and linear mixture models and design exploration-base
algorithms with regret guarantees in fully discrete Exo-MDPs, assuming finite endogenous and exogenous state spaces and primarily i.i.d. exogenous inputs, with Markovian extension. Overall, existing results largely focus on discrete endogenous dynamics and i.i.d. (or simplified) exogenous processes and typically rely on explicit exploration or optimism. In contrast, we study Exo-MDPs with continuous endogenous states and Markovian exogenous processes, and we provide the first noar-optimal finite- sample regret guarantees for pure exploitation strategies in this more general setting.
Exploitation-base ADP. A parallel line of work in ADP shows that greedy or exploitation-oriente strategies can succeed under strong structural assumptions. Nascimento & Powell (2009) propose pure-exploitation ADP method for the lagged asset acquisition model,, leveraging concavity of the value function to guarantee convergence without explicit exploration. NNseimento & Powell (2013) extend this to vector-valued controls in storage problems under similar conditions. More broadly, Jiang & Powell (2015) and Powelll (2022) highlight methods such as Monotone-ADD and post- decision state exploitation schemes that reduce the need for exploration by exploiting monotonicity or other structural regularities. However, these methods either assume discrete state and action spaces, rely on asymptotic convergence, or require structural conditions like convexity, monotonicity, or sereewise-linearty In contrast, we provide mnite-sample regret guarantees for pure exploitation in general Exo-MDPs without any explicit structural assumptions.
MDPs with LFA. Recent work on RL with IFAA has studied various linear structures, including MDPs with low Bellman rank (Tiang et al.) 2017 [Dann et al. [2018), 8), linear MDPs (Yang & Wang 2019 Joi et al. 2020), low inherent Bellman error (Zanette et al. [2020), and linear mixture MDPs (Jia et al. 2020 Ayoub et al. 2020; Zhou et al. (021). Our results contribute to this literature by establishing near-optimal regret guarantees for Exo-MDPs with LFA under pure exploitation.
3 PRELIMINARIES AND PROBLEM SETTING
Notation. We write [N] := 21, N} for any positive integers N. For matrix A, we use |||]] to denote its operator norm. We use I[-}} to denote the indicator function. For any I E IR, we define [x]+ == max(z 0}. We use Ó(.) to denote O()) omitting logarithmic factors. A table of notation is provided in Appendix A
MDPs with exogenous states. We consider Exogenous Markovian Decision Processes (Exo- MDPs) with Markovian exogenous dynamics, a subclass MDPs that explicitly separates the state into endogenous and exogenows components (Dietterich et al. 2018 Efroni et al. 2022 Sinclair ct al. 2023b, Powell 2022). Here, a state 8 = {x) factorizes into an endogenous (system) state L and exogenous input & E E. Intuitively, the exogenous state εn captures all randomness (e.g.. demand, arrivals, or prices), while the endogenous state Iy captures the system's 's internal configuration. Because actions cannot influence εn, the agent cannot manipulate future randomness, which is central to our pure-exploitation results. Formally, an Exo-MDP is defined by the tuple M(P, f,r) = (X' E, A,
P., r, H). At each stage h, the agent selects an action aş (sx) e A given the current state Sk = (æh, En) under their policy = (тл))εди) E 11 where II = {(TA)EE TA : :'' x E - A). The exogenous state evolves as a Markov process En+1 ~ (- independent assume the exogenous state space is discrete, which is well-aligned in operations research where the exogenous randomness corresponds to discrete demand levels
of 3r and [ _ Throughout
in inventory control (Besbes & Muharremoglu, 2013 Cheung et al. 2023) or job types in cloud
computing systems (Balsciro et al. 2020; Sinclair et al. 20236).
We discuss the general m-Markoviin setting in Appendix C
3

---

Published as a conference paper at ICLR 2026
Conditional on (2); an: En). the endogenous process evolves and the reward function is specified by deterministic functions:
Th+1 f( ah Sh+1), Th = r( on, (h) E 1].
The endogenous dynamics are still stochastie, only deterministic function of the exogenous state distribution through f- The full transition kernel from a state can be written as P(s 18h, ah) = ([ Oh Sa+1) + J.P (En+1 (n)-
Remark 1. These modeling assumptions are well-motivated in many operation research applications, especially resource management. For example, in inventory control, the endogenous state 24 is the on-hand inventory level, while the exogenous state &a. is the demand realization at time (Madeka et al. (022). Actions da correspond to order quantities. The system transition function are deterministic given demand, e-g. the newsvendor dynamics #h+11 = [(r,, dh Ea+1) max(22) an (,,,,,,,,0 0). The reward depends on sales revenue and holding or stockout costs, r(z,, as. Ex). The only randomness arises from the exogenous demand process. We give more examples of Exo-MDPs in Appendix C.1.3
Value functions and Bellman equations. For a policy æ, the action-value functions and state-value functions step h are defined as:
@% (s, a) == E EΣ*= r(0,, &x) (Sh, an) = (s, (s, क
V. (s) = 2% (8, (s())-
We also define hindsight value functions for fixed exogenous trace ε>Λ (5h+1.-.... EH):
Q7 (s, a, E.A) : Σim r(s,, {+) (sh. an.) = a), VI (s, Q7 (s)) E These are deterministic once S>Λ are fixed, so no Monte Carlo sampling is required under the known functions f and g. [Sinclair al. (2023b) show that unconditional values are expectations over A. and policy n,
hindsight values, i.c. for every / E [. (5, a)
(x a) E.... 1Q% (s, a, E>n)], (s) = Ee... n. [VTT (s, (sn)),), where the expectation is taken over the conditional distribution &>Λ Ph (- [x).
Online learning. We consider an agent interacting with the EXo-MDP over K episodes. At the beginning of episode k. the agent starts from initial state sf and commits to a policy #* II. At each step h, the agent observes s = (= < takes action af = (s)) receives reward r(ah, af, <h), observes 5h+11 and transitions to
x #1+1 = f(z,, a 1) ). Each episode has steps. The performance of algorithm is measured by its cumulative simple regret over K episodes:
SR(alg, k) = VT (81) V CR CR (Rlg, K) = =K (VT((s)) - Vf (s1)
where n² arg max (s) the optimal policy and * is the policy employed in episode
The initial exogenous state ef in each episode can be arbitrarily chosen. For each (k, h) E [K] x [H].
we denote by H A (st, at. 8). o²,, ..,
,., $)1 ......... . , a²) the (random) history up to step of
episode k. We define F& - H//1 as the history up to episode k - 1. We use & == (5' [{{())] to denote the exogenous trace up to the end of episode k.
PURE EXPLOITATION LEARNING IN TABULAR EXO-MDPS
We now illustrate the philosophy of Pure Exploitation Learning (PEL). In Exo-MDPs, the only unknown component is the exogenous process, which evolves according to a Markov chain inde- pendent of the agent's actions. As a result, trajectories collected under any policy provide unbiased information about this process, so explicit exploration is not required. PEL builds on this observation: instead of adding optimism or randomization, PEL algorithms repeatedly fit empirical models or value functions from observed exogenous traces and then acts greedily with respect to these estimates. To summarize define PEL algorithms
Definition (Informal). PEL denotes the family of algorithms that, each round or episode, construct an empirical value function from previously observed exogenous traces and act by greedily maximizing this function, with no optimism or forced exploration.
We next make PEL concrete in two simple settings: (i) an Exo-bandit warm-up (H = 1) and (ii) the tabular Exo-MDP. After presenting regret guarantees and computational remarks, conclude with an impossibility example showing that PEL can fail in general MDPs without exogenous structure. We then move onto the linear function approximation case.
4

---

Published as a conference paper at ICLR 2026
4.1 WARM-UP: EXO-BANDITS
We start with multi-armed bandits with exogenous information (coinciding with bandits with full feedback), Exo-MDP with no states and H 1. At each round k the agent selects arm ag. an exogenous input &a is realized, and because the reward map r(a, {) is known the agent can evaluate the reward r(a, Ex) of all arms. Following Wan al. (2024) we call this setting an Exo- BandB..
Here, the PEL strategy reduces to the classic Sollow-The-Lcade (FTL) strategy: at round simply choose the arm with the largest empirical mean reward ag E arg max.e.4 (a.
K-T T-T - (x). This procedure entirely exploration free, unlike in classical bandits where exploration schemes such as UCB or Thompson Sampling are essential for learning (Auer et al. 2002. Russo et al. 2018). This contrast illustrates how exogenous information fundamentally changes the role of exploration since the algorithm can use the counterfuctual information inferred from the observed exogenous information.
Proposition 1. Assume rewards are p--sub-Gaussian Then the expected per-round simple re- (FTL,K) $
gret of FTL satisfies SR
V 2og A and consequently the cumulative regret obeys
CR K) & 20 / (K 1) log A.
The proof is provided in Appendix F.1 These regret bounds recover standard full-inf fulliinformation or experts-type guarantees and are are minimax-optimal (Cesa-Bianchi & Lugosi, 2006) Shalev-Shwaar et al. 2012). 'he point here is not novelty but illustration: when full feedback is available via the exogenous feedback, simple PEL suffices, and additional exploration is no longer necessary.
4.2 TABULAR EXO-MDPS
We now extend PEL to finite-horizon Exo-MDPs with finite state and action spaces. Since exogenous traces can be reused across policies, Leader (FTL) at the policy level. This yields near-optimal regret bounds, consistent with [Sinclair al. (2023b), but evaluating all policies amounts empirical risk minimization (ERM) over II. This computationally infeasible in general since [I] < [A|MXI See Appendix D for discussion of this algorithm and the result.
form unbiased value estimates and apply Follow-the-
To address this, consider more practical EL instance, Pendiet-Then-pptmiiie (PTO), PTO first estimates the exogenous transition kernels IP (- &x) (e.g., via empirical counts MLE), and then plugs them into standard dynamic programming to compute greedy policies:
@ (Sh, an) = r(z,, ab. {n) + Eg, 1 len [ (f an Ea+1), (b+1)))+++)))) 1b+1); P
* (*n) E arg max (sn, an). (sn) @% (sA. 7/ (sn)). aa
The following theorem bounds the cumulative regret of PTO under Markovian exogenous noise by reducing model error to exogenous- errors, yielding rates independent of | and [A].
Theorem 1 (Regret of PTO under Markovian exogenous process). With high probability, the cumula- tive regret of PTO after episodes satisfies
CR (P S Ö(H*EKK).
The proof is provided in Appendix F33 A key challenge is that classical optimism pptimism-based analysis Even though the only unknown is the exogenous kernel Pz.
fails for pure exploitation in Exo-MDPs.
the optimistic inequality ViT" - < does not hold, so the usual simulation- telescoping breaks. We instead introduce new regret decomposition with two double value gaps, separating model errors for "²* and k While the on-policy term can be bounded as in classical analyses, the term for n* cannot-its trajectory is never observed. This motivates our use counterfactual trajectories that follow x but share the same exogenous realization to. Conditioning on the exogenous filtration allows a simulation-lemme gaps purely in terms of exogenous kernel errors, replacing acteonction counts by indee-iideeendeett exogenous counts C. (fn), resolving the policy policy-misaligmaee misalignment issue and yielding sublinear regret independent of the endogenous state and action spaces.
bound without requiring visitations under π². This rewrites the value
5

---

we assume that the dynamics Published as a conference paper at ICLR 2026
Unlike the exhaustive ERM/FTL approach, which is statistically sound but computationally infeasible, PTO provides a practical and efficient PEL implementation. runs in time polynomial |x] [A, and H, while preserving regret guarantees that depend only mildly on the exogenous cardinality |=]
4.3 IMPOSSIBILITY: PURE EXPLOITATION CAN FAIL IN GENERAL MDPs
To understand why the EXo-MDP structure essential for PEL, we examine what happens when its key assumptions are violated. Specifically, we consider PEL when either the endogenous transition function f or the reward function unknown.
Proposition 2. For any pure-exploitation algorithm, there exists a tabular MDP with unknown transition function f or unknown reward function on which the algorithm suffers linear regret.
The proof is provided in Section C.1.2 This result shows that once f or is unknown, the class of otherwise tabular Exo-MDPs already contains instances where every PEL algorithm incurs linear regret. In such settings, pure exploitation is not minimax-sufficient Hence, the Exo-MDP structure not just sufficient, it is the critical condition that makes it possible for PEL achieve sublinear regret, in sharp contrast to the general tabular MDP setting with unknown f or
Discussion. While this section considered simple tabular Exo-MDPs, we showed that pure ex- ploitation suffices: exploration is unnecessary because exogenous randomness is decoupled from the agent's actions, and Exo-MDP structure necessary for PEL to work. With the right implementation (e.g., PTO), PEL is both statistically and computationally efficient. However, these results hinge on tabular representations, limiting scalability. In the next section, we extend these ideas continuous state and action spaces under linear function approximation.
5 LINEAR FUNCTION APPROXIMATION
The previous section established that PEL suffices in tabular Exo-MDPs. However, in order to make this useful for more realistic and nigh-dimensional problems, need move beyond finite endogenous state spaces. This section develops LSVI-PE, a simple and efficient pure-exploitation algorithm under linear function approximation. Our algorithm leverages two structural ideas: (i) post-decision states, which remove the confounding between actions and exogenous noise; and (ii) counterfactual trajectories, the same principle that underpinned our tabular analysis.
Continuous Exo-MDPs. We now consider Exo-MDPs with continuous endogenous states Iy E X' continuous actions a₁ A, and finite exogenous states Én E E over horizon H. This extension is essential for modeling realistic operations research and control applications, where system states (e.g.. inventory levels, resource capacities, storage levels) and actions are naturally continuous. Following the ADP literature (Nascimento & Powell 2009 2013 Powell 2022),
decompose into two steps:
2i ( an) E 2 X' dpost-decision state),
Fh+1 ( En+1) E X (next state),
with E--1 (- En). For any policy æ, we define the post-decision value function
(I" .) Eele) V V===(o(=".5')ee)
which represents the expected downstream value after committing to action ag but before the next exogenous state is revealed. The pre-decision value function then decomposes as
Vi (z, = ((,,)))))())))))))...)))))))))>) V,,
(f" (x, E)).
The optimal policy also obeys
(x, max { (r(x,a,)) V (F,,) V Bew (it)l((a,
now formalize the definition of Exo-MDP with linear function approximation (LFA): Definition 2. An Exo-MDP is said to satisfy post-decision LFA with respect to a known feature mapping Rd if, for every policy æ, step h, and state (x", E) X x
V (x" .)) = )(xa) (E),
where sup.a ||1( I. 1, and the weight vectors satisfy suP 11 (E)ll2 & Vd.

---

Published as a conference paper at ICLR 2026
Thus, post-decision LFA can be viewed as Exo-MDP analogue of the linear MDP assumption, tailored to exploit the separation between endogenous dynamics and exogenous randomness. We denote the optimal weights by (E) == w (E) so that V/"" *. (a" = o(x)) (E)
Since the endogenous state space X' may be continuous, decision states. To make the LFA identifiable and the least-squares updates well defined, we introduce finite collection of representative post-decision states whose feature vectors span the feature space.
cannot directly regress all post-
Assumption 1 (Anchor set), For each step h. there exist N 2 d fixed post-decision states {xr (n)) n=1 such that the feature matrix 4% == (1(x)(1)), ..... ((sg(N)) E Rdx has full row rank, i.e., rank(On)) d.
Together, the LFA assumption and anchor condition provide tractable representation that supports efficient algorithms while keeping regret bounds polynomial in the feature dimension d rather than the size of the underlying endogenous state or action spaces. We also emphasize that Assumption I standard in the ADP literature (Nascimento Powell 2009 2013).
5.1 ALGORITHM
In this section, we present our algorithm Least-Squares Value Iteration with Pure Exploitation (LSVI-PE) for Exo-MDPs with LFA. See Algorithm for pseudo-code.
High-level intuition. Our algorithm LSVI-PE alternates between two phases:
1. Policy evaluation (backward pass): At each stage h, we construct Bellman regression targets using the empirical exogenous model P, (Line 10 Then run least-squares regression on the anchor states to produce weight vectors w (E) for each exogenous state & and stage h. defining a linear approximation for the value function as V/ (x",E) o(z") T (x) R V7 (~", .).
2. Policy execution (forward pass): In episode k, the agent acts greedily with respect to these value estimates (Line 19). The observed exogenous trajectory is used to refine the empirical estimate P.
Before moving onto the regret analysis we briefly comment on several aspects of the algorithm.
Role of anchor states. Anchor states {æ% (n) chosen to guarantee that the feature matrix 2 has full row rank (Assumption []. This ensures that the regression weights (E) are unique. Intuitively, anchors serve as representative endogenous states: they provide just enough coverage of the feature space to propagate accurate value estimates without requiring samples from the entire (possibly continuous) state space.
Anchor states not unknown structural assumptions but design choices made by the learner. Assumption simply requires fixing a finite set of post-decision states whose feature vectors span the space. These serve the representative grid underlying the feature map (e.g.. s.. hat bases, spline knots, or tile centers (Sutton et al. [998)). This mirrors standard practice in RL with LFA, where choosing implicitly specifies the underlying basis points. Such anchor constructions are routine ADP and operations-research applications, including inventory control and storage systems, where practitioners exploit domain structure (e.g.. piecewise linearity or convexity) to select natural breakpoints as Powell 2022)
anchors (Nascimento & Powell 2009 2013
Exploration-free design. Conventional RL algorithms with LFA rely on explicit exploration mechanisms. For instance, LSVI-UCE (Jin et al., (020) enforces optimism in the value estimates, while RLSVI (Oshand al. (016)) injects random perturbations into regression targets. In contrast, LSVI-PE is pure exploitation algorithm. All updates come directly from empirical exogenous trajectories observed along greedy play. The independence of the exogenous process makes this design both natural and theoretically justified, and we later show it achieves near-optimal regret.
Computational efficiency. In LSVI-PE, regression targets are computed only at the anchor states, and updates decompose stage by stage. This structure makes the algorithm scalable when the endogenous state and action spaces are continuous. Compared to FTL-style policy search, which requires evaluating every policy, L.SVI-PE is implementable in polynomial time.
7

---

Published as a conference paper at ICLR 2026
Algorithm LSVI-PP
Require: Anchor states {2% (n)) feature map Φ X - R
H.N 1: Precompute: For each h, set 4, - (1)) 600 (N))] RdxN and En. 4n Q /
2: Initialize: For each and 5,5' E E, set counts 55, + and (5 + 1/ set
(5) + 0 for all / E [1 1
3: for = to K do
// Episode loop
4:
// Policy computation using data up is 1 // 5: for = H down to do
6:
for each { = do
7:
(5) < E Rd for n to .N do
8:
9:
Define <5n(E") + o( (') for each E' E
( (e (F(E))) (E))
10:
(m: E - (61E)max
11:
(5) + (5) p( (m)) un
12:
end for w (E) En (E)
13:
// Least squares on anchors
14:
end for
15:
end for
16:
// Act in episode & with {wh) and collect data &x //
17:
Receive wt: observe et for to H do
18:
of E argg maNaEd { (r(at, a, (h) + (x a)) wh(sh)
20:
Fn k.a
+ fz a observe chi set set aht + g(zh :5h+2)
Update counts: (En, En+1) + -h- "En EN+1) + I[(En, Ex+1) (h+1)) end for
22:
23: Update empirical model: For all E. ((((()) +- Nh(C.())
NceENN(EN
24:
end for
Output: (E) for each h and E
5.2 REGRET ANALYSIS
Before presenting our main result we introduce some additional notation. Let di (n) == (n)) and define the anchor feature matrix 42 := [ox (1). (NV] E RdxN, We also define Ao := min Amin (En) O, where E, 2 2/ is the anchor covariance. Fix h, n, and g E. We
define the post-decision transition operator T (E'): x X as
(<x)))²²))== = Sr (g(a",e) T (o(=="')),)))
This represents one step of evolution:
I a'
(x as the compressed arrow xa S (x0)' (x))))))
We introduce two additional assumptions to establish our regret guarantees. We begin with a weaker requirement, that the anchor states are closed under the Bellman operator. Intuitively, this condition ensures that when an anchor state undergoes one step of post-decision transition, its image remains in the span of the anchor feature representation.
Assumption 2 (Anchor-closed Bellman transport (weaker)). For any n, h E [M]. and 5' E E, there exists a matrix (5') E Raxd with supa.g* & (E')ll E such that for every anchor (n)),,
(TT (E))((())) = MI (x)))))
Note that this establishes the one-step image of any anchor under the post-decision transition lies in the same feature span and linearly transported by (E')
Assumption 3. For any xº, Φ(x²) is in the nonnegative cone of +.
8

---

Published as a conference paper at ICLR 2026
Assumption the pointwise policy-improvenn the greedy update makes all anchor residuals nonnegative, and thus guarantees improvement at arbitrary post-decision states.
Theorem 2. Under Assumption 2
the regret of LSVI PE after K episodes satisfies
CR (LSVI--FE, & ((
PEL achieves standard sublinear regret under Assumption with dependence on the feature di- mension d. the number of anchors and their conditioning via /N/Ao. and the exogenous state size | while remaining independent of the size of the endogenous state and action spaces. In well-conditioned designs (e.g., À = (1) and N = d), the bound simplifies to O(E))
The intuition behind the proof parallels the tabular setting. We adopt new decomposition that requires controlling two value gaps. The key step is to bound the ppolicy gap using a simulation lemma applied not to the realized trajectory of n² but a counterfactual trajectory generated under I¹ while sharing the same realized exogenous sequence. Assumption Znnures that all Bellman regression targets remain in the anchor span, so each stage-h update reduces to well-conditioned least-squares problem governed by Xo. Along the counterfactual process, the proof decomposes the error into (i) Bellman regression errors at the anchors and (ii) exogenous-mode errors, and then couples both components to the observed exogenous trajectory through martingale concentration on the estimated exogenous rows. This contrasts sharply with standard Linear-MDP optimism analyses, which rely on confidence sets and self-normalized concentration in parameter space; here the central analytic objects are the counterfactual trajectories and the exogenous martingales that enable stage-wise wige-wise telescoping of Bellman errors and yield the ((v K) regret bound without optimism. Full proof's are in Appendix G
Our next assumption strengthens Assumption 2 to hold for all x" instead of just the anchors:
Assumption 4 (Global Bellman-closed transport (stronger)). For any ग, h E [H] and g E, there exists Mg (g') with suP=,5', .N (5) < such that for all xa, (E))))))))) MI (5') 6(*))
Under this we can establish the following regret guarantee: Theorem 3. Under Assumption 4 the regret of LSVI-PE after K episodes satisfies
CR (LSVI-PE, S Ó( E
While both theorems share the same dependence on K, this refinement tightens the guarantees when H d. Although Assumption is stricter than what LSVI-PE requires, we show yields sharper propagation bounds when exact closure is plausible (or enforced by feature design).
We provide detailed discussion of the anchor-set assumptions in Appendix C.2 including the role and selection of anchor states, connections to coreset and Frank-Wolfs methods, the invertibility and conditioning of k,, the reasonableness Assumptions 2 and several weakenings and relaxations.
Below briefly highlight the intuition behind Assumptions
Discussion on Assumptions 2 to 4 Many Exo-MDPs such as storage problems or linearizable post-decision dynamics naturally induce linear transport within common LFA classes (linear splines, tile coding, localized RBFs, etc). Moreover, the constraint (E')ll < 1 ensures that one-step feature transport is non non-expansive, standard stability condition ADP/LFA analyses. Additional discussion of Assumptions to iis provided in Appendix E
When Assumptions to too4 fails and the true value functions do not lie exactly in the linear span, or the function class is misspecified, Theorem 4 shows that the regret bounds match the earlier ones with additive OKK where EB measures the measures the inherent Bellman errof] (approximation gap between the true Bellman updates and the best function in the linear class). This bias term is unavoidable in general, since even an oracle leamer suffers an O(KEBE) cumulative bias (Zanette et al. 2020).
LSVI-PE with misspecificatioon (approximation) error.
Theorem 4. Assume Assumption I hholds. Fix 5 E (0, 1). Then with probability at least 8,
CR (LSVI-PE, K) < Ô ((#+
H
E H +
K EBE
Vdo
Formal definition provided in Appendix E.1

---

Published as a conference paper at ICLR 2026
NUMERICAL EXPERIMENTS
6.1 TABULAR EXO-MDP
Setup. We evaluate on synthetic tabular Exo-MDPs with endogenous state space X' [5]. exogenous state space 5, and K 250 episodes. Rewards are drawn i.i.d. r(2, a, E) Un, 1). Endogenous dynamics are deterministic, 2h++1 ( ag: fn-1) (2), + at + Eh+1) mod X, while the exogenous process a Markov chain with transition matrix Pg sampled row-wise from Dirichlet prior.
FT0
FTO-:t
PIDiFe33
[5], and action set A [3] and horizon
Camulstivv
300
Comparisons. We compare PTO with its optimistic counter- part PTO-Opt (using optimistic model (Pt) and PTO-Lite (lightweight estimate pp using sub-sampling).
Episades
76
Figure Comparison of PTO, PTO-Opt and PTO-Lite.
F Iillustrates the benefit of PEL. Despite no explicit exploration, PTO outperforms PTO-Lite and the exploration-heavy baseline PTO-Opt Opt in cumulative regret.
6.2 STORAGE CONTROL
Setup. We consider a storage control setting where 2h X [0, C] denotes the current storage level. After taking action as A mmx @max] the system transitions to the post-decision
17 _ The exogenous component is the discrete price. The storage level is modeled as T4+1 = g(0 Eh+1) = ax E (0, 1]. with default a = 1. The reward function is r(I,,, 4n {n. Ehan ap 3h capturing the market transaction, transaction cost, and holding penalty respectively.
state - = f (x,,, a) = clip Ih + +n at
C for n E [N]. one-dimensional Features and anchors. We discretize X' using anchors Pn N-I
hat basis is employed: for any x", the feature vector ((xx) E RN has at most two nonzero entries. Let A PJ+1 Pj- If x" E [pt:) then dz(2") coordinates zero. At anchor points, the basis reduces to canonical vectors, (pp)) Ens so that Φ IN and Σn- T // IN.
=x." 00+1
=i with all other
Comparisons. In Figure we compare LSVI-PE with optimism-based exploration LSVI-Opt. Across all instances, LSVI-PP consistently outperforms LSVI-Opt, emphasizing that in Exo- MDPs exploitation strategies dominate optimism-based ones.
We provide scaled-up experimental setup and comprehensive comparisons in Appendix H
LtViit
LW/iit
LSWIFt
LSvi-Opt
LSVi-Opt
LSVi-Cpt
OUTTAN Rogpe
CUmLArive
50
50
Tpacdes
Opaedes
Tpecdes
H
(b)
(c) 10
Figure 2: Comparison of LSVI -PV and LSVI -Opt across three different time horizon lengths.
CONCLUSION
We show that exploitation is sufficient in Exo-MDP. By introducing PEL, we give the first finite- sample regret bounds for PEL under tabular and LFA, and demonstrate PEL outperforms optimism- based baselines on synthetic and resource-management benchmarks. Future work include relax structural assumptions (richer function classes, continuous or partially observed exogenous processes) while preserving exploitation's sample efficiency.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We would like to thank all the anonymous reviewers for their careful proofreading and constructive feedback, which have greatly improved the quality of this work. This work was supported by the Engineering and Physical Sciences Research Council [grant number EP//003187/1 and UKRI849).
ETHICS STATEMENT
This research foundational and develops theoretical results on reinforcement learning in Exo- MDPs with linear function approximation. As such, it does not raise any direct ethical concerns. However, applications of our algorithms to specific domains (c.g.. inventory control, pricing, or resource allocation) may influence real-world decision-making that affects people and organizations.
We therefore encourage practitioners to carefully consider ethical implications such as faimess, accessibility, and potential unintended consequences when deploying these methods in practice.
REPRODUCIBILITY STATEMENT
All proofs of theorems and lemmas are included in the appendix, and we clearly specify all assump- tions used in analysis. Algorithmic details (see Algorithms T and 2 provided ensure transparency. Our empirical results are based on synthetic Exo-MDP benchmarks and resource- management tasks, both of which we describe in Section and Appendix
REFERENCES
Shipra Agrawal and Randy Jia. Learning in structured mdps with convex cost functions: Improved regret bounds for inventory management. Operations Rexearch, 1063)1644-1164, 2022.
Matias Alvo, Daniel Russo, and Yash Kanoria. Neural inventory control in networks via hindsight differentiable policy optimization. arXiv preprint arXiv:2306. /246, 2023.
Peter Auer, Nicolo Cesa Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with 463-474. PMLR, 2020.
regression. In International Conference on Machine Learning, pp.
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv preprint arXiv:1703.064F3 2017.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference on Machine Learning, pp. 613-628. PMLR, 2020.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration algorithms for contextual bandits. Management Science, 67(3):1329-133 1349, 2021.
Mohsen Bayati, Nima Hamidi, Ramesh Johari, and Khashayar Khosravi. Unreasonable effectiveness of greedy algorithms in multi-armed bandit with many arms. Advances in Neural Information Processing Systems, 33:1713-111 1723, 2020.
Omar Besbes and Alp Muharremoglu. On implications of demand censoring in the newsvendor problem. Management Science, 59(6):1407-1424 2013.
Nicolo Desa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Ethan Che, Jing Dong, and Hongseok Namkoong. Differentiable discrete event simulation for queuing network control. arXiv preprint arXiv:2409.03740 2024.

---

Published as a conference paper at ICLR 2026
Haozhe Chen, Ang Li, Ethan Che, Tianyi Peng, Jing Dong, and Hongseok Namkoong. Qgym: Scalable simulation and benchmarking of queuing network controllers. arXiv preprint arXiv:2410.06170, 2024.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Nonstationary reinforcement learning: The blessing of (more) optimism. Management Science, 69(10):522--573, 2023.
Luca Civitavecchia and Matteo Papini. Exploration reinforcement learning with linear function approximation. In Reinforcement Learning Conference.
Kenneth L Clarkson. Coresets, sparse greedy approximation, and the frank-wole algorithm. ACM Transactions on Algorithms (TALG), 6(4):1-30, 2010.
Jim G Dai and Mark Gluzman. Queueing network controls via deep reinforcement learning. Stochastic Systems, 2021.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac rl with rich observations. Advances in neural information processing systems, 31, 2018.
Thomas Dietterich, George Trimponias, and Zhitang Chen. Discovering and removing exogenous state variables and rewards for reinforcement learning. In International Conference on Machine Learning, pp. 1262-1270. PMLR, 2018.
Eric Eaton, Marcel Hussing, Michael Kearns, Aaron Roth, Sikata Bela Sengupta, and Jessica Sorrell. Replicable reinforcement learning with linear function approximation. arXiv preprint arXiv:2509.00666 2025.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for mosel-based reinforcement learning with greedy policies. Advances in Neural Information Processing Systems, 32, 2019.
Yonathan Efroni, Dylan Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford. Sample-efficient reinforcement learning in the presence of exogenous information. In Conference on Learning Theory, pp. 5062-5127. PMLR, 2022.
Xiaoyu Fan, Boxiao Chen, Tava Lennon Olsen, Hanzhang Qin, and Zhengyuan Zhou. Don't follow blindly: Lower sample complexity of learning optimal inventory control policies with fixed ordering costs. Available at SSRN 4828001, 2024.
Joyce Fang, Martin Ellis, Bin Li, Siyao Liu, Yasaman Hosseinkashi, Michael Revow, Albert Sadovnikov, Ziyuan Liu, Peng Cheng, Sachin Ashok, David Zhao, Ross Cutler, Yan Lu, and Johannes Gehrke. Reinforcement learning for bandwidth estimation and congestion control in real-time communications. arXiv preprint
2019.
Jiekun Feng, Mark Gluzman, and Jim G Dai. Scalable deep reinforcement learning for ride-hailing. In 2021 American Control Conference (ACC). pp. 3743-3748. IEEE, 2021.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19:399-468, 2003.
Chamsi Hssaine, Yichun Hu, and Ciara Pike-Burke. Learning fair and effective points-based rewards programs, arXiv preprint arXiv:2506.03911, 2025.
Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforcement learning. Mathematics of Operations Research, 2024.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pp. 427-435. PMLR, 2013.
Matthieu Jedor, Jonathan Louëdec, and Vianney Perchet. Be greedy in multi-armed bandits. arXiv preprint 10I.v:2201.0/11
2021.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2026
Daniel R Jiang and Warren B Powell. An approximate dynamic programming algorithm for monotone value functions. Operations research, (3(6))1489-40 1511, 2015.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Scok-Jin Kim and Min-hwan Oh. Local anti-concentration class: Logarithmic regret for greedy linear contextual bandit. Advances in Neural Information Processing Systems, 37:77525-77592, 2024.
Branislav Kveton, Milos Hauskrecht, and Carlos Guestrin. Solving factored mdps with hybrid state and action variables. Journal of Artificial Intelligence Research, 27:153-200 201, 2006.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Dhruv Madeka, Kari Torkkola, Carson Eisenach, Anna Luo, Dean P Foster, and Sham M Kakade. Deep inventory management. arXiv preprint arXiv:2210.03117. 2022.
Hongzi Mao, Shaileshh Bojja Venkatakrishnan, Malte Schwarzkopf, and Mohammad Alizadeh. Variance reduction for reinforcement learning in input-driven environments. arXiv preprint arXiv:1807.00224. 2018.
Juliana Nascimento and Warren B Powell. An optimal approximate dynamic programming algorithm for concave, scalar storage problems with vector-valued controls. IEEE Transactions on Automatic Control, (3(11)):995-3014 2013.
Juliana M Nascimento and Warren B Powell. An optimal approximate dynamic programming algorithm for the lagged asset acquisition problem. Mathematics of Operations Research, 34(1):
210-237, 2009.
Afshin Oroojlooyjadid, MohammadReza Nazari, Lawrence V Snyder, and Martin Takáč. A deep network for the beer game: Deep reinforcement learning for inventory optimization. Manufacturing & Service Operations Management, 24(1):285-300 2022.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR, 2016.
Warren B Powell. Reinforcement Learning and Stochastic Optimization: A Unified Framework for Sequential Decisions, volume 22. Taylor & Francis, 2022.
Hanzhang Qin, David Simchi-Levi and Ruihao Zhu. Sailing through the dark: Provably sample- efficient inventory control. Available at SSRN 4652347, 2023.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ Machine Learning, 11(1):1-96, 2018.
Ilya O Ryzhov, Martijn RK Mes, Warren B Powell, and Gerald den Berg. Bayesian exploration for approximate dynamic programming. Operations research, 67(1):198-22 2019.
Devavrat Shah and Qiaomin Xie. Q-learning with nearest neighbors. Advances in Neural Information Processing Systems. 31, 2018.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2) 2012.
Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization in online reinforcement learning. Operations Research, 636-):1636-1652 2023a.
Sean Sinclair, Felipe Vieira Frujeri, Ching-An Cheng, Luke Marshall, Hugo De Oliveira Barbalho, Jingling Li, Jennifer Neville, Ishai Menache, and Adith Swaminathan. Hindsight learning for mdps with exogenous inputs. In International Conference on Machine Learning, pp. 31877-31914, PMLR, 2023b.
13

---

Published as a conference paper at ICLR 2026
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Jia Wan, Sean R Sinclair, Devavrat Shah, and Martin Wainwright. Exploiting exogenous structure for sample-efficient reinforcement learning. arXiv preprint arXiv:2409. 14557, 2024.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features.
In International conference on machine learning, pp. 6995-7004. PMLR, 2019.
Liang Yu, Shuqi Qin, Meng Zhang, Chao Shen, Tao Jiang, and Xiaohong Guan. A review of deep reinforcement learning for smart building energy management. IEEE Internet of Things Journal, (15):12046-1200) 2021.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill, Learning optimal policies with low inherent bellman error. In International Conference on Machine Learning. pp. 10978-10989, PMLR, 2020.
Zhongjun Zhang, Shipra Agrawal, Ilan Lobel, Sean Sinclair, and Christina Lee Yu. Reinforcement learning in mdps with information-orddeed policies. arXiv preprint arXiv:2508. 25002440,,03044, 2025.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory, pp. 5532-4576. PMLR, 2021.
14

---

Published as a conference paper at ICLR 2026
A
TABLE OF NOTATION
Table 1: List of common notations.
Symbol
Definition
Exo-MDP specification
X
Endogenous (system) state space
Exogenous state space
A
Action space
H
Planning horizon
K
Number of episodes
2 X
Endogenous state at time f Exogenous input at time t Action at time t Endogenous transition function, F++1 [11,, 0z: Et)
E
O1 A
x X (()
Exogenous transition kernel Reward function
T:Xx3+A
Policy mapping state to action
(T,,,)
Value function of policy at stage
State-action value function of policy ı at stage h
Regret(K)
Cumulative regret after K episodes
Pure Exploitation Framework
PEL FTL
Pure Exploitation Learning framework
Pure Exploitation algorithm for Exo-bandits (H 1) and tabular Exo-MDPs
LSVI-PE
Pure Exploitation algorithm for Exo-MDPs with linear function approximation
LFA
(())
Feature map of state r Feature dimension
On
Parameter vector at stage /
Pr.
Empirical estimate of exogenous transition stage h Estimated Q- and value functions
Qn, Vh
Logarithmic factor log H2 in regret bounds
Storage Control Example
C
Storage capacity
2h E 10.cl c1
Storage level at stage Price at stage h.
En E
4n = (a 0%)
Charge (a+) discharge actions Charging/discharging efficiencies Post-decision state after action an
n, "7
rh
P(E'L<)
Estimated price transition kernel
Theoretical Analysis
Confidence parameter in high-probability bounds number of anchor points Standard big-O and log-suppressed complexity notation
N 00))0++
B DETAILED RELATED WORK
Exo-MDPs. Exogenous MDPs, a structured sub-class of MDPs, have been introduced and studied in growing line of work (Powell 2022
Dietterich et al. 2018 Efroni et al., 2022 Sinclair et al.) 2023b Feng et al. 2021 Alvo et al. 2023 Chen et al. 2024). Early approaches (e.g.. Dietterich et al.
(2018): Efroni et al. (2022)) ) exploit factorizations that filter out the exogenous process, simplifying learning but potentially yielding suboptimal policies since policies agnostic to the exogenous states need not be optimal. Other work leverages hindsight optimization, bounding regret by the hindsight bias, a problem-dependemt quantity (Sinclair et al., 2023b; Feng et al., 2221). Across this literature, the dominant assumptions that endogenous states and actions discrete and that guarantees
15

---

Published as a conference paper at ICLR 2026
rely on optimism tabular analysis. More recently, Wan et al. (2024) connect Exo-MDPs to linear mixture MDPs, proving regret bounds that are independent from the size of the endogenous state and action spaces, but their results apply only to discrete endogenous states. In contrast, we study Exo-MDPs with continuous endogenous states and Markovian exogenous processes, and establish the first near-optimal regret guarantees for pure exploitation under linear function approximation.
Exploitation-base ADP. A parallel line of research in ADP has shown that greedy or exploitation only strategies can succeed under strong structural assumptions. Nascimento & Powell (2099) analyze a pure-exploitation ADP method for the lagged asset acquisition model, where the concavity of the value function guarantees convergence without explicit exploration. [Naccimnnto & Powell (2013) extend this approach to storage problems with vector-valued controls under similar conditions. More broadly, Jiang Powell| (2015) and Powell (022)) survey methods such as Monotone-ADD. and post-decision exploitation schemes which reduce the need for exploration by leveraging monotonicity or other structural regularities. Related work has also sought to mitigate exploration using Bayesian belief's (Ryzhov et al., 2019) or by exploiting factored state representations (Guestrin et al. [2003 Kveton et al. 2006). However, these methods generally assume discrete state and action spaces, or depend on strong structural conditions (e.g. concavity monotonicity). In contrast, provide finite- sample regret guarantees for pure exploitation in general Exo-MDPs with continuous endogenous states and Markovian exogenous components.
Regret analysis of pure exploitation (exploration-free) methods, Recent work has begun char- acterizing when greedy policies can still achieve sublinear regret. [Bastani et al. (202T) show that in contextual bandits, a fully greedy algorithm attains O(VT) regret under covariate diversity assumption. Civitavecchia & Papini push this into RL, proving that greedy LSVI (no bonus) can yield sublinear regret under sufficient feature diversity. ]edor et al. (202T) analyze greedy strategies in multi-armee bandits and delineate regimes where pure exploitation suffices. [Bayati et al. (2020) demonstrate that in many-armen regimes, greedy policies exploit a "free exploration" effect emerging from the tail structure of the prior to achieve sublinear regret. [Kim & Ohj (2024) gives a broader class of context distributions under which greedy linear contextual bandits enjoy poly-logarithmic regret Kim & Oh (2024). Efroni et al. (2019) show that in finite MDPs, one can match minimax regret bounds by using greedy planning on estimated models (i.e. no explicit exploration). Most recently, Hsssinne et al. 2025) show that in certain structured resource management settings, greedy calle-iteration-tee type methods can enjoy convergence guarantees without explicit exploration. These results suggest that under strong structural or distributional conditions, pure exploitation may rival exploration-basee methods, albeit in narrower settings than general theory guarantees.
MDPs with function approximation. RL with structural assumptions has been studied under both nonparametric and parametric models. Nonparametric approaches, such as imposing Lipschitz continuity or smoothness conditions on the Q-function, offer flexibility but suffer from exponential dependence on state/action dimension (Shah & Xie 2018 Sinclair et al.) 2023a). Parametric approaches trade model flexibility for computational tractability, typically assuming that the MDP can be aprlxxppro by linear representation. This has fueled rich literature on RL with linear function approximation, spanning settings such as low Bellman rank (Jiang et al. 2017 Dann et al..
2018), linear MDPs (Yang & Wang 2019: Jin et al. 2020 Hu et al., (024), low inherent Bellman error Zanette et al., 2020), and linear mixture MDPs (Jia et al. 2020 Ayoub et al.
2020 Zhou et al.,
2021 Indeed, Exo-MDPs are closely related to linear mixture MDPs. Wan et al.
2024 establish
structural equivalence between the two, but only in the case of discrete endogenous and exogenous
spaces. Our contribution focuses adapting the machinery of linear function approximation to Exo- MDPs for continuous endogenous spaces, and show that their properties allow for pure exploitation strategies achieve near-optimal regret.
Exo-MDPs in practice. A growing empirical literature has applied function approximation (typically using neural networks) to Exo-MDPs in operations research applications, particular in inventory
control and resource management problems (Madeka et al., 2022] Alvo et al.) 2023 Fan et al.) 2024 Qin al. 2023). These works demonstrate strong practical performance but provide limited theoretical guarantees. In contrast, our contribution simplifies the function class to linear function approximation, which allows us to obtain sharp regret bounds while retaining the structural advantage of Exo-MDPs. Moreover, while some prior work focused on heuristic policy classes such as base stock policies (Agrawal Jia 2022, /hhng et al. (205)), our algorithms converge to the true optimal policy, thereby avoiding the suboptimality inherent to such restricted classes. Lastly we note that RI.
16

---

Published as a conference paper at ICLR 2026
has been applied various other problems in operations research (without exploiting their Exo-MDP structure) including ride-sharing systems (Feng et al. [021), stochastic queuing networks (Dai & Gluzman 202T), and jitter buffers (Fang et al. 2019). Applications of our method potentially improve sample efficiency in these applications by exploiting the underlying exogenous structure.
C DISCUSSION ON EXO-MDP MODELING ASSUMPTIONS
C.I KNOWN TRANSITION FUNCTIONS AND REWARD FUNCTIONS.
Our model assumes that the endogenous dynamics f and the reward function known and deterministic given the exogenous state. While this assumption is more restrictive than the fully general unknown MDP model typically studied in the RL literature, it is well-motivated in many operations research domains. Indeed, inventory control, pricing, scheduling, and resource allocation problems are often modeled with deterministic system dynamies where the only uncertainty arises from exogenous randomness (Powell 2022). This assumption also aligns with the practice of simulator-bel based design, widely adopted queueing and inventory control studies (e.g., Madeka et (2022): Alvo et al. (2023) Che et al. (2024)).
We highlight several aspects of the assumption that the transition and reward function f and are known below.
C.1.1 SUFFICIENCY
These assumptions are precisely what make pure exploitation viable. Once and known the only source of uncertainty is the exogenous distribution P- {) which is independent of the learner's s actions. This structure enables data reuse and counterfactual value estimation and is the basis for our regret guarantees. No analysis of PE in even fully tabular Exo-MDP (with Markovian exogeneous proceses). We establish the regret bound first to show the effectiveness of PE in the case of continuous endogenous state space and continuous action space.
in tabular Exo-MDP, and more importantly, we are the
C.1.2 NECESSITY
First, we show that in Proposition 2 and Theorem 5 that there exist 2-armed Bernoulli bandits such that PEL (FTL, greedy w.r.t. empirical means) suffers linear regret.
Impossibility with unknown reward functions. Because (I-step) bandit is special case of tabular Exo-MDP with unknown reward function, this directly yields:
1, a single state x, and finite action set A. The reward of each action E A is an unknown random variable with mean ((a)= == (fr(a, E)]. Any pure-exploitation algorithm suffers Q(K) expected regret on some MDP in this class.
Corollary 1. Consider the class tabular Exo-MDPs with horizon
Proof. A 1-step, 1-state tabular Exo-MDP with unknown reward function is exactly stochastic MAB, with each action corresponding to an arm and the (unknown) random reward R2 = r(a, E). Theorem then yields instance which any pure-exploitation algorithm has (?(K) regret. L
Over the class of tabular Exo-MDPs with unknown reward function pure exploitation is not minimax-optimal. No pure-exploitation algorithm can guarantee O(K) regret in the worst case.
Impossibility with unknown transition functions. Unknown transition functions and known terminal reward are equivalent (from the learner's 's perspective) to unknown rewards of the two actions h 1. A pure-exploitation algorithm that plans greedily from estimated model behaves just like a pure-greedy bandit algorithm on the two "effective arms" corresponding to "go to state or 2". Formaly, let A be any pure-exploitation algorithm that uses its estimates of the transition function (e.g., empirical transition frequencies) choose, in each episode, action z (0) that maximizes its current estimated value function, never choosing actions whose estimated value is strictly smaller than another action's estimated value.
17

---

Published as a conference paper at ICLR 2026
Corollary 2. Consider tabular Exo-MDPs with horizon H = 2, state space X' = {xx0), (z=()),(1) 2 and action set A {1.2}. The initial state is always 20 At the first step L, the transition from (0))) under action E {1,2} } is random:
(((a = f(x(0) a,
where each action a leads to stochastic state x(((aa) E {x(1)),x())), At the second step h = 2, the episode terminates and (known) deterministic reward is obtained, and the initial return for each action is given by
R₂ = P(i(a) 1))(x(() + PP(((a) ())(2
In particular, we choose f and r(x(1)), r((((2)) such that
R1 = 2
=2=
for some fixed A (0, 1/4), independently across episodes. Then there exists a choice of f and r(x()), r(x(2)) such that the expected cumulative regret of A over K episodes is ((K)).
Proof. From the learner's s perspective, each action a E {1, 2} induces an unknown expected return equal the (known) reward of the state it deterministically reaches at h 2. Thus the problem is
equivalent to a two-armed bandit with unknown means + and 2. A pure-exploitation algorithm that always selects action with maximal estimated value behaves exactly like pure-greedy bandit
algorithm on these two arms. By the same argument as in Theorem (5) there exists an stochastic assignment of actions terminal states such that the algorithm suffers (2(K)) expected regret. D
Necessity of known endogenous transition functions and rewards. Corollaries and 2 show that, as soon as either the reward function or the transition function is unknown, the class of tabular Exo-MDPs already contains instances where any pure-exploitation algorithm incurs linear regret. In particular, pure exploitation is not minimax-sufficiien in these settings.
By contrast, our Exo-MDP framework we assume that the endogenous dynamics f and reward function r are known, and only the exogenous kernel is unknown. This structural assumption is crucial. allows us to design pure-exploitation algorithms that achieve sublinear regret, in sharp contrast to the tabular Exo-MDP setting with unknown f or r.
C.1.3 REASONABLENESS
Example applications of EXO-MDP We have introduced the storage control in Section See (Pow
ell 2022 Sinclair et al. 2023a for a more exhaustive list.
Inventory control. In classical inventory models, the endogenous state 24, is the on- ma- inventory level, while the exogenous state &n is the demand realization at time h (Madeka et al. 2022). Actions aş correspond order quantities. The system dynamics
deterministic given demand, e.g. the
newsvendor dynamics FA+1 = [ (1+)) = max (IA + 4A Ex+1, 0}. The reward depends on sales revenue and holding or stockout costs, r(#,, an (x). The only randomness arises from the exogenous demand process, making this a canonical instance of an Exo-MDP.
Cloud resource allocation. In cloud computing and service systems, the endogenous state 2. may represent the allocation of resources (e.g., virtual machines, CPU quotas, or bandwidth) across job requests (Sinclair al. 2023b). The exogenous state εn captures job arrivals at time which evolve independently of the resource allocation policy. Actions correspond to scheduling decisions, and the reward reflects performance metrics such throughput or delay penalties. The exogenous job-arriva process drives all stochasticity, while the system dynamics (queue updates, resource usage) are deterministic given arrivals.
C.2 DISCUSSIONS ON ANCHOR SET
C.2.1 KNOWLEDGE OF ANCHOR SET
While knowing the anchor set a priori appears strong from a general RL perspective, this assumption well-motivated in our Exo-MDP setting:
18

---

Published as a conference paper at ICLR 2026
Anchor states are designed by the learner. Assumption 1 requires that we fix finite collection of post-decision states (n) such that the feature matrix 4 == [0 (1)), ...,, ( (NV)] has full row rank. These states are the representative grid that the practitioner chooses when constructing
the feature map ø. including hat basis, spline knots, tile centers (Sutton et al. 1998). This mirrors
standard RL with LFA, where the learner chooses & and implicitly chooses the basis points which é is built.
This is standard in ADP and matches how Exo-MDPs are implemented in practice. Anchor states standard in ADP for control and operation research applications Nascimento & Powell (2009) 2013);
Powell (022). In applications like inventory control and storage systems Nascimento & Powell (2009] 2013), practitioners often can exploit domain knowledge and problem structure, e.g. piecewise- linearity or convexity of the value functions Powell| (2022). For instance, with piecewise- hat features, anchors are just the breakpoints of the basis functions Nascimento & Powell (2013) Powell
(2022). This is also shown our storage control example in Section 6.2.
C.2.2 CONNECTIONS TO CORESET AND FRANK-WOLFE PROCEDURES
The anchors in Assumption 1 act as small, cell-conditioned spanning set of feature vectors, analogous in spirit to coresets used in linear RL and ADP. We clarify the connections and differences below.
Anchor sets serve the similar purpose as coresets in linear RL and ADP. In our paper, anchor sets provide well-conditioned spanning set of feature vectors enabling stable value regression and Bellman transport. This is similar to the concept of coresets or representative set in linear bandits and RL, e.g. Mahallnobis-distaaee representative sets in Yang & Wang (2019) with well-conditioned feature coverage, optimal design in Lattimore & Szepesvári (2020) with minimal set of points that well-condition the Gram matrix, coreset with well-conditioned feature coverage in Eaton et al. (2025).
Regarding the connections between coreset and Frank-Wold Wolfe (FW) methods, which arises in convex optimization. Specifically, the coresct there represents small subset of points that approximately represents much larger dataset for the purpose of convex optimization. FW constructs such coresets by iteratively selecting "anchor" points via the linear minimization oracle. This idea has been used in problems such as learning convex bodies Clarkson (2010), sparse convex optimization [Jaggi (2013), and practical large-scale machine learning Bachem et al. (2017). However, FW-based coreset construction has largely remained within the convex optimization literature rather than RL settings involving linear function approximation.
In contrast, in our Exo-MDP setting, the anchor set is designed a priori using domain knowledge and problem structure. In many structured control problems they can be constructed a priori, without observing any data, For example, inventory or resource-str resource-storage problems, anchors can be naturally chosen as grid of storage levels, e.g., extreme low / high and intermediate points, which are natural design points for value approximation.
Extension from domain-driven anchors to algorithmic construction. Our currunt method leverages domain knowlege or problem struture. When such problem-dependen design choice is difficult, promising direction to adapts anchor selection online. We first generate large pool of candidate post-decision states, and adaptively construct the anchors by FW-like methods.
C.2.3 INVERTABILITY AND WELL CONDITIONEDNESS
Anchors are fully user-selected, and practitioners can exploit domain knowledge or problem structure to construct a well-spread collection of feature vectors. In principle, one can precompute the anchor feature vectors ((*)) offline, prior to learning, ensuring that Σ is full-rank and well-conditioned. For example, in the storage control experiment in Section 6.2, a simple uniform grid yields Σ IN and Ag = 1.
Ridge regression, however, is a promising method to improve the inveriiilityymummrrial stability while tradeoffing bias. While we can improve the invertibility of Σ by carefully designing the anchors and features, such process can be computationally heavy sometimes. Regularization invertibility with a controlled bias term. It trades a small bias controlled by 3 for numerical stability. We now provide short theoretical sketch showing how f-regularrzerr impacts the regret bound.
replace strict
19

---

Published as a conference paper at ICLR 2026
The regret bound in Theorem 2 states
(VN/A> v2)
Letting Ag == A + 5, then reg. reduces the conditioning part of the regret bound to (VN/A8
E H VTV. K. However, it introduces the additional bias as it solves reguralized problem
min V. y112 + B1
So even if the model is perfectly realizable (no approximation error), we can show that his induces an extra Bellman error term of order Åg vd, which then propagates through the horizon and across K episodes. Therefore, the total regret bound is worsened as
N/N/> VajE
K Vd. Vλo Ag
In the realizable setting our main theory takes O, so no extra bias term appears. one adds small ridge term 37 numerical stability, the analysis can be interpreted as introducing effective
inherent Bellman error of size Eridge = O X
vd). which adds an 3HvRK Thus ridge reduces only
x
constants in the O(vK) K) term, but introduces an additional linear-in-K contribution, which vanishes B O.
C.2.4 EXAMPLE WHERE ASSUMPTION 4 HOLDS
Models. Consider an storage control Exo-MDP where the endogenous (pre-decision) storage state Iy E [0, Rmaa] At each stage the controller chooses an action E A(2,, C. R, which produces post-decision storage
2/1 Ll Rmaxe (zh + an):
where II denotes projection onto [0, Rmaa] After acting, the exogenous state evolves as En+1 ~ IP(( {n) and the storage evolves according to
Th+1 [l Runz (A(En+ 2i + b(EN+1));
with efficiencc//reention factor A(E') E [0, and inflow/outflow b(g') E R. The next post-decision storage under policy л is then
tht1 II Io (Iu+1 + ((12+1,E++1))
The one-period reward is bounded measurable function r' ra( (h, Ex.
Basis, anchors, and value representation. Choose storage anchors 0 = Po < 0r < ... PN Rmax- Define nonnegative, nodal, partition-of-unigg piecewise-linear hat functions {1 (p) and set
<pp) (no(p). (p)),
p(pn)= =n- Cn-
Thus each ø(p) is a convex combination of anchor vectors. The post-decision value is represented using storage-only features and information- dependent weights:
V (x),E) d(x") (T)(
where (E) R1 and [w][()) VTT (n.,)). E). At the terminal time, weights encode salvage values, egg. (E)
(E)] S(pn,
Recall that Assumption 4 holds if for each h. policy and exogenous realization ç', there exists a storage-feature transport matrix MT(E') e (N++)) such that for all post-decision storage states d E [0, R,uxx]
(I(an.((5)) Bn,x(()))) = o(z)),
20

---

Published as a conference paper at ICLR 2026
where (5') and (5') the coefficients induced by the composition of the storage dynamics and the policy's action, followed by projection. Crucially, (i, does not depend on x", so the identity holds globally. The weights evolve linearly in expectation over E::
(E) Eewerriss ME( w[+1(5')]
This formulation is reasonable under the following conditions. First, the post-decision to next pre-decision mapping is affine in r", possibly followed by clipping. Second, the policy æ is piecewise- affine in that the overall map to rh41 is affine with clipping. Third, the storage basis ø is translation-stable: for any affine map + II(r + 3) there exists fixed sparse matrix Sa,s such that <(I[(rr + 8)) = S., ((,) for r. Finally, since á forms a partition of unity and clipping corrssoodss to convex mixing with boundary anchors, each Mf("" is row-stochastic or sub-stochastic, and therefore non-expansive with |M (C) S 1.
C.2.5 WHEN ASSUMPTION 3 HOLDS
Assumption 3 requires that every post-decision feature vector can written as nonnegative combination of a fixed set of anchor feature vectors. This section lists common modeling choices under which the condition automatically satisfied and gives a simple recipe to enforce it in practice. Assumption aligns with widely used feature constructions in ADP/RL (tabular, hat/spline, histogram, grid/ReLU bases).
Tabular features.
With one-hot features, each post-decision state corresponds standard basis vector, which in the conic (indeed, convex) hull of the anchor set by construction.
Storage with piecewise-liness (hat) features. Let 0 Po P1 storage anchors and define nonnegative, nodal, partition-of-unity hat functions {n IN Set p(p) that ((p)) en and En (p)
< PN Rmax be
(no (p)( ... (p))
for all p. For any post-decision level xx" E [0, Rmax], we have 6(x") = Σn, Ya (=(")) ((p)) with Vnn (x²) 2 O, so o(x") lies in the conic hull of the anchor features (in fact, in their convex hull). Clipping at the bounds and Rmax simply mixes with boundary anchors and preserves nonnegativity.
Histogram / indicator bases. If é is formed by nonoverlapping (or softly overlapping) nonnegative basis functions that sum to at most one (e.g., bin indicators or triangular kernels), then ((x") is nonnegative combination of the anchor features obtained by placing anchors the bin centers knot points.
B-splines and ReLU tiles. Nonnegative partition-of-unity spline bases (e.g.. linear B- B-spines)) and grid-based ReLU "tiles" yield 6(x") with nonnegative entries and local support. Choosing anchors at the knots/cell corners makes (xx:") a nonnegative combination of anchor feature vectors.
To ensure Assumption 3 (i) include boundary anchors so that clipping/projection maps to anchors; (ii) use nonnegative, locally supported basis functions that form (approximate) partitions of unity over the post-decision domain; (iii) place anchors at the basis nodes (knots, cell corners, representative states) so that ((staee) a sparse nonnegative combination of anchor columns. If a signed feature map is preferred (e.g., mean-centered features), a standard fix is a nonnegative lifting ø = (6+; Φ-] with Φ+ maxfó, 0} and d_ max o, 0}: placing anchors the lifted coordinates restores the cone property.
C.2.6 WHEN THE BOUND supn.g,t [[ S HOLDS
Recall under Assumption 2 or Assumption that for each (h, (,)) one builds mixing matrix
(g(g') ((N++)((N+1))
whose n-th row contains the interpolation weights (Ey () 0 (usually two nonzeros) taking the anchor Pn. to the next post-decision storage rf and then back onto the anchor grid. Thus each row sums to 1 (row-stochastic; aub-stochastic the capacity boundaries when clipping pins Po or PN). We provide some sufficient conditions for || M (g') I 1 below.
Lipschitz-in-stone intrrragg- dynamics with hat basis. If the continuous map T(r) I[ + () is 1-Lipschitz (i.c., al < 1) and functions r are represented on a uniform grid with nodal PLC interpolation, then the discrete composition operator interpolate 7 is nonexpansive on grid values under the Fuclidean
21

---

Published as a conference paper at ICLR 2026
norm. This operator is exactly Mr (5'),, hence (5 I 1. Intuitively, 1-Lipschitz maps do not increase distances between storage levels; interpolation preserves (and slightly underestimates) distances, the induced linear map is nonexpansive.
Doubly (sub-)stochee )stochastic mixing. If every M, (5") is row-stochastic and column-sub-ssochasee (all column sums 1), then
|M S (IIMg(E9II (M) I vI.1 =1
Column-sub--soccastin holds, for example, if the one-step map in storage is monotone and nonexpansive: r + I[(ar= +3) with |a| S I, and the basis nodal hat (partition-of-unity features on uniform grid. Each anchor's "mass" spreads to at most two neighbors without duplication, and clipping removes mass near the boundaries.
Decomposition into contractions. If the mixing matrix can be expressed convex combination of contractions,
(5') - TeTe
Te 20 Σ == = 1, ||Tlle <
then by subadditivity and convexity of the operator norm, [M < 1. Two useful instances are: Permutation/shifft structure: when the map is grid shift or clipping, each Te is a permutation (possibly composed with boundary projector), hence |[Te|l2 1. Row-weighted permutations: M = E, D,II, with II, permutations and D2 diagonal with entries in [0, 1], then || S EeIlDele Ee (Dz)ss If the row-wise weights over sum to 1, the bound is 1.
Doubly-stochasey special case. columns also sum to 1 (e.g., pure permutations, or measure- periodic grid), then M is doubly stochastic and
preserving monotone maps without clipping with equality only if M is a permutation.
|| <
Furthermore, provide some methods to check or enforce the assumption. Empirically, one can draw a batch of g ~ Q( E). build (E'). and compute the largest singular value maxx verifying max max I 1 (allowing numerical tolerance). Design-wise, one can ensure nonexpansiveness by using uniform nodal hat features (partition of unity), storage dynamics with |al < 1, and capacity clipping. If some scenarios have la] > (expansive), increase grid resolution or add a smoothing step (row-wise convex averaging) that preserves row sums, making M a contraction. For non- non-unifore uniform grids or unusual features, "whitening" each local two-anchor block (normalizing columns per cell) enforces contraction while preserving row sums.
Under storage-only anchors and nodal, nonnegative, partition-of-unile hat basis, and with standard storage dynamics (affine + clipping) satisfying |ax| S 1, the transport matrices M (g') are row- stochastic and numerically, and if needed enforced by smoothing or per-cell normalization without altering the PLC interpolation semantics.
Hence supx.e.A (e)ll < 1. This can be verified
Connections to Nascimento & Powell (2013). Under the modeling assumptions in Nascimento & Powell (013)) the bound is justified when one implements the storage-only anchor/hat hash//stt-bsssssts scheme. Nascimento & Powell (2033) works in post-decision form and shows that, for each information state, the value function in the scalar storage is piecewise-lined concave with breakpoints. Each period's decision is obtained from deterministic linear program with vector-valued control, and the algorithm maintains concavity of slopes via projection. This is exactly the setting where one uses storage-only anchors {p,) and nodal hat features. The storage dynamics between periods are affine plus clipping: the model introduces exogenous changes in storage in post-decision form, so that the next storage is an additive update (possibly with losses) followed by projection to capacity. This map is 1- 1-Lipschitz in the storage variable.
With nodal, nonnegative, partition-of-unity hat functions on {pr}, the push-forward and interpolation step from an anchor Pn. produces a row-stochastic mixing row (two nonzeros in one dimension). Collecting these rows defines the matrix MT Because the underlying continuous map is Lipschitz and interpolation is stable, the induced discrete operator on nodal values is nonexpansive in the Euclidean norm, hence ||M (E)ll2 < 1. At capacity boundaries, clipping only reduces distances, so the bound continues to hold. This is consistent with the PLC/anchor structure and concavity projection used in the paper. It should be noted that the paper does not phrase its analysis in terms of an M matrix or spectral-norm bound. Instead, it proceeds via dynamic programming operator on
22

---

Published as a conference paper at ICLR 2026
slope vectors with technical conditions ensuring monotonicity, continuity, and convergence. Thus the spectral norm assumption is an implied property of the standard discretization, rather than a stated theorem.
In summary, for Nascimento & Powell (2013), with the standard storage law (additive exoge- nous changes with clipping) and the PLC/anche representation, the discretization induces row- stochastic (and nonexpansive) mixing operators. Therefore is reasonable and consistent to assume SuP,,E.A A (E) I even though the paper establishes convergence via slope-operator mono- tonicity and continuity rather than an explicit spectral-norn bound.
C.2.7 WEAKENING AND RELAXATIONS
Adaptive anchors selection via coreset/Frank-Noe Wolfe style procedures. The anchors can be viewed as a small, hand-picked coresct for the endogenous space. In principle, we can learn this coreset from data via coreset/Frank- Wolfe style procedures and then rumning LSVI-PE on the resulting anchors. Analyzing such scheme requires second layer of error control between the data-driven anchors and the optimal anchor set and is beyond the scope of the present work, we now mention this as promising direction in the Conclusion.
Approximate closure assumptions via inherent Bellman error. The realizable analysis (Theorems 2 2-3) uses Assumptions 2-3 (or 4) to guarantee exact closure of Bellman updates in the anchor span. However, our agnostic analysis (Theorems 4-5) only requires the basic Assumption plus a finite inherent Bellman error. In other words, even if the post-decision values only approximately representable by the anchor features and the cone/closure conditions only hold approximately, the regret bound still holds with an additional O( bias term. This already provides quantitative weakening: violations of Assumptions 2-3 are absorbed into êEE rather than being ruled out outright.
C.3 ADDITIONAL DISCUSSIONS
m-Markovian exogenous process. Our framework extends to exogenous processes with finite memory. Specifically, assume that the exogenous state follows m-Markov model: time h, the augmented state includes the endogenous component 24 together with the last m exogenous states,
8/ (Ir,, ,.. En)
The next exogenous state fn+1 is drawn from conditional distribution that depends only the most recent &t exogenous states:
Ex+1 ~ IP( En-m....,
This formulation strictly generalizes the i.i.d. and first-order Markov settings while retaining compact representation that captures temporal correlations in the exogenous sequence.
D OMITTED DISCUSSION IN SECTION
Here we outline the application of PEL (and FTL) to the simpler tabular Exo-MDP settings.
D.1 FTL FOR TABULAR Exo-MDPs
As discussed in Section D one can extend the FTL principle to finite-horizon Exo-MDPs with finite state and action spaces. For any deterministic policy æ, using the exogenous traces ( ck-1) collected up to episode k; we can form the unbiased empirical value estimator:
k-1
k-1
Vki (s1)
(7
r r Tn (sn).. Eh)
=
k
k
where the transitions take the form
Sh+1 (1++1:5h+1).
Fk+1 f(In, (h.n)))
23

---

Published as a conference paper at ICLR 2026
The FTL algorithm then selects the greedy policy in episode & with respect to these empirical value estimates:
#
arg V( xell
This construction crucially leverages the fact that the exogenous trace distribution & is independent of the agent's 's actions. Hence, every exogenous trace can be reused to evaluate all candidate policies without bias, a property that enables policy-level FTL in Exo-MDPs and sharply contrasts with general MDPs where action-dependent transitions break this replay.
The following proposition is a restatement of known ERM/FTL-style guarantees in this setting. Note, however, that the computational cost of unconstrained search II be prohibitive.
For any å E (0, 1), with Proposition 3. [FTL guarantee, Theorem 7 in Sinclair et al. [023b
probability at least 1 - 6,
2 log (8)
SR (FTL, K) S H
K
In the tabular case this gives the stated dependence ||||
S A
Motivated by the proof of regret bound of FTL for Exo-MAB, we also provide the expected regret bound of FTL for Exo-MDP.
Proposition 4. The expected regret of FTL can be bounded
E[SR (FTL, K)] S H log III
K
In the tabular case this gives the stated dependence [I]] & A
Thus, while the statistical guarantees for FTL are strong, the algorithm is computationally infeasible in practice due the exponential size of the policy space. This motivates more efficient implementations of PEL that avoid enumerating IT. In particular, one can estimate the exogenous transition model directly and then apply dynamic programming compute greedy policies- approach refer to as Predict-Thent TheppiieTeen-ppimmiee (PTO) in Section
D.2 PTO UNDER GENERAL m- M--MARKOVIAN CASE
For the general Markovian setting, PTO learns the transition model P (En (h-1) to approximate the true distribution IP (Es. Ea-1). PTO uses the model P (Ex. E)-1) to solve the Bellman equation. PTO uses the maximum likelihood estimator of transition model, which is the empirical distribution
1-
k-1
P (En Eh-1)
(Eh-1 = En-1, th En
Σ
(Eh-1 = En-1)
to solve the Bellman equation
(nh, an) = BEales- r(rn, an, En) Vata (J (In ons En),
=: BEalen- r(In, ans En) Vh+1 (f (I ap, En), En), [n)
(sn)
Qn an)
a1.
कe (sh) arg max Qn (Sh, an),
a,EA
where 8n = (In, En-1). Note that the size of policy set [I depends on the m
x A MIx), m O, ||E = A x|EI m =
H
h=1
| A YH 1 -(AIIIEE)))) ), m, H.
24

---

Published as a conference paper at ICLR 2026
Proposition 5 (Theorem 6 in Sinclair et al. (202b)). Suppose that
PP (P - P (<x) Sc. sup he Sc
Then we have that In addition, if each &n is independent from &ch+ then vA (0, 1), with probability at least - 8
SR (n, K) S H²
2 log (2H/6)
SR (ft K S 2
K
Therefore, the regret of PTO can be bounded as follows.
Corollary 3. Fix E (0, 1). with probability at least 1 6,
H
2H Los(A/5 (A/5)
m 0,
K
SR (TTLKK) S
2
m 1, loR(A/6)
K
HV
2
log( (A/8)
m H.
Corollary 4.
H
H (og(A)
O,
E|SR (FTL, K)] S
H
H log(A)
m7 1,
H
H-1 log(A)
H.
K
Proof of Proposition Qn and VA refer to the Q and V values for the optimal policy in M where the exogenous input distribution is replaced by its estimate F(- En-1). Denote by V the value function for some policy æ in the MDP M. Then V Vn by construction.
SR (f, K) = V/ (s1) 1/$ (s1)
= V/" (81) DT" (s1) + Vi (81) - Vi
-VV V/ (81)
$ 2 sup Vi" (s1) - Vi" (s1)
By the simulation lemma, it is bounded above by 4f max,,0, (P, a) 100--pp Pr a)l. Since PA (-1s,a) the pushfoward measure of TP 1)- under mapping /
Pa(s's E a)) = (,, - (1, = TP (ʃ (s, a, En-
we have (since f is function)
Pr(ssa)= - (s
|P (m-1) - P 16-1)) -
and thus
Ph(s,a) -
P (1-1) - P En
max saa,
max h.E-1
Then the proof for the first part is finished
SR (R, K) H
max hrEA-1
(c (1-1) P (n-1)
Now suppose that & ~ P has each &n independent from En-1 and let IP be the empirical distribution. Using the & concentration bound shows that the event
vh |i E PPEA E =))],
2 2 (1/))
8 E
<
K
occurs with probability at least 5. Under E we then have that:
| (.1 (x-1) - P( E--1) 5/
2 = log H/8)
max k (e[M) 1)
K
Taking this in the previous result shows the claim.
25

---

Published as a conference paper at ICLR 2026
Remark 2. The quadratic horizon multiplicative factor ( in regret is due to compounding emrors in the distribution shift. In the worst case, can scale as O(E= if each &n is correlated with Êa-1- Remark Proposition is not valid for the m-Marrkovia case. A straightforward extension of the proof for Exo-Bandit is not valid since
V max V..M o max B[V S E E|max VT.M] E[V
The inequality is due to that the value function is nonlinear in P and Ps. y P.. for L + 1'. In partieular, EVV] = E(r + Pr v = тΛ + E[PA(r++1 + PA+t P(+2)l = Th + PATh+1 + +[PP, Pa+ V442 # Th PaTh+1 + Pr
D.3 REGRET BOUNDS OF OPTIMISM-BASED METHODS FOR TABULAR EXO-MDPS
D.3.1 REGRET BOUND OF UCB FOR EXO-MAB
Proposition 6 (UCB for Exo-MAB). The expected cumulative regret of UCB in the full information setting with arms satisfies
CR (UCB, K) & (og(A)3)(KK 0(1)
Proof. With prob. at least
6, the event E holds
Va E [A], Ak E [K], | - pa(+)) & b.(k)) = / 20² log(AK/0)
1:
Conditioned on event E, the simple regret can be bounded as
log (AK/8)))
SR (UCB, k) p= Ma,, (k) Maz Jan (k) Mas 2han (k) 2 20
21/200
The expected simple regret is bounded
SR (UCB, k)) = Elue* - May] = Elue" May [E)((E) + El11 Ma. (E9P(EE) S 2 20 log( (AK/6)
+ 5.
k 6-1
Therefore, the expected total regret
K
log(Ak/)) (KK/))
CR (UCB, K) S - 2 20
+0 S 220 (K/8))( K6.
k k-1
t=2
Choosing 1/K yields
CR (UCB, &
0(1)
50 K log A) OOvv Klog K).
D.3.2 REGRET BOUND OF OPTIMISTIC PTO FOR TABULAR EXO-MDP
We consider PTO-Opt, an optimistic version of PTO, which replaces the exogenous transition model with its optimistic version. In episode k. PTO-Opt performs
Q (sh, an) == r ah En) + E (f an PP
=r an En) + (.l((ce-P((e)) (C)(E) &'
Σ
VE an (441)55441
#*n) E arg max (8h, an), V/h = (*(,
Proposition 7 (High probability cumulative regret bound of PTO-Opt). Fix any E (0, 1). With probability at least 1 8,
CR (PTO-Opt,K))
Compared with Theorem I PTO-Opt has slightly worse regret bound. This verifies that PEL is sufficient for tabular EXo-MDP with simple implementations.
26

---

Published as a conference paper at ICLR 2026
E OMITTED DISCUSSION IN SECTION 5
E. LSVI-PE -PE WITH MISSPECIPICATION (APPROXIMATION) ERROR.
Here consider the case where the function class is misspecified and the true value functions may not lie exactly in the linear span. To capture this, we introduce the notion of post-decision Bellman operators.
Write x=:== = (((x,,)) For any Unti X R.
(T* .) = EgrwPa (( ((',, +
51]. (TUn+1)(z", .E) (e max {r(x', ,',')) ( d'), {
Let Fn == (10, + 6(x4) (E): wx(E) R2) be the post-decision linear class at stage h.
We then have the Bellman errors or approximation errors as follows:
Definition 3 (Inherent Bellman error). Define the (post-decision) inherent Bellman errors
T BE
:- max sup sup hE(P) {EB 11 W.EP& x"
inf sup (T*
(z
max = BE
sup ke( EEE 1 1EF WAEN, (Tp -0,(=,, E
max sup
inf
We will use BE == max mmxx J.
Theorem 4. Assume Assumption hoolds. Fix 5 E (0, 1).
Then with probability at least - 8,
CR (LSVI-PE, < Ô
H
EHKK +
K EBE
VAo
Compared to the realizable case, the regret bound now includes an additional bias term, linear in K, that scales with the inherent Bellman error CBE. This term is unavoidable in general agnostic settings: B is fixed, even an oracle learner suffers an O(KBB)) cumulative bias (Zanette et al. 2020).
F PROOFS OF REGRET BOUNDS IN SECTION
F.1 EXO-BANDITS
Proposition 1. Assume rewards are oz-sub-Gaussian. Then the expected per-round simple re-
gret of FTL satisfies SR (FTTL,,)) S
20 2og k-1
and consequently the cumulative regret obeys
CR (FTL, K) S 20 /(K
log A.
To show the result we start with the following lemma. Lemma 1 (Maxima of sub-Gaussian random variables). Let XI...., X,, be independent su-sub- Gaussian random variables. Then
max ISiSn
X,
< 222 12g2
and, for every t >> 0,
max X, /20² (logn +t) sssn
Sett X V 20 log(n/o) 56
or equivalently
P
max ISSn
Proof. The first part is quite standard: by Jensen's inequality, monotonicity of exp, and o². subgaussianity, we have, for every X > 0,
ABlmaxiges x.) < Scdmaxigisa X,
max EA 1si5n
< E AX. S ne
2212
27

---

Published as a conference paper at ICLR 2026
so, taking logarithms and reorganizing, have
1 +
Ao
max X Ss
$ In
Choosing À
2 a²
proves the first inequality.
Turning to the second inequality, let
/202(1og + 1). We have
max Isisn
= =
X,
2 u
Σ P (X tf S ne =
the last equality recalling our setting of u.
Now we provide the proof of Proposition
Proof. Observe that the empirical mean unbiased for each arm at each round.
SR (FTL,, k) n¹ Eljaa.] = max Rl - payl = max Elja((k) [Ma)] S Elmax (k) 14
a
Bllia (k) - Marl
- max Pro (k) Mal aE[A
2n log A/(K - 1):
where the last inequality due to Lemma [
Therefore, we have
K
CR (F =
SR (FTL, k)
S
20 log A/(k- 1) s 20 (K - 1) log A.
k=1
F.2 TABULAR EXO-MDP
Proposition 3. [FTL guarantee, Theorem 7 in Sinclair et al. [023b probability at least 1 - 6,
For any 5 E (0,1), 1), with
log 11 (8)
SR (FTL, K) < H
K
In the tabular case this gives the stated dependence [II| < [
Proof. Observe that V (s1, <*) are iid r.v.s, each of which has mean V/T (s1). Using Hoeffding's inequality and a union bound over all policies shows that the event
H2 log (2) 2111/00
Vn IT: VVT (s1) [V7 (s1)
2K
occurs with probability at least 8. Under & we then have
SR (FTL, K) V (s1) - V*** (s1)
VT' (s1) - E. VTT' (81, k)
F VT' (51, {)]
[vp (s1,
+ E y (s1, E)
Vi (51)
H2 log 1 (5)
$ 2/
2K
28

---

Published as a conference paper at ICLR 2026
Proposition 4. The expected regret of FTL can be bounded as
E[SR (FTL, K)] H2 log III K
In the tabular case this gives the stated dependence [| S A Proof. It holds that
ESS (FTL, VI (s1) - E[V (51) max B|B (s1, - BEV"" (s1)
s E[max E [V (s E)ll - E (s1)
= BM (s1) - Vi** (s1)
S E[max V (s1) Vi" (s1)
H2 log IT
K
where the last inequality is due to Lemma
F.3 PROOF OF THEOREM
Lemma 2 (Data processing inequality, TV distance). Let μl, be two probability measures discrete set X and f X + Y be a mapping. Let f# and f#.. be the resulting push-forward measures the space Y. Then
11 SHwll1 S 11ee ull
Proof.
If Stuul1 =
Σ (Hta()) - St,(lU) Σ -1))
VEY
DEY
Σ1 Σ m(x) Σ w(x))
-Ef-
xEf-t(M)
<
Σ
uu(x) - -((x)
Σ
[u(x) - v(x) = -11a-vih
yEY (M)
zeX
where the second inequality is due to the triangle inequality.
F.3.1 PROOF USING EXPECTED SIMULATION LEMMA
Lemma 3 (Simulation lemma, expected version). Let M = (P.r) and M = r)), Define
25 2
(s. a) = (s)((s))) - PA(s,))ll S
Cn(s,a)
For any fixed policy æ and 81 P.
#
M..M - -VMM
E
H ()n,(sh,a)le P.p.
4=1
It also holds that for any 81
H -1
ya.M (81) -V (81) < E
H h)cx(5h, an) P,81
29

---

Published as a conference paper at ICLR 2026
Proof. For two different MDPs, their values are defined for the same initial distribution p(s1)
|VaM VaM [B[V (81)) - E (81)]
- (P|V2 + [P112 M. 1 (P ((),)))
1o(P1(V2 - V.T.M. [[( + ((P [() (Is,
IB[V (82) V.- (s2)| pPF (H- 1) EEle (81, p, (s)))
1V V/T, + (H - 1) (le, |s a, = (s1)]
S IV V..Ma || + [ - 1)6 + (H - 2)c 02) P.p.
Σ (H - h)en aT) P.P
Note that the expectation taken w.r.t.
$1 Pl.--- .,, Th (sh), 5h+1 (h))
The policy æ and transitions P, P' are considered fixed, which implies that en2 (8, a) is NOT random for fixed (8,0) ().
For [K]. h (H), define the filtration
F = ((s) 0% mee[k- (sh a )ree(n))))
The policy a is measurable w.r.t. Fi. hence
* [k
but
*k 1 (sh a nE)
Observe that
Vi* (s1) 1/ (s1) = V/* (81) -/ (81) + -itt (s1) - Vi (81) + -/ (81) -V#* (81) (s1)
VI (81) :il.5t" (01) + / (81) - * (s1)
Define
(En- Pn(En ((h-1) (En -(EA-1)
R-1
(E =
Σ Tish = = m=1
where (E) is defined by Fb.
Key observation Since 86+1 = (f an, En), En) is a mapping of & given F4 and ag. for any (deterministic) policy/action sequence and any 8h, follows from Lemma 2
(sn, on) = PM E -ls,,, ap) - PA (sn+1 E -118,, an)] S (E S 1O (E
which bounds the model estimation error by poliicy/action--ndeeeeeddd error term. This will lead to tighter regret bound than directly bounding the model error
S
(sh. an) s 0lV
C (sh
30

---

Published as a conference paper at ICLR 2026
Furthermore, we will see that the use of Exo-state ÊΛ-1 overcomes the misalignment issue since the sequence gx-1 is always Ft-measurable. Note that C* pk A are all -mmasuurrbl,, then e (.) is also Fk -maasurable.
The failure of using state-action count. Denote by (s metm and (5% MET the sequence generated by (#*; P) and (x*; P) at the n-th episode. In particular,
= - 2t ब (i())) 3 = (f(3), at. Ef), 3h+1 (f(5) aft. Ehi Ch).... Note that (5 a [ is fixed conditional on 5*, its randomness only comes from e". We bound the random regret as
K
K
K
Σ
V
19
S
+ D2
V
V
+
V$a - -.
R-1 1
K
H-1
K
<
Σ
(H - h)
E (c
[i
Σ
(H - h)
E
[c ) Fir
h=1
k=1
A=1
k=1
H-
K
H-1
28t
2St
(H
h)E
(3
Fi
+
Σ
I
C ax)
Fk
where the third inequality is due to Lemma 3 and the last inequality is due to Lemma key is that the visiting count
2 However, the
(s, Σ a() (s.
is defined by F generated by (æt P). Although we can bound the second term via standard proof, we cannot obtain an upper bound on the first term. Specifically,
2S5.
Σ
Σ
I (5t at) = (s, V (+ at)
25t
Ckick, a
k=1
8,8
2Sc
ΣΣ
(3% at) (s,a)} V (s.
1=1
C (3.a)
25
8,0
The last inequality is due to the fact that Ch (s, a) does not increase by 1 if (sh, af)) (8,a) a) since
Ch counts based on Fk or (sf o.).
The solution: bounding via exogenous state count. Using Lemma 3 we can get
K
Σ
Vi
V
Vi
V Vi
-17*
1=1
H-1
K
H-1
K H - h)
< Σ
(H - h))
Σ
[
(
+
(s [F
h=1
k=1
h=1
H-1
K
2
log (H/()
2 H h)
Σ
E
FR
LV
Ch(sh_)
,
A=1
k=
where the expectation in the second line is taken w.r.t. the (5), a NEEM p*
pa* and (s) annnem
Taking expectation on both sides, we can get
E
K
Vi
- v**
2 h=1
> H
H-1
NJE
K
2 (og(K(/8)
< <4H log KH
chick
31

---

Published as a conference paper at ICLR 2026
F.3.2 PROOF VIA MDS SIMULATION LEMMA
Lemma 4 (Simulation lemma, martingale difference). Let (P,r) and M' (P,, r). Fix an arbitrary policy т. Define
25 25
Ch := [IPr(sh,
(sh, (shs))) V Chhs: (sh))
CA : [PAlV Va. [[(s,, (s())) - -V h+1 ((5)+1),
1+1
h+1
where eh is martingale difference sequence w.r.
the filtration Hn.
(s1, (11), ". 1h-1, Th- (Sh-1)). Then
H-1
(s) V (s1)
(si)) S
Σ (ex (H- h))))
Lemma bounds deterministic term by the sum of two random variables.
Proof.
1(51, IV (81) - ViT. (s1) (1 (81)) + ( - ri (s1, - MM (1)))
[[P((V - -V2
+ P1)V, (I),
I [Ri -
+ - P() [1s1,
1V -V,- VV- 1(82) + + [[( [[][[[-P)) PT) (s))
V V22 V/.M (182) (H (H-
1/ M V3 (88)) + + (ff - 2) +el +1 (H 1)
H-1 l
< IV
V.. (88))
n
+
(cn + (H - h)(a))
h=1
#-1
Σ
(en + (H h)en).
1=1
Define
(sh,, ax) ; Pa(sn, an) - (sn, and (,), 2
2St
(sh, (sh, (sh,
(sh, an/m) [PA|VT+ V/ an) VT+1 V (S+41))
where of a martingale difference sequence that depends on ग through Vyke Recall that (ot aeene and (sh, (5,,a)))[m)) are the sequence generated by (#*, P) and (T*, P) at the k-th episode, which satisfy 84 = st = =t. Using Lemma we can get
K
K
Σ
Vi
VT (s1) - -im (81) + VT (s1) - pm (81)
1=1
H-1
K
#-1 K
(5 af|m²) + (H nie (3f
a
Σ
k af
( + (H -
1=1
The key observation is to verify MDS by considering the essential filtration o((E*),) )..) instead of the
full (standard) filtration a ((s at) n. Formally, we define the exogenous filtration (s 2/)
9 = ((s)': - (")me[a-]-- st. (Eh (e((--1))>
32

---

Published as a conference paper at ICLR 2026
which is only generated by the exogenous process. This is different from the full filtration
F = a a((5% a ME(l)) (oh ax We(h--1); s%) For any & and h, recover/simulate (3% a Ias from st nT² and 6h as follows
* = - -1), a t (5 + Sa
which implies that (sh ah gr is measurable w.r.t. gh Furthermore, P is measurable w.r.t. g implies V.ki" is measurable w.r.t G Then
( (= = [Px Vh+t - h+1 [1 ax) 1V741 V (5h+1)
an MDS w.n.. 9% since
I [e axlm=)) |[
E [PhlVTTts
h+I (1 a - IV W+1 (15++1)19% 11%
[PriVT - V [1 a - [PAIVE 1 11(s)) a/)
=0,
where the second equality is due that the only non-measurable variable is b and (5h af [+*= gh since 1 is measurable w.rt. 9h+1
Since * is measurable w.r.t. gh, vre,a and (s ah hes measurable w.r.t. g Then
Te (s a = [PNIVA+ - V/ h+1 [Iss att - I - V ((*
h+1
= [PaalV - V 11(5 att - [Px] [PA|VI
D [1 at)
=0,
and (s **** is measurable w.r.t 9 Thus ( a/)**) also MDS w.r. 9% Using the Azuma-Hoeffiin incquality, obtain w.p. 8'
H-1
(s a/|
OH
KH KH 1/8
We can bound the error terms as
H-1
H-1
K
2 log KH/5)
CH--M
( a. + at) <
Σ H h)
Σ
< 4H2 E 2K log K/8)..
Remark 4. We cannot obtain a bound on the expected regret that is independent of 5 as the full information MAB setting since
V*. max V..M max V.
E[max Va.M) E]
Remark We may obtain a tighter regret bound O (b) by a finer analysis. Remark The simulation lemma MDS leads to a high prob. regret bound, while the simulation lemma expected version leads expected regret bound. They are the same order, but the latter one weaker.
F.4 PROOFS OF IMPOSSIBILITY RESULTS
Definition 4 (Pure-Exploitation Greedy (PEG) after a finite warm-start). Fix an integer (not growing with K). Warm-start: pull each arm exactly L times (in any order), Greedy phase: for all subsequent rounds K AL. play
aj arg max P.a KE(K]
where P.a (k) is the empirical mean of arm a over the learner's own past pulls a. Ties are broken by any deterministic rule that is independent of future rewards.
33

---

Published as a conference paper at ICLR 2026
Lemma 5 (Monotonicity barrier), Consider PEG. Suppose at the start of the greedy phase there exist arms 1. with P:( = and ( > 0. Then PEG never pulls arm again.
Proof. At any time 2 K L,, the empirical mean of arm remains exactly 0 unless is pulled; conversely, any arm with at least one observed success retains an empirical mean > forever, because the count of successes for that arm can never drop to zero. Since PEG selects an arm with maximal empirical mean and (k) 2 (LL) > 0 > ts (k) for all t 2 KL L, arm is never selected.
Theorem (Linear regret for K -armed PEG with L 1). Fix any K 2 2 and any gap A E (0, +l- Consider Bernoulli arms with means
P1 = A
pk 2'
Run PEG with warm-start L 1 (each arm pulled once) and then act greedily. For all T 2 K,
E[Regre((T) 2 (1- A K) = Q(T).
Proof. Let Xa,1 {0,1] the first Bernoulli sample from arm a. Consider the warm-start event
E = {X1,1 0} n {a6e .2....,KK K]: X }
Independence gives
K IIa mb) { (1- 6=2
P(B) = (1-
On E, after the K-round warm-start we have Po (K) = 0 and (at least) one suboptimal arm b with (K) 1. By Lemmaß] PEG never pulls arm again. Hence from round K+1 onward PEG plays a suboptimal arm every round, incurring per-round regret 141 maxa31 j4a = A. Therefore,
Regret(k) 2 AT K) on E, and taking expectations yields the stated lower bound.
Theorem 6 (Linear regret for any fixed warm-start L.). Fix K 2 2, any integer T. > 1 that does not grow with T, and any E (0, 1 Consider the same Bernoulli instance as Theorem PEG run with warm-start size L. and then acts greedily, then for all T 2 KI,
(1- -T -(T-KL) = ((k).
E (Regret(k))
a positive constant independent T
Proof. Let S..L be the number of successes observed from arm during the L warm-start pulls of that arm. Consider
E, = 1 n {abe (2...., St, = 4].
By independence across arms during the warm-start,
= P(SI.L = 0) = (1 - p1)² = ( A) = pb = (2)²
and therefore
P(EL) ( A) ' - (1-(1-2-9*-)
On E,,, after the L--round warm-start we have Li LKL) = 0 and at least one suboptimal arm with (KL) 1. By Lemma PEG never returns arm 1; consequently it plays suboptimal arm in every round / KI, suffering per-round regret A. Taking expectations yields the claimed bound.
Corollary 5 (Any finite exploration budget). Let an algorithm perform any deterministic, data- independent exploration schedule of finite length < oo (not growing with T), after which always selects an with maximal current empirical mean (deterministic tie- neebbreaknng independent of future rewards). Then there exists a Bernoulli K- aarmed instance on which the algorithm has E, RegRett [k)] = ((k).
34

---

Published as a conference paper at ICLR 2026
Proof. Map the schedule some La 2 pulls per arm during the exploration phase, with and define the event that the optimal arm produces only
Ee La = N. Choose means as in Theorem aadd zeros in its L1 pulls while at least suboptimal arm produces only ones in its La pulls. This event has strictly positive probability [[-factor bounded away from 0 (independent of T). Conditioned on this event, the post-exploration empirical means create strict separation (optimal arm 0, suboptimal arm at 1), and Lemma applies verbatim to force perpetual suboptimal play thereafter, yielding linear regret in T'
Remark 7 (Beyond Bernoulli, bounded rewards). The same conclusion holds for any rewards supported on (0, 1] when there exists gap A = /¹¹ maxasa" > O. By Hoeffding's 's inequality, for any fixed I. there are constants Pı, > 0 (depending on T. and the arm means) such that with probability at least P1 the optimal arm's warm start average is S ju* & and with probability least P2 some suboptimal arm's 's warm-start average is 2 μ A. The intersection has constant probability P1p2 0, producing strict empirical mean misranking after the warm-start and thus linear regret by
Lemma 5
G PROOFS OF REGRET BOUNDS IN SECTION 5
G. PROOF OF THEOREM 2
Define (T) = (V Vi (s))) We have
(T) = (V - (s = (V/ - (2 1
-r(at tT, eh V (1 (2 T). 2 - =h- Vo ()
(6 x) (wh R: (ch-
wT (sh-)))
=: =:((tttT)) _ (w (Sh-1) w (Sh-1))
= =(att ) TTh T (v
R.m (ch_ - ()))))))
where
ki
(ch Σ Ph(chish - +o(lo TT))))))(, k. (Eh)
ch
Σ Ph 1) [r(oR
Tw (E:))
ck
Vi Σ
Pa ((
ch
Ph Ph [r( (n)
ek
Note that we denote 2/"" == (2 ((... (h-1)) which implicitly depends on ch and 2 (n) = (n))(n), { which implicitly depends on Et. We have ((())
p(x K: tT (V
v% ((h-)))
= (sa T InT Σ (n))())
(PP
+ 26a
k. T
Eー Σ (x)((n))
Σ
1 (m),
K. (sh) - (n), x)) wh (Eth)
w
35

---

Published as a conference paper at ICLR 2026
Under Assumption
we have
k. (5h-1) = En dn
(E (rrctist-)(((oooO((... (l) ( +(( k. (ch)
Wh
c
E P r 1) + Ih
Σ on (k)
Sh.
T 1) + I Σ (k))on T
Σ DAM wi (
SR
ME + Σ PAMCEEEEEDMMMM w (5h)
si.
1 + [PX
Similarly, get
w// (5h (P [P(((MA) (O (F
Thus
W " wx = En 1 PA)r((Eh-1) + ( -PP(()))) Tw TRA
-En'on((P,, Pr)r)((h-1)) + [(Ph - PA)((M)) T BiT
MEEAICE [PA((MR) (w wh+t)))
-E - Pr)t)((h-1) + [(P) - PN)((MH) T NiT (
+IPh((NTF) (w - - (TM)) (w - + (MT - -(5))
R.T =T)( + (T) (M)) (w (Et))
where we define
(T) = [Po((M))
- T (w Ko (T) = Dn Pa)r)(sh-1) 1(P - -PO((MR)) (OC(MM)TTHHTT "h 11)
-(++)))( (EM) (w 2(hh)
Lemma 6. Let {o IRd, and define
K
ri E Radd
which is assumed to be full rank. For E, E R and u Rd, set
== == (c C
(0 Øæl Rdd
Then the following bound holds:
T A
I ||ulla ||e||2
1=1
where ||u]|A- = Vu VuTA- A-
Proof. Observe that
u T -1 Σ dcc; u UT -1pp.
Let A A-1/2 denote the symmetric square root of A- and define
B:= -1/2 E kd
Then
u A-1 (A-1/2 T (A- (A-1/20)e (A11/22)) Be.
36

---

Published as a conference paper at ICLR 2026
Note that
BBT --11/2pp 10-4TTAA10 A-1 A-1/2AA AA-1/2 Ld-
hence |B|| = 1. By the Cauchy-Schwarz Schwarz inequality.
([A-1/2u) T Be - 1A-1/22lp Bell2 s ||A-1//2|] 2//2/
Finally, ||A-1//ul|2 Vu -u ||u|| ^ 1, proving the claim.
We obtain the recursion for (T) wh k,
w
d (T) (T)) + ( (MT T di+1
Σ (C)(m) +c(
M=k
H
Σ (T) + (T). s=h
Note that ex is an vector-valued MDS w.r.t. g since
(w k. wo 1 0. (T) IE [IPA((ME) (w wT 1) (EM) (ecG)))(())
Since Mn (Eh) are bh meeasuuureble for h h 1, we have
E (x)(())) = E
III M=1
(II Mc)
TE [ch19]] = 0.
#=1
Thus (Tr) is also vector-valued MDS w.r.t. g
Note that ob is full rank, so d(x²) can be represented as d(x)) = tb for some E RRK Under Assumption we can prove the following lemma.
Lemma 7. For any (n, t, n, xx,g), {),, it holds that V, ,i .0 (x", ,)) 2 Vi (x"
We have
K
Regret K)
Σ
VT (sf) - V/at v/*((s8t)
k=1
K
(vT" -v(t (sf) + (vtir - -Vxtt* (st) + (yleat - v7x)) (st)
VTT' - -vit (st) (u - vIrt) (of)
K
Σ
((01.10) T 84t (7** + ((ztta) , Tof (**
k=
K H-1
$l ((tha(())TT))))) ( + a( (2t( (e + (x*)))
Note that for any -e.meauurabe policy म. the sequence (a (T) an MDS w.r.t. S Moreover,
((ot()TT((7) < 4vd.
37

---

Published as a conference paper at ICLR 2026
Next, we bound
II Mg ) 2h
W==
h-1
II
(C )o(at())))
Sn Dn - -PDD + +(PP
-PO((M)) w (ONCM)TTRFDCCCC ((FD)))H-))
h-11
M (o(1)
2h 1 - P
(ch (0(2)10)
I(PA - PP)((M))) wwfftMl(ch-)
h-1
T
II W=
(Ch )6(=711)
2n 1 - 1
+
(PA - Ph)
II
whil
kit
(sh-1).
W==
We can bound the first term as
(g )0(27
In f I(Ph P.)r((sh- = 10 T Enn -5-1 I - -r,rr
( - -Ph)rrl
1
VN
(PA (c))
The second term can be bounded as
(Ph Pw) (Ii
h
MR (CCo0aii )
wh+1 (sh-
W==1
< | Ph) |>]
II (E (5)
max &
$ || - (e)(c--i) -DDSs->>/
h II
ME )o(atig
|
h II W==
< 1 - Ph)(sh->)l) -I
M (
|
k.g
RiT Wx+1
s ||P PA)
II W-=1 hr II W=1
MR (Ek.))
Vd
< 1 - PADCER-DD/,
Vd
< vd (PA - Ph)
38

---

Published as a conference paper at ICLR 2026
where the last inequality is due to the fact that sup,,g. (M 1. We can bound the regret
K H-1
Regret K)
Σ
+ + o(a (T (+* (x*²))
K H
< 50 dK 20lvakHlow log 1/0')
M MM k.
VN ( -Ph)(hh
h=1
-
El
50(VdKHlog 1/8") + Σ (v N/A0 Va E
dKH log 1/8") + Σ (NN/A Va
<
G.2 PROOF OF THEOREM K
Recall that
(T) (( T (w (a - w/ (1h
= ((thii) (x(()) = o(2,;²)) ( (Eh) (T))
= (T
T Mn - PP)tt + [1P) - PN)((MH) T Ait ((f)))))h-)))
+ = T P)(((M) T (w R. w ())(-))))))) - (ME((E)) (o
(whif - w
+ + ) (ME)))))) (wh+1 (E6)
= = Enh Tn [(P) - (()r)( .) + TT TT E (PP PPO((MF)T P (ssh + +PPN(0(xhiTt) T (w - -(++)))
- (w RT (Eh) + )(a (m ((th
(t) + (T) + (T))
where we used Mg (ch) ((a)() R.T)) = ((ab)t)) kit under Assumption Oj since
Note that (T) is an MDS w.r.t.
E (T) -E [PP (w wT wD - Tw ( 0.
In addition, the following holds almost surely
(+) [Pa(O(u K.t J (w K.T - www w1+1)))(ch_)) (( (w KT
wT (a eh)
1PP -V V= (V/+11 V.RT (1/771 st)
5 2( - 1-h).
39

---

Published as a conference paper at ICLR 2026
We can bound et (TT) as
(T) (xx%//))))) ) "
Mx ) "
1 [P P. - + - T
o(xh11) 12 Dnl(PE - PAIT((EH-)) + [(2) PN) di (
S | (i))
||ICPA - -PDr((SH-)) )| + [P - PAI 1/1 (11 -h)
< | 1
VN ||CPA - ) || + || - PN) -il, (H -h)
|P - Ph)(sh->)/
||1 | (V oo
+11 -h)
VN (
k.
+
H H-11 h
C₁ 1
Unrolling the recursion of (T), we have
H-1 (T) = E + (T))
Lemma 8. For any (n, E, n, x=; :),, it holds that V/
Vi aa (x 2 Vi (x".))
Proof. The proof follows from induction. Observe that holds when HH 1. For any (a E). using the definition of nh, we have
Vil vk (z" {)- = )(x²) T "un
A. (E)
(I xxx9)T T
whe Ko + (I)E))
)(x0)) "En 1 [P) (t) + 1
)(x0) TE 4p r(() + 1
2 )(2)) T 2n 2b (E) + wka la (xx,
Now we bound the regret
K
Regret( K)= =
VTT (sf) - V/*1 v/+(()t))
K
(VT' - -v(lr**) (of) + (vrea - v/barrt (of)
(07) + (yrrnt - -1s0t) (of)
K
(VF' -val:=)) ) (st) + ( (st)
- v7²)
K
-0())) + -8((m7))
(c(((m)) (T())) + + (m + (
H-1
K
2 log (KH/5) (h()
$ /KHlog 1/81+ +2
Σ
VN | )
+ H h
h=1
< OH / KH 1/8) + 2 + H
11 log KH
40

---

Published as a conference paper at ICLR 2026
G.3 PROOF OF THEOREM
4
We start with two simple geometric and statistical facts.
Lemma (Anchor LS predictor stability). For any t, E, any anchor vectors y, u E RK and any x",
[o(=)) " Pn 2) Σ >p 1/2 2/1/ by u1l2.
Proof. By Cauchy-Schwarz, 0 A 4 u) I 1101|2 ||- ll - ull2. Since || S 1 and
| 01| = mmin ( (+) = X5 the claim follows.
Lemma 10 (Row-wise empirical transition concentration). Fix t and &. Let g E +
[0. H and suppose (- (- {) is the empirical distribution from n (E) 2 1 iidd. samples of g drawn from E)) (across episodes). Then for any E (0,
Pr (11PP' -P)gl PP(ss S H
12/(2/82 2m
2 1-
Proof. (Pn-P)9 1 Hoeffding's inequality.
m 1= Zi E[2z]] where Z₃ == g E [0, H with E P(- (E) i... Apply
The concentration will be lifted to uniform (over n, i, E events via union bound and the standard summation (m + 1)-1/2 < M.M.
1/2
Proof. We follow a the one-step decomposition as in the proof of Theorem carefully adding the misspecification term.
Fix any reference policy æ (we will take ı x at the end). Let s = (ar (t) be the state visited in episode n by the coupling argument used in LSVI analyses (or simply the realized trajectory under the deployed policy at episode n). Denote the value error
(T) = (V k.a ViT (sh)
where Vk, is the value when Bellman backups use pn and parameters w., while V uses the true model and the ideal parameters w. that linearly represent the values of π as well as possible (defined below).
Let (E) V and og (5) R. be the anchor target vectors under (empirical) greedy backup and (true) n-backup,, respectively:
1 A. (E)(,, = Σ (e)((1()) (M (( (m,, E))) wh++=(E))
[VT())) Σ P(E'lE) [F( ( x, + a5 (2n (m) m)) wT wTt
The LS predictor at 2h a.k
(a x/) is " b (.). Hence
(5 (. T 1 (1 (5%_1) u (EP-)) (T)
Write, with ght1 Ro
(n, = r(-) 0(-)T " (E') and gh+1 defined analogously with w
un 1/j (p P) gh + Pl 9h+2)
(A) transition erroe
(B) propugation
misspecification
where 1o == 17j u and uj is the anchor vector of
W E arg min sup (upl(T (T"VAL)) (2=, ,()) - W(x (c.))))) WEF, za
By Definition 3 11 EBE-
41

---

Published as a conference paper at ICLR 2026
Apply Lemma equation G.3
(()( - 2o= 1/2 ()(pm - P1
+ P 9h+1) || + 11
12
S 0 1/2 ( p) p. +1
1/2
P)
+
|h++1 k.
gh+1 + VN EBE
since P is a contraction in & and rewards/values are in [0, H] so g E [0, H] coordinate-wise.
Fix f, Lemma 10 with union bound over & - k,t H. 5 E yields with probability 1 - --/2 that
log (2H
k.r ||
LIVE
2 2
uniformly. Summing these martingale-Iie increments along the sample path and using Σ Σj=[(n 1)-1/2 < 2MM gives the contribution
C2 E H log
HKE 8
stage, which after accounting for the LS geometry (the Ej tb factor) and the greedy-vs-policy coupling yields
C
N
K log
HK
Here the H² and H /N/Ao arise from H -tet propagationn/ellscooing and the LS projection norm as in standard LSVI analyses; constants are absorbed.
The term || gh+11 - g || is linear in | Vi hence in [ Unfolding over t = 1...., and using Seeeddman/Bersttinn..e type arguments for the resulting martingale differences (and rewards bounded by 1) gives
C H K log
By Lemma 9 and
10% I VN NEB:
[6(5%
o.
4n p7
S Ao
1/2
VN
EBE.
Summing over 1,..., H gives H\
1/2 /N EBE per episode. The standard comparison of R.. with n² doubles this constant but stays of the same order; summing over 1...., K yields
H
C3
K
EBE.
VĀO
Combining (6)-(6 with union bound over the high probabitbbbylitty events gives the claimed inequality with probability at least -. 8.
H DETAILED NUMERICAL EXPERIMENTS
H.1
TABULAR MDP
We conduct numerical experiments using tabular Exo-MDPs, and display the model estimation error over episodes and the regret comparison of PTC, PTO-Opt and -e in Figure 3 We provide the implementation details below.
Model estimation. PTO or LSVI-PE estimates the model (r( v) from past episodes (counts per time-step) and solves backward DP using Pt.
Optimistic model.
At each Bellman backup the PTO PTO-Opt solves max Stonss Qv/)V(())) by mass transfer to obtain optimistic expectation.
Policy evaluation. All algorithms are evaluated by exact backward induction on the true P, to obtain stage-1 value functions V(,,,
42

---

Published as a conference paper at ICLR 2026
Regret and model error. Per episode and report cumulative regret E (averaged across runs). Model error is measured by the average Frobenius norm + E. Il.: Pyl.
instantaneous regret Σz,8 (V
g
Baseline methods. We compare the PTO to PTO-Opt (Section D.3.2 that solves constrained 41 subproblem for optimistic model with confidence radius bonus cV lol /O.00.0)//N,, (default 0.3). We also implement three PIO-Lite baselines with subsampling ratios of 0.2, 0.5, and 0.8 for comparison, serving as the natural intermediate points between PEL algorithms and exploration-heavy methods. Instead of constructing the full empirical exogenous model from all episodes, Lite subsamples the historical exogenous transitions at each stage. The resulting subsampled dataset is used compute lightweight estimate, reducing computation while keeping the model statistically representative.
Model Estimation Error Episodes
Curnulative Regret Comparison
1.4
350
PT0
PTO-Opt
Model Estimation, Error
Cumulative Regret
PTO-LIte-0.2
250
PTO-LIte-D.8
0.0-
200
150
50-
0.2
0.0
30
100
159
200
250
50
100
150
200
Episodes
Episodes
Figure 3: Comparison of PTO, PT0-Opt and
H.2 STORAGE CONTROL
We display the model estimation
episodes and the regret comparison between LSVI-PE and LSVI-OPi in Figure 4 across three Exo-MDPs with different horizon lengths. Across H E {6, 8, 10), LSVI-PE consistently outperforms LSVI-Opt in cumulative regret.
We also analyze three expanded Exo-MDPs with state/action spaces scaled and planning horizons increased, and the results are presented in Figure LSt and three LSVI-LI te variants are implemented as baselines. Across all these enlarged benchmarks, LSVI-P -EE maintains the best overall performance, and Lite achieves performance close LSVI-PE validating that PEL remains effective even under aggressive subsampling of exogenous traces.
We provide the pseudo-code of LSVI-PE for storage control in Algorithm
Baseline method. LSVI-OPe differs from LSVI-PE in Line 12 of Algorithm 2 LSVI Opt computes the optimistic target
Specifically,
(k( CE'E' d'E(- Pm---mas (lmaoe]
{ (Ml(p. + (f w (E')
max
EEE
where PA is the optimistic model obtained by solving the & constrained subproblem around j% with confidence radius bonus 2Y log(KY/0.01)/N.,, (default e= 0.5).
Detailed setup for Case I. We numerically analyze storage control problem with continuous endogenous state space X' [o, C). discrete exogenous state space E [Y). and continuous action space A amazz amaa]. X' discretized by N anchors. The default parameters are C. 10, Y 10, amaz 2, N 10. and K 100 epsiodes. Three time horizon lengths H (6,8, 8, 10) are evaluated for comparison. The exogenous variable is the discrete power price with the following transition rules applied: 70 % probability exists of either remaining in the original state or transitioning to an adjacent state, with the remaining 30 % assigned to uniform selection among all feasible states.
43

---

Published as a conference paper at ICLR 2026
Detailed setup for Case II. We analyze three expanded storage control problem cases, where both the state spaces and planning horizons are scaled by factors of 2x to 4x relative to the original settings. To observe the long-term performance and convergence characteristics of each algorithm, the number of running episodes to 200). The subsample factors of the three Lite haselines are 0.2, 0.5, and 0.8, respectively. All other experimental configurations remain consistent with Case I.
increase
Computational efficiency. The major computational overhead of Algorithm is to solve the optimal action for given state sy, each time-step h
* (
a, + (f"()) " ($))
max Amax Ranax]
"E
We emphasize this step computationally efficient via anchor enumeration due to the LP structure of the subproblem.
Estimation Enorrs sodess
Enoorss Episedes
Estimation Spisodes
Mooe patmennt Enge
Epiedds Cumddative Bagret
Epicodes Cumulative Ragret
Epicods Cumclativn Regret
LEVIEE
LEVIE
00.2
06.0
Cura Mihe Reg
Cimcable
Cume
Eplcdds
Epicdes
Specdes
(a) H 6
(b) H 8
(c) H 10
Figure 4: Comparison of LSVI and LSVI-Opt across three different time horizon lengths in Case
Mozel Eptmation Erro Episades
Model Estimation Eror vs Eploodes
Model Estination Errrr us Ediodes
Mrrge Edvegdnn
Epaodes
Eppodes
5355005
Rogret
Regret
Rogret
LSV
12V PG
LSV 2K
LoV iiG-iii Lo 3-5
LOV PEA
LOV A0-- LoC 3.
2i6--inn. 2.4
Camuuatte 100
Comuuative
208
30.0
Euoodas
Essodas
Euoodas
(a) H 20,
20, 20
(b) 17 = 30, 30,
(c) H 40, = 40, N 40
Figure 5: Comparison of LSVI-PE, LSVI-Opt and LSVI-PE-LiE under three different experi-
mental scales Case II.
44

---

Published as a conference paper at ICLR 2026
Algorithm 2 LSVI-PE for storage control
Require: Horizon H; capacity C; anchors Pr. -ー1 C, n 1...N; hat features [0, +R
with p(p.) 6n
Require: Action set A I-a amax]; efficiencies 1) 17 > O; leakage a E (0,
Require: Reward r(s, a, {) = Ça ac/al |a| Sn.:; post-decision f"(s,a) = clip s + 17 1 a 0, C); pre-decision update g(s ass
Require: Price codebook = = { CRI; dataset of k price trajectories ( 1m with 4 E
1:
Update P/ {):; for each (),
E. N >0
P (8) =
E.
otherwise (unvisited row)
n2:
where - 1sh = E, ch+ = E'}.
2: Backward Value Iteration:
3: for h = H down to do
4: for each { E do
5:
I/ Design at post-decision anchors (identity under hat basis) 4 IK, ag 1K
6:
2n + (o(p)),.. ....) {(n)): on + 2, 2/ (E) + R
7:
8:
for to N do
9:
h = H then
10:
(n) 0
11:
else
12:
(n)
{)
max a'El ael-ammoee.e Renax
(ro(pm.5):ddee))
C'EE
(f a')) w
13:
// Inner max is 1-D LP (piecewise linear); solve via breakpoint enumeration
14:
end
15:
(E)(E) < (E) + d(p)) vk(n)
I| writes v (n) into entry k
16:
end for
17:
(E) + En (E(
I1 with En IN: wx((5) 1of (1).....v/ (N))
18:
end for
19: end for
20: Output:
21: V (xx {) = o(x²) (w)(())
for all (s
22: return F
h.
45

---

Published as a conference paper at ICLR 2026
1 DECLARATION OF THE USE OF LARGE LANGUAGE MODELS
We used large language models (LLMs) to assist in proofreading and improving the language, grammar, and clarity of this manuscript. The authors retain full responsibility for all intellectual content, results, and claims presented in this paper.
46


Reviews:
[{"review_id": "aaHvfKsQkY", "reviewer": "Reviewer_odvK", "summary": "The authors propose a pure exploration learning framework in Exo-MDPs, where the state decomposes into exogenous and endogenous components. Starting from a simple Exo-Bandit warm-up, they show that in tabular Exo-MDPs, one can estimate the exogenous transition kernel and computed the policy via dynamic programming, deriving a theoretical regret bound. For linear function approximation, they introduce an algorithm called LSVI-PE, which combines post-decision state and counterfactual trajectory analysis, and provide a corresponding theoretical analysis.", "questions": "Given the relatively small experimental scale—in terms of state/action set sizes, horizon length, and the number of episodes—and that the baseline is limited to an optimism-augmented variant, would it be feasible to scale up the experiments and include additional baselines, particularly other pure-exploitation methods?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "They present the first near-optimal regret bound for Exo-MDPs under linear function approximation and theoretically establish that it is independent of the endogenous state and action cardinalities. Furthermore, they rigorously prove that the exogenous process in EXO-MDPs evolves independently of the policy, thereby removing the need for explicit exploration. This is supported by $\\tilde{\\mathcal{O}} (\\sqrt{K})$ regret guarantees in both tabular and linear function approximation settings.", "weaknesses": "1. The modelling assumptions are somewhat restrictive, as the theoretical results rely on the exogenous state space being discrete and on the endogenous transition and reward functions being known.\n2. The regret bound scales linearly with $|\\Xi|$ in both the tabular and linear function approximation settings, which may limit scalability. In particular, LSVI-PE can exhibit degraded performance when the anchor placement is suboptimal and $\\lambda_0$ becomes small.", "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": "fyn6kjX4FE", "reviewer": "Reviewer_4nVr", "summary": "The paper makes a contribution to the reinforcement learning literature attempting to characterize when greedy policies are sufficient for provable guarantees, or when exploration is not necessary. The authors show that this is indeed the case for exogenous MDPs, where there is an exogenous Markovian component that is unaffected by the learner's actions. Their variant of LSVI achieving sublinear regret crucially hinges on an assumption that the endogenous transitions are deterministic and known, as well as three technical assumptions on an anchor set that is closed under the Bellman operator with non-negative residuals. A tabular method only requires the former.", "questions": "1. How much of this relies on the assumption of known deterministic endogenous dynamics?\n2. Can the anchor set assumption be weakened? What could replace it?\n3. Where is the counterfactual analysis?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper makes a solid contribution to the RL literature. Understanding exactly when greedy exploitation is sufficient for provable guarantees is a topic that has gotten more attention lately. \n- This tends to occur when there is sufficient environment noise, and Exo-MDPs appear to be one such case. To my knowledge, this is novel.\n- The authors tackle bandits and both tabular and linear MDPs, showing that this holds somewhat more broadly than just in an isolated case. \n- The paper is largely well written, save for a few issues on clarity.", "weaknesses": "1. Not much intuition is provided on exactly why such a positive result is possible. At a very very high level that probably amounts to skimming over a lot of subtleties, it seems to be because the learner can decouple the exogenous transitions, of which no exploration is necessary to learn them, from the endogenous transitions, whom are deterministic and known. Assuming that one can do so, the whole problem then reduces to learning the exogenous transitions for input to learning a Q-function via the standard LSVI procedure.\n2. The assumptions are quire strong. Needing the existence of an anchor set that is known to the learner, plus additional assumptions on said set, is quite strong in the RL literature (I am reading this as its alternate name, a coreset). It is understandable that strong assumptions are necessary, but one could also (for instance) assume that the minimum eigenvalue of the design matrix is bounded under any policy. Characterizing exactly why this is needed, how it can be obtained (it is folklore that Frank-Wolfe-like procedures get you one, but it should be stated), and the relevant intuition would go a long way towards helping the unfamiliar reader and justifying these assumptions.\n3. The proofs in the appendix, especially for the linear MDP section, are quite poorly written. The authors state that they make a counterfactual analysis. It is unclear to me where this is done, or what exactly this means. This is striking -- I've seen the linear MDP proofs many, many times, but it's not clear to me where it happens.", "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": "ndbSeEMVrI", "reviewer": "Reviewer_8gd3", "summary": "This paper studies exogenous MDPs where the noise in the transitions is independent on the action taken by the learner.\nUnder this setting the authors show that no exploration mechanism is needed in Bandits Problem and Tabular MDPs where the transition dynamic is known.\nMoreover, the result is extended to the linear case.", "questions": "1) How is the initial exogenous state chosen? Is it sampled from a fixed distribution, or can it be chosen adversarially?\n\n2) If the transition dynamics (the $f$) in tabular MDPs were not known, would pure exploitation still suffice?\n\n3) In the tabular guarantees, there is no dependence in the number of endogenous states and actions ($S$ and $A$). However, the feature dimension $d$ shows up in Theorem 2? If I represent a tabular MDP by choosing the features that are one one-hot encoded vector of dimension $d = SA$, I would get a dependence on $\\sqrt{SA}$  if I apply your Theorem 2 in this setting, while Theorem 1 avoids this dependence.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "I think that the question tackled here is interesting, as several problems of practical interest are usually solved by algorithms that do not use any exploration mechanism.", "weaknesses": "I think that the assumption about the existence of the anchor set is not strong; however, I do think that it is a strong assumption that the learning algorithm knows this set.\nWhy is it not possible to guarantee the invertibility of $\\Sigma$ by defining $\\Sigma = \\sum^N_{n=1} \\phi_n \\phi_n^T + \\beta I$ where $\\beta$ is a small scalar and $I$ is the identity matrix ? In this way, switching from Least Square to Ridge regression it should be possible to avoid the assumption.\n\nWhy do you use the anchor points to define the matrix $\\Sigma$ instead of using the data collected during the policy rollout phase? It seems weird to me that the rollout phase only uses the encountered exogenous states to estimate the exogenous to exogenous transition matrix. In contrast, the encountered states and actions are discarded.", "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": "yUiZ8XP3QK", "reviewer": "Reviewer_4oif", "summary": "The paper shows that pure exploration—model estimation with greedy action execution—is sufficient for rate-optimal regret in exogenous MDPs when the exogenous process is the only unknown. The paper covers both the tabular MDP case and the case of MDPs with linear function approximation. In both cases, they show a regret of order $O(\\sqrt{K})$.", "questions": "- Could you provide some intuition as to why pure exploration is sufficient to achieve rate-optimal regret in this setting? Is it because the endogenous process is fully known, and the exogenous process is independent of the actions, so that it can be learned at a \"fast\" rate (approximately $1/\\sqrt{K}$) without impacting the regret too much?\n- In the linear function approximation setting, could you comment on how the regret depends on the problem parameters (such as d, anchor points, etc.)? Is this dependence optimal, or could it be improved?\n- The assumption that anchor points are known seems strong. Could you comment on this assumption? Is it possible to relax it?\n\nOverall, I think the paper provides interesting and novel results on exogenous MDPs, even though the setting is quite specific.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and easy to follow. Overall, the authors do a good job of providing intuition about the results and explaining why the algorithm works.\n- I am not up to date with the literature on exogenous MDPs, but from what I can gather, the results seem novel and interesting (I did not have time to check all the proofs).", "weaknesses": "- The main weakness of the paper is that the setting is quite specific. In particular, the assumption that the only unknown component is the exogenous process seems quite strong to me. The authors justify this choice as being common in the literature, but I do not have enough knowledge of the literature to judge this claim. However, I can understand that in certain operational research applications, this assumption might be reasonable.", "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)