An Improved Model-free Decision-estimation Coefficient with Applications in Adversarial MDPs
Authors: Haolin Liu
Chen-Yu Wei
Julian Zimmert
Venue: ICLR 2026 Poster (2026)
Keywords: decision making
reinforcement learning
online learning
Primary area: learning theory

Abstract: We study decision making with structured observation (DMSO). The complexity
for DMSO has been characterized by a series of work [ FKQR21 , CMB22 , FGH23 ].
Still, there is a gap between known regret upper and lower bounds: current upper
bounds incur a model estimation error that scales with the size of the model class.
The work of [FGQ+23 ] made an initial attempt to reduce the estimation error to
only scale with the size of the value function set, resulting in the complexity called
optimistic decision-estimation coefficient (optimistic DEC). Yet, their approach
relies on the optimism principle to drive exploration, which deviates from the
general idea of DEC that drives exploration only through information gain.

In this work, we introduce an improved model-free DEC, called Dig-DEC, that
removes the optimism mechanism in [FGQ+23 ], making it more aligned with
existing model-based DEC. Dig-DEC is always upper bounded by optimistic DEC,
and could be significantly smaller in special cases. Importantly, the removal of
optimism allows it to seamlessly handle adversarial environments, while it was
unclear how to achieve it within the optimistic DEC framework. By applying
Dig-DEC to hybrid MDPs where the transition is stochastic but the reward is
adversarial, we provide the first model-free regret bounds in hybrid MDPs with
bandit feedback in multiple settings: bilinear classes, Bellman-complete MDPs
with bounded Bellman-eluder dimension or coverability, resolving the main open
problem left by [LWZ25].

We also improve online function-estimation procedure used in model-free learning:
For average estimation error minimization, we improve the estimator to achieve
better concentration. This improves the  $T^{\frac{3}{4}}$ and  $T^{\frac{5}{6}}$ regret of [FGQ+23 ] to $T^{\frac{2}{3}}$and
 $T^{\frac{7}{9}}$ in the cases with on-policy and off-policy exploration. For squared estimation
error minimization in Bellman-complete MDPs, we redesign the two-timescale
procedure in [ AZ22 , FGQ+23], achieving $\sqrt{T}$ regret that improves over the  $T^{\frac{2}{3}}$
regret by [ FGQ+23 ]. This is the first time the performance of a DEC-based
approach for Bellman-complete MDPs matches that of optimism-based approaches
[JLM21, XFB+23].

Published as a conference paper at ICLR 2026
AN IMPROVED MODEL-FREE DECISION-ESTIMATIOO COEFFICIENT WITH APPLICATIONS IN ADVERSARIAL MDPS
Haolin Liu'; Chen-Yu Wei', Julian Zimmert
University of Virginia, Google Research
(srs8rh, chenyu. wei @vi Revirging iiginiii a. edu, z zimmert@googler com
ABSTRACT
We study decision making with structured observation (DMSO). Previous work [FKQR21, FGH23] has characterized the complexity of DMSO via the decision- estimation coefficient (DEC), but left gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, [FGQ introduced optimistic DEC, achieving bound that scales only with the size of the malue-function class. However, their optimism- bbased exploration is only known handle the stochastic setting, and it remains unclear whether it extends the adversarial setting.
We introduce Dig-DEC, model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than opti- mistic DEC and can be much smaller in special cases. Importantly, the removal optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under linear reward and several general transition structures, resolving the main open problem left by [LWZ25].
We also improve the online -estimatistt procedure in model-free learning: For average estimation error minimization, we refine [FGQ* 23 estimator to achieve sharper concentration, improving their regret bounds from T to 7 (on- policy) and from & to T (off-policy). For squared error minimization in Bellman- complete MDPs, we redesign their two-timescale procedure, improving the regret bound from T to VT. This the first time a DEC-based method achieves performance matching that of optimism-bar based approaches [JLM21, XFB 23] in Bellman-complete MDPs.
INTRODUCTION
[FKQR21, FGH23] developed the framework of decision--stimaaton estimation coefficient (DEC) that character- izes the complexity of general online decision making problems and provides general algorithmic principle called Estimation-to-Deciise
(E2D). In the state-of-the-art result by [FGH23), regret lower and upper bounds are established with gap of log J.]. where M the model class where the underlying true model lies. This log [ reflects the price of model estimation. Essentially, the exploration, while the
lower bound in [FGH23] only captures the complexity of poecision-makinn upper bound additionally includes the complexity of model estimation. Since E2D is model-based algorithm that learns over models, it necessarily incurs this cost of model estimation.
On the other hand, large class of existing reinforcement learning (RL) algorithms are model-free value-based algorithms, which only estimate value functions. better capture the decision-makin complexity in this case, [FGQ+23] proposed a variant of F2D, called optimistic E2D), that achieves a regret upper bound characeterized by the complexity measure called optimistic DEC. However, unlike the model-based DEC/E2D framework [FKQR21, FGH23] which drives exploration only
Alphahetical order

---

Published as a conference paper at ICLR 2026
through information gain, optimistic DEC/E2D leverages the optimism principle drive exploration, which may not be fundamental and could lead to sub-optimal performance in certain cases. Overall, the precise tradcoff between model estimation complexity and decision-mann making complexity, along with the gap between upper and lower bounds, remain largely unsolved.
A parallel line of reserach seeks to relax the assumption that the environment remains stationary. [FRSS22] and [XZ23] studied the pure adversarial setting where the environment can choose a different model in every round. In this case, their algorithms only estimate the optimal policy and the price of estimation becomes log II] where II is the policy class. In such pure adversarial environment, however, the pocision-makinge complexity could become prohibitively high and is often vacuous in Markov decision processes (MDPs). A simpler and more tractable setting is the that of hybrid MDPs where the transition is stochastic but the reward is adversarial. This setting has been studied in various settings: tabular MDPs INGSA13, RM19, +0,,+20, SERM20J, linear (mixture) MDPs [LWL221, DLW723, SKM23, LW724, KZWL.23, L.Z224), and low-rank MDPs IZYW+24, LMWZ24]. The work of [LWZ25] first leveraged the DEC framework to obtain results for bilinear classes, However, they only gave a model-based algorithm (incurring large estimation error) and model-free algorithm that requires full-information reward feedback, leaving the model- free bandit case open.
We provide unified framework that advances both directions discussed above:
In the stochastic setting, we introduce new model-free DEC notion, Dig-DEC, that improves over the optimistic DEC of [FGQ 23]. Our approach does not rely on the optimism principle, but ad- heres more closely the general idea of DEC that drives exploration purely with information gain. For canonical settings such as bilinear classes or Bellman-compler MDPs with bounded Bellman eluder dimension or coverability, we recover their complexities with improved d'depeeneence in
the regret, while in some constructed settings, the improvement can be arbitrarily large.
We establish the first sublinear regret for model-free learning in hybrid bilinear classes and Bellman- complete coverable MDPs with lincar reward and bandit feedback, resolving the open question in [LWZ25].
We improve the online function estimation procedure both in the case of average estimation error and squared estimation error. This allows us to improve the T /T regret of [FGQ+23] 23] to T / in the former case, and improve the T regret of [FGQ+23] to vT in the latter case. The techniques we use to achieve them could be of independent interest.
Tables that compare our results with previous ones are provided in Appendix A. Notably, our framework generalizes the Algorithmic Information Ratio (AIR) framework of [XZ23] and [LWZ25], substantially simplifying the analysis while enhaneing algorithmic flexibility (Section 4). This generalization may facilitate future development in this line of research.
We remark that, similar [FGQ*23] 23), the term "model-free" learning in work does not mean that the learner has no access to the model class M or has computational constraints. Instead, it only means that the regret bound is independent of the size of the model set M. This implicitly restricts the learner from making fine-grained estimation over M.
2 PRELIMINARY
We consider Decision Making with Structured Observations (DMSO) [FKQR21]. Let M be a model space, II a policy space, O an observation space, and V a value function. For simplicity, we [II] is finite. Each model M E M is mapping from policy space II to distribution over observations (O). Every model M e M is associated with a value function VM II + [0, 1] that specifies the expected payoff of policy æ E II in model M. We denote aM = arrmax (T).
The learner interacts with the environment for T rounds. In each round t = 1,..., the environment first chooses model M, E M without revealing it to the learner. Then the learner selects a policy Te E II, and observes an observation o ~ Me)- The regret with respect to policy n: E II is
T
Reg(m*) = Σ (TM((*)) - (T,()))))
2

---

Published as a conference paper at ICLR 2026
Markov Decision Process A Markov decision process is defined by tuple (S, $1). where is the state space, A is the action space, P S x A + (SS) is the transition kemel, R. S x A + A(OO, 1)) is the reward distribution (with abuse of notation, to denote the expected reward R(8,0 a) E [0, 1). H the horizon, and 81 the initial state. Assume s = - Sn with S; n nj 0 for A j. and Si {a1}. In every step h = 1, 1.2...., H within an episode, the learner observes the state 8n E Sp, and selects an action ap E A. The learner then transitions to the next state via $h+1 P(-|sM, (,)), which is only supported
also use R(s, a)
S4+1. and receives the reward The R(s (i.). We assume that the reward is constrained such that Σ Th [0, 1] for any policy almost surely. Given a policy x S + A, the Q- fffucction and V-function for E Si, are defined by (s, a) ET <>> R= Th |sh 8, ab. al and (T( QT (s)) The Q-function and V-function of an optimal policy n* are abbreviated with Q and V*. We use QT a; M) and Q" (s,a; a; M) denote the Q Q-functions under model M (P, R).
Learning in MDPs is a DMSO problem where M = P x R with P being the set of transition kernels and R the set of reward functions. A round in DMSO corresponds an MDP episode, and observation o = (81, a1, v1, 82, d2, (TH. is the trajectory. For any function g. we write ET.M [g(o)] = (() If g(0) only depends on (81, 01, 82; (22,..., a,,), we also write it as [TT"(((())) We use (T)( = ET.. |EK= T'al to denote the expected total reward obtained by policy in MDP M, and dr, (s,a) (or di,
d (s.a)) the occupancy measure on step h under policy
and model M (or transition P).
2.1 --RESTRICTED LEARNING
For DMSO, [FKQR21, FGH23] and [CMB25] studied the stochastic setting where Mr = M for all t. They showed that the DEC characterizes the regret lower bound and captures the complexity of decision making. They proposed model-based algorithms with near-optimal upper bounds up to the model estimation complexity log .M.. On the other hand, [FRSS22] and [XZ23] studied the pure adversarial setting where M, arbitrarily changes over time. For this setting, they identified that DEC of the convexified model class characterizes the regret lower bound, which could be significantly larger than DEC of the original model class. Their upper bound replaces log [M] by log III, reflecting that they perform policy-based learning without finegrained estimation of the model.
Several works go beyond pure model learning or pure policy learning, [FGQ+23] considered model- free value learning in the stochastic setting where only the value function estimated, aiming to only incur log [F] estimation complexity, where F is the value function set. [LWZ25] and [CR25] considered the hybrid setting where part of the environment is stochastic and part adversarial, and the target of estimation is only on the optimal policy and the stochastic part of the environment.
We base our presentation in [LW725]'s formulation, which can cover all cases mentioned above.
Definition (Infosets and & [LWZ25, CR25)). Let be a collection of subsets of M x II satisfying: 1) The subsets are disjoint, f.r any o, ø' E 4. o # ø', then $ o' = 9. 2) Every & contains single policy, i.e., if (M, π) (M', x') E o, then π x'. We call a & an information set (infoset). Due to 2) above, each @ E + is associated with a unique policy. We denote this policy as Th. We also Uscs á M x II.
define V
With Definition 1, for given p E A(D). PE A(TI), v E A(T), and n > 0. [LW725] defiieeeeeeeed --AIR:
Vir(TT) - VMr(z) 1 (L
AIR, (p. v) = (...
(I)
where vs(. 0) is the posterior over @ given (H, which satisfies o) x " "MM (MM,T*)M(M (o)T)) A-AIR can characterize the decision-making complexity in the $- restricted environment defined below:
Definition (f-resitricted environment [LWZ25, CR25]). A restrictd environment is an (adver- sarial) decision making problem in which the environment commits to ø* E & at the beginning of the game and henceforth selects (Ms, π&.) E ø* in every round L arbitrurily based on the history.
We use the notational convention in [LW725]: the hold subscript in (-(1,,, o) specifies the identity of the variable represented by instead of a realized value of that variable. The subscript may be omitted when clear.
3

---

Published as a conference paper at ICLR 2026
Theorem 3 (LLWZ25)) For @-restricted environment defined in Definition 2, there exists algo-
rithm ensuring E [e )] - IE E, miny max, AIR (p, vi Pi)] log [8)
2.2 RESULTS AND OPEN QUESTIONS IN [LWZ25]
[LWZ25]'s main results are based on 4-AIR: For model-free learning in stochastic MDPs, [LWZ25] obtained vT regret for linear Q" /V- MDPs (before their result, the best known rate is T Unfor- tunately, their algorithm cannot handle other canonical settings such bilinear classes, MDPs with bounded Bellman-cluder dimension, or MDPs with bounded coverability. For model- based learning in hybrid MDPs where the transition is fixed but the reward function changes arbitrarity time, [LW725] obtained near-optimal regret bounds for general cases up to a log([P||[T) factor.
An attempt was made by [LWZ25] to handle model-free learning in hybrid MDPs based extension of the optimistic DEC approach [FGQ 233.. However, their result only handles full- information reward feedback. Extension to the bandit setting is challenging under this framework as the optimistic update requires an explicit construction of the reward estimator.
In this work, we focus on model-free learning in both stochastic and hybrid MDPs. Our results generalize those of [LWZ255 in both directions: Our framework handles all canonical settings for model-free learning in stochastic MDPs, improving previous results by [FGQ* also handles model-free learning in hybrid MDPs with bandit feedback under the same reward assumption as [LWZ25].
SETTINGS AND ASSUMPTIONS
Below, we show how to view model-free learning in stochastic and hybrid MDPs as learning in r-restricted environments (Definition 2), and introduce the assumptions used in the paper.
3.1 THE STOCHASTIC SETTING
Definition 4 (Stochastic setting). In the stochastic setting, the environment commits to M at the beginning of the game and sets M, M in every round
For model-free learning in the stochastic setting, we assume the following:
Assumption (& for model-free learning in stochastic MDPs). In the stochastic setting, addition to II, 0,V) ) in the DMSO framework (Section 2), the learner is provided with function set F. Each model M E .M induces a function f F. Assume that models inducing the same f have the same Q* function and hence the same optimal policy TM (for example, an F that contains all possible Q" functions satisfies this, though F could also provide additional information). With this, & is created by partitioning M according the function they induces: Define t {op E F} where of {(M, Tas): M induces f}- With abuse of notation, we write M E & to indicate that (M, TM) Φ. We denote by Th the common optimal policy for all M é. and by fo(s, a) the Q" function induced by M E 6, i.e., fo(s, a) = Q" a; M) for all M E d. Define fols) = max, fo(s, a). We also use Vo(Te) == fo(s1) denote the value of policy as under any model in 6.
3.2 THE HYBRID SETTING
Definition 5 (Hybrid setting). In the hybrid setting, the environment commits to P E at the beginning of the game. In every round, the environment selects R₃ E R arbitrarily based the history and sets Mt = (P*, Rt).
For model-free learning in the hybrid setting, the definition of & becomes more involved as partitions over three dimensions (II, P. R) in different ways. Formally, the partition should satisfy the following Assumption We provide an illustration in Figure I in Appendix B help the reader understand this assumption.
Assumption 2 (& for learning in hybrid MDPs [LWZ25]). The learner is provided with a function set J for every TT. For any fixed n, each transition P E P induces function f E Frt T is created
4

---

Published as a conference paper at ICLR 2026
by partitioning P x R x II firstly according and then according to the the transition induces in F=: Define Q = [ т E II. E FF), where ox. = {(P, R) P induces f in F* E R...
We write P E Φ if there exists R. π such that (P, R. T) E o, and write M = (P. E o if P We denote by T the unique ι E IT defining & E +b
The next assumption describes the requirement for the function set in our work.
Assumption 3 (Unique reward to value mapping given & ILWZ25]). Let Tb satisfy Assumption 2.
Assume that for any fixed é and P. P,P' E é. holds that Q (s, az (P, Rt) = Q== a; (P', R)) for any 8,a, R. We denote fo(s, R) (s, a; (P, Rt) for any P E Φ, and define fø(s; R) Ba-xs(-ss)ffll a; R)). We also use VO,)(TT) = fo( R) to denote the value of policy The under (P, R) for any P E Φ.
To understand Assumption and Assumption better, we take adversarial linear MDP [LWZ24] for example. In adversarial linear MDPs, the learnr is given known feature mapping (pss, a) e Rd such that the reward function can be represented as R(s, a) = g(ss, a) T On and the transition as P(s'|s, a) gfs, a) Twp(s') In this case, one can show that for any π. Q" (s, a; Ri) (" a; P2. R)) Vs, a, R if and only if ET... [0(*), Assumption 3. we would like put such P1 and P2 in the same partition under иT (see Figure I for an illustration). In other words, in Assumption 2, each f E F= corresponds to a unique value of (E..P(o(sn, (o((), an)))RE[R] E Rd and as long as two P's share this value, they both belong to Φz.--
(h. a2)] for all h. Based on [0(,,, ax)] = TT.P2 [0(*%,
We remark that while Assumption 3 is reasonable generalization of Assumption 1 to the hybrid setting, does not capture all learnable hybrid MDPs we are aware of. For example, if the transition space is partitioned according to Assumption 3 for hybrid low-rank MDPs with unknown reward feature, then log |$| will scale polynomially with the number of possible feature mappings. In contrast, the work of [LMWZ24] handles this case with the regret scaling only logarithnically with the number of possible feature mappings. There is still technical difficulty in handling this case in our framework, and we leave it future work.? We also remark that the previous work by [LWZ25] has the same limitation even in the full-information case.
Therefore, in this work, for the hybrid setting, we consider linear reward with known features, formally stated in the next assumption.
Assumption 4 (Linear reward with known feature). There exists feature mapping 9 S x A - Rd known to the learner such that for any R E R. R(sh, an) (p(s), an.) (0 for all (sh, an) e Sp. X A for some Og Dr(FF (R) E Rdd
While the stochastic setting (Definition 4) and the hybrid setting (Definition 5) are special cases of @-restricted environments (Definition 2), the adversary in these special cases has additional restriction: for example, in the stochastic setting, the adversary is allowed to choose M d² at the beginning of the game, but has to stick to M* throughout interactions. Similarly, pa has to be fixed in the hybrid setting. This is different from the general @-restricted setting where the adversary is allowed to choose M, E ø² arbitrarily in every round. However, using such a "coarser" partition & to model these settings is crucial for obtaining improved estimation error that only scales with the size of the value function set.
4 GENERAL FRAMEWORK
This section introduce a general framework and complexity measure for the @-restricted environment, which covers model-free learning in stochastic and hybrid MDPs as special cases. For given p E A ()), define for p E (III) and E A
. AIR, (p.P:p) = EEN VM((T)) -M(T)))-M(TT)) 1 - = 1)
(2)
'The algorithm of [LMWZ24] begins with reward- free exploration to learn a feature mapping. followed by online learning over that fixed feature mapping. While this two-phase approach could potentially be integrated into our DEC framework in special cases, our goal is to explore approaches that avoid such design to address more general scenarios.
5

---

Published as a conference paper at ICLR 2026
for some divergence measure DF convex in for any and p. 4-AIR defined in Eq. (1) is special case where D" (wilp) = MMM-)BanM((-1)) (K (-IT, o), p)] The general algorithm designed based on Eq. (2) is shown in Algorithm 1.
Algorithm 1 General Framework
Input: Set of partitions & and its union v (defined in Section 2.1). (1) = 1 VΦ E
for f = 1, 2,
do
Set pt, 2 the solution of the following minimax optimization (defined in Eq. (2)):
min max AIR, (p, pt). PEA(T)
(3)
Execute Fe ~ Ps, and observe Or ~ Me(-(TT)-
Update Pr+1 = POSTERRIORUPDAATE((. Pt: Te, Oz).
Algorithm I has two main steps. First, given the infoset distribution E A($), solve the policy distribution Pt and the worst-case world distribution in in the saddle-point problem Eq. (3). This is similar to the previous AIR framework in [XZ23] and [LWZ25]. After taking policy n; ~ Pe and receiving the observation Or ~ M+(-TT), perform a posterior update by incorporating new information from og (Eq. (4)) and obtain the new infoset distribution Pr+1 (()). In [XZ23] and [LWZ25], this posterior update step is simply P++1(0) = ue " ot), but could take different forms in our case depending the specific divergence D instantiated later.
The ability of our algorithm to handle a general divergence D is enabled by our new analysis techniques. The update rule P++1 (ő) 1/ ( oz) in [XZ23] and [LWZ25] and the corresponding regret analysis heavily relies on a "constructive minimax theorem" [XZ23] that is restricted to strictly convex divergence measures and somewhat cumbersome to generalize to divergence other than KL. Our new analysis, on the other hand, is more flexible and nicely connects to the standard analysis of mirror descent.
Our analysis goes as follows. For any (M, π) E M x II, denote MM.= E AM x II) as the Kronecker delta function centered at (M, That is, DM,((M, T) and 6 (M', x') for any other (M', T'). By simple first-order optimality condition (Lemma 18) and the fact that 142 is a best response to Pt (Eq. (3)), we have (recall the definition of a in Definition 2)
Exapi VMN. - (T) 1 D 10 (6 llp:)
(5)
1)
1 - DT (vl(p)) ETpop Breg nz (-lee (6 ag v1)
max ET E(M VMr(TT)) VTs(T) PEA(F)
1)
where Breg y) = F(x) - ((v))<VP(yy,.r
2 0 is the Bregman divergence defined with convex function Since pe minimax solution in Eq. (3), after rearrangement of Eq. (5) and
summation over t, we get
T
(VM. (TT.) Eapp, (T))
(6)
Est
T
T
min max AIR, (p.
Enaop
D (O lle)) - Breg pa ((Ip.)) (11))) (OMe)
1=1 PEA(IT) vEA(W)
1=1
where we use the definition in Eq. (2). From Eq. (6), we have the following theorem.
Theorem 6. Algorithm 1 achieves E[Reg(TT: < B E min, max, AIR . (p, (:)):
Est 7
The POSTERIORUPDATE in Eq. (4) has to be further designed in order to minimize Est. In Ap- pendix C, we show how our new analysis recovers previous results of [XZ23] and [LWZ25] easily, We remark that when recovering [LWZ25]'s result for model- learning in hybrid MDPs with fall-information feedback, achieve it with a more complex two-level algorithm. This shows the flexibility of our framework. In the next two subsection, we discuss about the two terms in the regret bound of Theorem 6.
chooses D such that Est does not even scale with log |0) while they

---

Published as a conference paper at ICLR 2026
4.1 DIVERGENCE MEASURE IN ALGORITHM 1 AND dig-dec
To handle the MDPs of interest in Section 3, we will instantiate Algorithm 1 with the following divergence D:
Dd (v(ll))) = M KL (vo(()
B D ((IAA)]]]
(7)
where D² M) Miii is another divergence that measures the discrepancy between infoset & and model M. Two choices of D will be introduced later in Section 4.2: averaged estimation error and squared estimation error.
With this defimition of D" (v(lp)), the first term in the regret bound in Theorem can be bounded by the following complexity:
dig-dec,
O.D A
min max AIR
(EA()) REA(V)
max min max PEA(T) PEA()) WEA(V)
B B(Maar Jou Vir(T*) - Var(T)- 1
1 Moo (KL(Uo((TT,)) o), - -Bpp D "
[
(8)
As both the KL and the D terms Eq. (8) are measures of information gain, we call this complexity notion dual information gain decision-estimation coefficient (Dig-DEC). In Section 6, we compare in more detail how Di is upper bounded by optimistic DEC the complexity achieved by the prior work IFGQ+237 in the stochastic setting, and when the improvement can be arbitrarily large.
4.2 POSTERIOR AND BOUNDS FOR Est
The D we would like to use in Eq. (7) depends on the MDP class we consider. Below, we describe two classes of problems that associated with different choices of D, under which the achievable rates for Est are different.
4.2.1 AVERAGE ESTIMATION ERROR
Assumption 5 (Average estimation error). There exists an estimation function C, [- B, B for every h such that for any & E & and any M E á. it holds that for any π E IT,
BT. [()(
Additionally, assume that the adversary is restricted such that for any 6 and t E (T), it holds that Ma (6x on)] Ex.Me (dx on])]
The estimation function é in Assumption 5 will be instantiated the average Bellman error in Lemma 8 for all concrete examples. In this case, Assumption 5 is essentially the standard realizability assumption. We adopt the more general terminology of "estimation error" following [DKL 2
Theorem 7. Assume Assumption 5 holds. Then Algorithm 4 with Algorithm 2 as POSTERIOR UPDATE with Dd M) = (dll A maxxe[[] F Σ (E [en(ó) ox)) ensures
E[Est] S N 10g((2))
Lemma 8. In the stochastic setting, Assumption I implies Assumption 5 with N = estimation function (ō; on) = fa(sh. an) - rh - fo(sn+1) In the hybrid setting. Assumption 2, Assump- tion 3 and Assumption 4 imply Assumption with N d estimation functions (n((: fo(sn, ani e;) ) (pss,, ax) e; - fo(sntieez), where ej as a reward represents the reward function defined as R(s,a) a) = ((s,(())))))))) a)
In order to minimize Est in Eq. (6), have to obtain estimator of D ( for all ø. This can only be achieved via batching, which results in the design of Algorithm 4: In each epoch k 1,2, ..... T/T, the learner uses the same policy m. to interact with the MDP for episodes. While
7

---

Published as a conference paper at ICLR 2026
similar epoching mechanism has been proposed in [FGQ*23], our construction of the estimator improves their rate of Est from vT Ti. To the difference, consider the case N in the stochastic setting, in which the goal is to approximate Σ (E*t.M [(x (n)))))) With observations (o',...,0") o7) drawn from M (T)) ) in epoch k, we construct an unbiased estimator as (Ø) Ex=1 (2 EEE (db; of))) E la (00 o.)), while [FGQ+23] constructs biased estimator as [x)()) Dh=1 ( Ei= (x The detail of this estimation procedure is
provided in Appendix F.I.
4.2.2 SQUARED ESTIMATION ERROR
Under stronger assumptions on the estimation function, we can improve the rate further. This is motivated by the class of Bellman-compler MDPs, given as followed.
Definition (Bellman completeness for the stochastic setting). & satisfying Assumption is Bellman complete under model M = (P. R) ifr any & E Φ there exists an o' E & such that for any 8, O,
for (s. = R(s, (x
A 4 is Bellman complete if is Bellman complete under all model M E M'. Definition 10 (Bellman completeness for the hybrid setting). A 1 satisfying Assumption 3 is Bellman complete under transition P for any & E t, there exists an o' E such that Th = T and for any a, R.
(s a; R) = R(s, a) + EN' [f((s;; A & is Bellman complete if it is Bellman complete under all transition P E P. Assumption 6. There exists εn. o x + O [0, B²1 for every h and TM o - 1 for every M such that for any & and any M E 6. it holds that &- M. Furthermore, any & & E 4, any M E M, and any II,
4B2. 182.TE= T... M (En( oo; on) - Cn(TTr, 9r; (x)) 2 R [SE((0' (roo)) - En (TM d; on)))
Additionally, assume that the adversary is restricted such that TM,, Φ TM, A for all & and all
t, E [T).
Similar to Assumption 5, the function & in Assumption 6 will be instantiated as the square Bellman error in Lemma 12 for all concrete examples. In this case, Assumption 6 corresponds to the standard realizability plus Bellman-ccopletence
assumption.
Theorem 11. Assume Assumption 6 holds. Then Algorithm with Algorithm POSTERIORUP- DATE with Dt M) = Di (+ll A B²H
Σ _ ExM (6, on) (TM &; on)) ensures
E[Est] S logg210 (0).
Lemma 12. In the stochastic setting, Assumption I together with Bellman completeness (Definition 9) implies Assumption with the estimation function En(d &; on) = (fer ax) - Th fa (s(+++))) and B² 1. In the hybrid setting, Assumption 2, Assumption and Assumption together with Bellman completeness (Definition 10) imply Assumption 6 with the estimation function Ed(d', 6; 0%) = [f (Sh, ax:ez) - sfsn, an)) e, - fo(s)41:
and B = d, where ej as a reward represents the reward function defined as R(s,a) = (8),a))-
With Assumption 6, POSTERIORUPDATE no longer needs to rely on batching. We leverage a two-timescale POSTERIORUPDATT learning procedure similar to that of [FGQ+23], which in turn builds on [A722]]. We refine their approach so Est can be bounded by a constant, improving over 23]'' f bound. In addition, our approach comes with a simpler regret analysis. Our POSTE features two-layer learning structure with a biased loss on the top layer. It is related to model selection algorithms with comparator-depender [CLW21],, but also has its special structure not seen in prior work. Thus, we believe it of independent interest. The detail of this estimation procedure is provided in Appendix F.2.
second-order bounds (e.g..
IIn fact, it suffices to assume Bellman completeness only under the ground-truth model M (as in [FGQ 23J). However, it is without loss of generality to assume Bellman completeness under all M E M.. as one can preprocess the model set M by eliminating models under which Bellman completeness does not hold. For simplicity, we assume the latter. Similar for Definition 10.
8

---

Published as a conference paper at ICLR 2026
5 APPLICATIONS
By Theorem 6, the worst-case regret Algorithm is E, min, max, AIR "t
f. D (p, pb) + Bst/n/ -
T + Est/1). In Section 4.2, we provided bounds on Est for two types of D, i.c., Dav and
Daq Below, we provide upper bounds for dig-dec,) "t 9.D in concrete settings associated with each D.
5.1 STOCHASTIC SETTINGS
For the stochastic setting, consider MDP class M and its associated O with bounded bilinear rank 21KI Bellman-eluder dimension [J1]] J, and coverability (XFB+23) The results are summarized in Table 1.The on-policy/off-pol -olloyyy in Table should on-policy/off-polli training in standard RL. Instead, they are two subclasses of the bilinear class [DKL*21] and correspond to the Q-type/V-tyee policy case has smaller regret because the executed policies provides sufficient exploration to notice model missmatch, while the off aff-policy case, the learner needs execute an additional exploration policy for this purpose.
be confused with the standard
Bellman eluder dimension in [JLM21]. The on-
Table Summary the applications in the stochastic settings. BE stands for MDPs with bounded Bellman-eluder dimensions. Dig-DEC bounds provided in Appendix H.3 for bilinear classes, Appendix H.4 for BE, and Appendix H.5 for coverable MDPs. Bilinear classes marked with are restricted estimation function specified in Lemma 29, under which it holds that dig-dec,, (i Dm < dig-dec, 9. D B and N are parameters specified Assumption Assumption The regret bound given by T dig- dec
Est/n with Est given in Theorem Theorem 11, with the optimal r7.
Setting
dig- dec,
4
D
B
N
Rege (TM-) )
class
sub-class
completeness
bilinear
on-policy
H dn
Dav av
1
1
H /dvllog T
bilinear
off-policy
A
Dav
[A]
H log
BE
Q-type
H'
D
1
H H log T
BE
V-type
AHdd|AIn
Dav
1
(d) log [ ( T
bilinear*
on-policy
/
11'd
Dsa
1
H H dT log |
bilinear*
off-policy
V /Had|App
Dzg
|A]
(d] log 2 ( (
BE
Q-type
/
H2dm
Dsg
1
H / log |
BE
V-type
/
/HadAAA
D=n
1
H(d log" $1)+T'
coverable
H²dn
Dza
1
H HddT log |
remark without giving details that in the stochastic setting, we can achieve same results in Table 1 with high-probability if we replace the EM~wEo- KL(u (-IT,, o), p:)] term by KL Pe) in the definition of D in Eq. (7). This variant, however, cannot handle the hybrid setting.
5.2 HYBRID SETTINGS
For the hybrid setting, with known linear reward feature, consider transition structure including hybrid bilinear classes [LWZ25] and coverability x3JB+23.. While it is possible to also extend Bellman-eluder dimension to the hybrid setting, omit it for simplicity.
COMPARISON WITH PRIOR COMPLEXITIES IN STOCHASTIC MDPs
Compared with dig-des dec +D in Eq. (8) achieved by our algorithm, the complexity of optimistic E2D [FGQ+23] defined for the stochastic setting is
T.D o-dec,
max min E ER Eamp Vo(TT) VM((T) - (d1l (EA()) PEA(T)
(9)

---

Published as a conference paper at ICLR 2026
Table 2: Summary of the applications in the hybrid settings. Dig-DEC bounds are provided in Appendix 1.2 for hybrid bilinear classes and Appendix 1.3 for coverable MDPs. Bilinear classes marked with * are restricted estimation function specified in Lemma 36, under which it holds that dig-dec, D.D < dig-dec,) "...
Setting
dig-dec, +
D
B
N
E[Reg( ((Reg(===)))
class
sub-class
completeness
bilinear
on-policy
(H)&
Dav
1
d
d(H1 log / (1))TT
bilinear
off-policy
(Had)|A(())) n))
Dav
IAI
d
(Hod*IAA)) log T +
bilinear*
on-policy
(HDd'
Daq
vd
d(H² log" |+1)=
bilinear*
off-policy
(H ||(
Deq
Vd.AA
(Hod*AA) log + +1)+
coverable
(HHd
Daq
Vd
d(H log" {0))+
for the same choices of D. Another model-free DEC [LWZ25]
dec, + max min max E EM- Vir(#*)) Var - -. ( PEA(T) (II VEA(V)
7
S dec for any non-negative divergence D. Furthermore, we have Theorem 13. In the stochastic setting, dig-dec,;, 4.D S o-dec, 4.D for any D.
clear that dig-dec,," ". D.D
Since DECs with parameter is usually of order (nd)² for some intrinsic dimension d and exponent S 1, Theorem 13 implies that for any setting that can be handled by optimistic E2D with a certain D2, it can also be covered by our algorithm with the same D). Compared to optimistic DEC (KL o), that can (KL o), v2)). They have different purposes: The first term (L () is for regularization, which makes the marginal distribution of not overly distant from p. This is the key that allows us to avoid the optimism mechanism [FGQ [FGQ+23] 23] (i.c., the (T( in Eq. (9)). We remark that by regularization only, we recover the bounds achieved by optimistic DEC in the stochastic setting (this can be seen from the proof of Theorem 13), though is unclear whether can give strict improvement. However, the removal of optimism turns out to be important in the hybrid setting (Section 5.2) as it avoids explicit (L o), 14)]
(Eq. (9)), Dig-DEC (Eq. (8)) has an extra KI. term Egp be further decomposed into two terms (L P) -EB.ppEM..BooMME
construction of the reward estimator. The second term En--EM--EE--Miii an information gain that allows Dig-DEC strictly improve over optimistic DEC even in the stochastic setting. This is because all common choices of D such as bilinear divergence and squared Bellman eтror are mean-based and ignore distributional differences, and the KL information gain term can capture them. We give toy example in the next theorem to show this, with a detailed proof provided in Appendix
Theorem 14. There exists 3-armed bandit instance where for any T and S 1, the algorithm in [FGQ 23) suffers max, E[Reg(a)) Ri (T),,, while our algorithm achieves max, E[Reg(a)) S 1.
CONCLUSION
We introduced a new model-free DEC approach that removes optimism in prior work and incorporates two information-gain terms into the AIR objective for decision making. In addition, we refined the online function estimation procedure. Together, they yield improved regret bounds in the stochastic setting and establish the first regret bounds for model-free learning in hybrid MDPs with bandit feedback. Future directions include relaxing Assumption 3 and Assumption 4, and investigating the fundamental limits of model-free learning.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
[A722] Alekh Agarwal and Tong Zhang. Non-linear reinforcement learning in large action spaces: Structural conditions and sample-effcienccy of posterior sampling. In Conference on Learning Theory, pages 2776-2814 PMLR, 2022.
[BLL+1I] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[CLW21] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pages 1216-1259 PMLR, 2021.
[CMB25] Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-estimation coefficients: Pac, reward-free, preference-baat based learning and beyond. The Annals of Statistics, 53(1):426-456, 2025.
[CR25] Fan Chen and Alexander Rakhlin. Decision making in changing environments: Robust- ness, query-based learning, and differential privacy. Conference on Learning Theory, 2025.
[ Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
[DLW223] Yan Dai, Haipeng Luo, Chen-Ye Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. In International Conference Machine Learning, 2023.
[FGH23] Dylan Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimatioo coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pages 3969-4043. PMLR, 2023.
[3G Dylan J Foster, Noah Golowich, Jian Qian, Alexander Rakhlin, and Ayush Sekhari. Model-free reinforcement learning with the decision-estimation coefficient. Advances Neural Information Processing Systems, 36, 2023.
[FKQR21] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 12. 2021.
[FRSLX21] Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance- dependent complexity of contextual bandits and reinforcement learning: A disagreement- based perspective. In Conference on Learning Theory, pages 2059-2059. PMLR, 2021.
[FRSS22] Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35:35404-35417 2022.
[0]] Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adver- sarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860-4869. PMLR, 2020.
[JLM21] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13440--133 13418. 2021.
[KZWI.23] Fang Kong, Xiangcheng Zhang, Baoxiang Wang, and Shuai Li. Improved regret bounds for linear adversarial mdps via linear optimization. Transactions on Machine Learning Research, 2023.
[LMWZ24] Haolin Liu, Zakaria Mhammedi, Chen- Yu Wei, and Julian Zimmert. Beating adversarial low-rank mdps with unknown transition and bandit feedback. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.

---

Published as a conference paper at ICLR 2026
[LWL21] Haipeng Luo, Chen- Yu Wei, and Chung- Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931-22942, 2021.
[LWZ24] Haolin Liu, Chen- Yu Wei, and Julian Zimmert. Towards optimal regret in adversarial linear mdps with bandit feedback. In The Twelfth International Conference on Learning Representations, 2024.
[LWZ25] Haolin Liu, Chen- Yu Wei, and Julian Zimmert. Decision making in hybrid environments: A model aggregation approach. Conference on Learning Theory, 2025.
[L77724] Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Improved algorithm for adversarial linear mixture mdps with bandit feedback and unknown transition. In International Conference on Artificial Intelligence and Statistics, pages 3061-3066 PMLR, 2024.
[NGSA13] Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online markov decision processes under bandit feedback. IEEE Transactions on Automatic Control, 59(3):676-69) 691, 2013.
[RM19] Aviv Rosenberg and Yishay Mansour, Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32, 2019.
[SERM20] Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613. PMLR, 2020.
[SKM23] Uri Sherman, Tomer Koren, and Yishay Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. International Conference on Machine Learning, pages 31117-31150. PMLR, 2023.
[3FB+23] T Xie, D Foster, Y Bai, N Jiang, and S Kakade. The role of coverage in online reinforcement learning. In Proceedings of the Eleventh International Conference on Learning Representations, 2023.
[XZ23] Yunbei Xu and Assaf Zeevi. Bayesian design principles for frequentist sequential learning. In International Conference on Machine Learning, pages 38768-38800. PMLR, 2023.
[2Y Canzhe Zhao, Ruofeng Yang, Baoxiang Wang, Xuezhou Zhang, and Shuai Li. Learning adversarial low-rank markov decision processes with unknown transition and full- information feedback. Advances in Neural Information Processing Systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2026
Appendices
A Regret Bound Comparison with Previous Work
14
Partitioning over P x II for hybrid MDPs
14
Omitted Details in Section 2
15
C.1 Recovering Theorem
15
C.2 Recovering results for adversarial MDP with full-information feedback [LWZ25]
15
D Concentration Inequality
16
Mirror Descent
18
F Estimation Procedures
20
F.1 Average estimation error minimization via batching
20
F.2 Squared estimation error minimization via bi-level learning
22
G Omitted Details in Section 4
25
G.1 Assumption reductions
25
G.2 Bounds on Est
26
Relating dig-dec Existing Complexities the Stochastic Setting
28
H.l
Supporting lemmas
28
H.2
Relating dig-dec to o-dec
28
H.3
Relating dig dec to bilinear rank
29
H.4 Relating dig- dec to Bellman-eluder dimension
30
H.5 Relating dig dec to coverability under Bellman completeness
31
I Relating dig-dec Existing Complexities in the Hybrid Setting
33
LI
Supporting lemmas
33
I.2
Relating dig-dec to hybrid bilinear rank
36
1.3 Relating dig-dec to coverability under Bellman completeness
39
J Omitted Details in Section 6
42
J.1 Proof of Theorem 14
42
K Use of Large Language Models in Preparation
45
13

---

Published as a conference paper at ICLR 2026
A REGRET BOUND COMPARISON WITH PREVIOUS WORK
Table 3: Regret for model-free learning in stochastic MDPs (only showing 7 dependence). "Toy
3-arm" is defined Theorem 14. The two bounds in the same cell correspond the cases with on-policy and off off-policy estimation.
[Bilinear or BE Coverable] + Bellman Complete On-Policy
Algorithm
Bilinear BE
Toy 3-arm
Exploration Mechanism
[DKL 21]
[JLM21]
T
VT
VT
optimism
[XFB+23]
[FGQ+23]
TH/T8
T
VT
information gain + optimism information gain
Ours
T5/Tb
VT
Table 4: Regret for learning in hybrid MDPs (stochastic transition and adversarial reward). The model-free learning guarantees in [LWZ25] and our work cannot handle general reward but rely on Assumption 4.
Billinear or Coverable]
Algorithm
Bilinear
Model-Free
Bandit Feedback
General Reward
Bellman Complete + On-Policy
[LWZ25]
/T/T3
VT
[LWZ25]
T T
X
X
Ours
T is
T
X
B PARTITIONING OVER P x R X II FOR HYBRID MDPS
P
R
Figure 1: Partitioning for hybrid MDPs
Figure illustrates the partition scheme over II P R described Assumption
Fach infoset ø (represented by the green block in Figure 1) is associated with single policy To. subset of transitions, and all reward functions. shown Figure 1, the partition over the P space could be different for different
14

---

Published as a conference paper at ICLR 2026
C OMITTED DETAILS IN SECTION 2
In this section, we show that the algorithms in [XZ23] and [LWZ255] are special cases of Algorithm 1.
C.I RECOVERING THEOREM
The decision rule of [LW725]]s algorithm corresponds to Eq. (3) with D=(()pp) EM (L p)]
It can be shown that (l (v,
EM EM-OBOMMM M-)a) ( (-|x, o), u uss(11n (-IT,)))) in this case. Furthermore, notice that when V' = a we have (- T, o) = 6g- according to Definition 2. Thus, the estimation error term in
Eq. (6) in [LWZ25]'s algorithm is
KL pc) (o KL (v))o(11Te, (T))))))))))
E Est
E
E log ve(0" (Te. 01)
(KL pi) KL (vel (-1T,, 0z)))
Pe(())
where the second equality we use that og is drawn from M, (- Thus, by letting Ps+1(0)
ue ( ot), their algorithm achieves E. [Et] E log Pt-1( I log oाtσ- log ///
p=(0*) Using this in Eq. (6) proves Theorem 3. The results of [XZ23] can also be recovered they are special cases of [LWZ25]]
C.2 RECOVERING RESULTS FOR ADVERSARIAL MDP WITH FULL-INFORMATION FEEDBACK [LWZ25]
For learning with full information feedback in the adversarial MDPs, the learner can observe the full reward function at the end of each episode. In other words, episode the reward function R₂ S x AA- + [0, 1] is part of the observation bound can improved to log [A]. To achieve this, [LW725] designed a two-level algorithm and define new notion called InfoAIR. We can recover this result by instantiating
In this setting, the log [T]] dependence in the regret
Algorithm I with PEP P, a, E A, Vs E S} where (p.(o.)=es = {((P, RR,, T²) E R, x* (a,).es) }, that is, partitioning M II according the transition kernel and the actions taken by the policy on all states. Then define
= (or,(a.).ss
(= = ).p. Bondd Eardr.P KL
Pa,,
where Mp.R denotes the MDP model with transition kernel P and reward function R, and Pa..P denotes p' marginal distribution over (a., P) following notational convention. Finally, update the posterior as Pi+1 = argmin, E.es KL (Pa..P, P(- oc)). This recovers the same regret bound as in [LW725] without the need for the two-level design. We also note that the analysis for this result requires our new proof strategy in Eq. (5), as the D (vllp) here is not strictly convex A and the previous proof [XZ23, LWZ25] cannot be applied.
15

---

Published as a conference paper at ICLR 2026
D CONCENTRATION INEQUALITY
Lemma 15 (Freedman's inequality [BLL+1IJ). Let X1, X2.... .. be martingale difference sequence with respect a filtration 81 C 82 C... such that E[X;] 8+ 0 and assume Xx S almost surely. Then for any 2 B, with probability at least 1 - 5,
E
1|x213d + a log(1/)).
(10)
... be a sequence with respect to filtration 81 C 82 C ... such thut [3] lr and assume max{Xe Pt, Mt] S B almost surely. Then for any a 2 4B, with probubility at least
Lemma 16 (Empirical Freedman's 's inequality). Let X1, X2....
T
(ee X.)
x? a log(1/0).
(1I)
Proof. Denote E+| = B[. Br]. We have at any time step
- (m -x)) xxx²)
E
exp
4 o x? + (1(1--))) 4 )
21
< E,
1 +
- (c4 -xi)
4
((r - X,)² + +x3) 1.
1++
a²
x?
+
Markov incquality finishes the proof.
Lemma 17. Let (i), (X2, Y2).. ... be sequence with respect to filtration 31 32 such that [X, < B and 0 < Y, < B almost surely. Furthermore, [[. 2 E[Y, and
BE BE
[e] N E [
Then with probability at least 85
T
4 1v)
3
S
Σ
X₂
+ 9B 1olgg(1/)))
(12)
Also, with probability at least 1 - 8.
X1
X, xx
lolog()/
(13)
Proof. Denote E, = E 3.). Let c
[ 1] be fixed constant, and define Z, cX,
à LY,
Applying Lemma 15 with = 9B gives
T
EE [z,] Ze) <
E, [E z 9B (1/8)/))
9B
T
<
E2 + 9B 9Blo)(1/))
9B
t=1
Σ
2c 2c x +
2
Ex
+ 9B log(1/8)
9B
16
1=1
1 T
Σ
2c E, [X.]
2
2
+ 9 log(1/8)
9
16
(E. Y?
BE, Y.] because Y₁ E [0, B)
16

---

Published as a conference paper at ICLR 2026
Rearranging:
2c
1
Z4
X
Zz 9B log(1 (1/))-
(14)
72
1=1
To prove Eq. (12), let = 1, which gives Es Z1
20
+ 72
X = E, [x - 1/2 X 2
E.
X2)- Combining this with Eq. (14) proves Eq.
(12). To prove Eq. (13), let c = 1 which
gives E, 1 2c² + X. = E, 2 1 72 Xx
2 0. Combining this with Eq. (14) and
rearranging proves Eq. (13).
17

---

Published as a conference paper at ICLR 2026
E MIRROR DESCENT
Lemma 18 (First-order optimality condition). For any concave and differentiable function F, if V E argmaxyen F for some convex set S2 then F(v) S F(v)) - BBeeg (v. v/) for any v E S2.
Proof. Define G = FF Then G is convex and v/ E argmin, G(v'). We have by the definition of Bregman divergence Breg, (v, v/) G(v) G(v)) (VG(''), -///- and first-order optimality
condition (VG(v'). - 1/) 2 O. Thus, G(v) 2 G(v)) + Brego(u, which is equivalent to
F(v) F(v')
(V)))))))
Lemma 19. Let g: 2 + 1-1, 1] be any function and let v, p E ( Then for any 1) > 0,
Ex-r(o(o]] Eg-plg(0]] KK(V, p) n.
1)
Proof.
B - Ex-ple(0] S 2Drv(v..) S $2 (LKL)( & kL( +m. "
where we use Pinsker's inequality and AM-GM inequality.
Lemma 20 (Mirror descent with auxiliary terms). Let F, be convex function over AN. and let l, b E RN with lg denoting (le(1)?,.... ((())),...,,(((N)))) Then the update p1 N 1 and
P141 argmin (p, le 4rl + bi) F((e) + kL((p.D)} PEAN
1
?
with 7|6((1) S TO and 0 S rb)(1) S & for all i E [N] ensures for any p* AN.
Σ (pe. Et)
log +
T
Σ (p',te + 47 + bi) 2 (pe, be) + Fi(D") - Fi(++1) - Breg (p', pc+1))
Proof. By Lemma 18.
(pe+1, 4 + 47 + b.) + F((p++1) + -K((p++1,1))
s <(p', la 4 + bb) + Fi(e") 1 KK(('',pl pp)) Bregr, (p', p(+1) 1 Rearranging gives
KL((p' p(41).
?
(pr,4 4 S (p*,4 + 1-(2) + (pr- P1-1; eg + 47,, + -b) -K((p41.P))
+ +p- - pc. + KL(p", .p)) KL(p", PP+1)
+ FF(())) FF(((41) Bregr, P(+1). (15)
7 1
Since 7/ex(1) + (1)2 + b.(1)) S
(1) 12 < 1, by Lemma we have (p. pe+1, + 47 + b.)
T6
1 7
kL(p(+1,P.)
s> (pe. (C, + 1762 b²)²)
22 (pr, (14))) + 2y (pe. bZ)
1
(pr, 17(2) + 2 (pr bz).
18

---

Published as a conference paper at ICLR 2026
Using this in Eq. (15) we get
(pc. 41) S (p', le + 4y(1) + bp" - (pr: bi)
2
KL(P", pt) KL ,Ll(x,,++1)) + Fe(D") F+(p++1) - Breg,, (f", Ptt11)-
Summing over 1 gives the desired inequality.
19

---

Published as a conference paper at ICLR 2026
F ESTIMATION PROCEDURES
We present the choices of POSTE as standalone online learning algorithms because they might be of independent interest.
F.1 AVERAGE ESTIMATION ERROR MINIMIZATION VIA BATCHING
Algorithm 2 Epoch-based learning algorithm for average estimation error
Input: An estimation function 4, O + [. satisfying Assumption 5. Parameter: T = T 3 = N 7 23 (
for k = 2........ K do Receive observations or Me (T)) for all E Is {(k: 1)T (....,hT). Split I into two sub-intervals of equal size:
.
I = (kk- 1)r + 1..... (k- 1)T + } and I = =(k - 1)T + +3 + kr....,TT).
Define for all j E [N].
H
[+) B²H
T
Σ
Σ
(nloe Ix(d) = Σ
La [x(
I
h=1
EEZ
j=1
Let (Fi)seTa
( + R be convex functions. Calculate
(0. + (47 + + Σ Pelp) + 1 x
Pk+1 = argmin
(16)
PEA(O)
KEIx
7
Lemma 21. With probability at least 1 8/3, Algorithm 2 satisfies
K
H
K
Σ
max JE(N)
Σ
pe(
[Ix(0) + $ [c(())) + 4,3 log (3/5).
1
BAH
LEI
k=1
Proof. By Assumption 5, for any 1, Is it holds that
B. [Ex (ó; on)) Eya.My (((():)))) We denote ( E (d: on)] for any E It. Clearly, the left-hand side of the desired inequality upper bounded by
N ΣΣΣ
N
H (0)
B (O)
M Mi
[L (c;; (d))))))))))
(d(
ΣΣ j=1
B
LET, 1=
By construction, [T) = B ビj=1 Σ (0)) due to the conditional independence of Lemma 16 on
the observations. Furthermore, we have (x) [-TN,
E,,,, NN. Therefore,
the sequence X₃ = Eepo(o) with 3 2 7rN:
(0) ΣΣ
(n) < Σ Σ
1 - + 48 13g(3/)). pk(() (x(Ø)
B-H
j=
k=1
Lemma 22. With probability at least 1 - -//3,
K Σ 1x(0')2 < KN2 2og (12NKH/))
20

---

Published as a conference paper at ICLR 2026
Proof. By Assumption 5 and Lemma 15, for any J. k, h, have with probability 1 1-6, 6,
Σ
Σ
- Σ
S BB/rlog(110))
KET
rEI
1EI
Σ En( o0.h)s TEZ
Σ (Ø onhn)s
Σ
E B (60'"
S BB llgg(1205)
KEII
Via a union bound over all these events, this holds simultancously for all j, Hence with
(
probability 8, we have [x(Ø")}] BhH H (IB//1og(12XXHHH)) (0
for all j, k simultancously. Summing over j and k finishes the proof.
Lemma 23. With probability at least 1 - 8/3, we have
K
(x(6)) S 3
Proof. Define the random variable Xx have with probability at least - 6/6,
min =inn By Lemma 16
K
K
Σ
x.
k=1
k=1
where we use that [E([X,) I E T
(o') ]
Finally note that with probability 6/6 we have
(d))) X₁ for all k by the proof of Lemma 22. Combining both events finishes the proof. O
Lemma 24. With probability at least 1 6, Algorithm satisfies
Σ
Σ
(. (ea on)))) So (NT's log (8)
max JE[N
B
TET
(F((5.)) Fe(p++1) Bregg, (k+1)).
Proof of Lemma 24. By union bound, the events of Lemma 21, Lemma 22, and Lemma 23 hold simultaneously with probability 1-6. Observe that the update of ps (Eq. (16)) is in the form specified in Lemma 20. Invoking Lemma 20 with by 2 24 we get
K
log (
I Pk. La + 8
(17)
7
Lx(Ø")
2 ( 3
La( (F((6))) F((px+1) Bregr, (8p- putii))
tEIN
Chaining Lemma 22 and Lemma 23,
K
Lx(x+)+ + ( 3 Le((TT2)
I 48 (6/8)) + 47 + KN2 KN2 log (12
Using Lemma 21 and substituting 3 = 7TN 28 yields
E Th. M [ea(d: 35. KN T
B ΣΣ Pk
max JE
EE
Using K = T/T and tuning
T yields O(T
21

---

Published as a conference paper at ICLR 2026
F.2 SQUARED ESTIMATION ERROR MINIMIZATION VIA BI-LEVEL LEARNING
Algorithm 3 Bi-level learning algorithm for squared estimation error
Input: An estimation function En : 4 x O + [0, B²] satisfying Assumption 6. 64 log (b)
Parameter:
(i( = // / Ve E and ς (0) ()) = 1/ [/. Vol
for f 1, .... I do
Receive observation or ~ Mc(-(Te). Define
H
( B²H
Σ h=1
En o, or,));
(, = A の) - Exiingr ae (110) (e(0', 0]],
((()) = (0) max Ps(ti))+,
pc(
Let F (T)) + R be a convex function. Calculate
T4 + bb) + P((p) + ]
Pt+1 = argmin PED(B)
(18)
$ Σ ((()))
(++1(0)))) x exp
where ar(Φ)
16 max,5t P=(
Lemma 25. With probability at least 1 - 6,
Pt, L.) log |
7
(pe, bi) +b(00) + F(((o-) F((p41)) Breg (6or ((o)) + + (log(1/6)).
Proof of Lemma 25. Observe that the update of pe (Eq. (18)) is in the form specified in Lemma 20.
Invoking Lemma 20, we get
log $
(pr, Tx)
(19)
7
1 (=(0")+47/4) + 2 b+(0") (pe,be) + F2(5x)) Fe(pe41) Bregg, (6ar, (ōar,pt-))
By Assumption 6 we have
0 < [T( E, [A,100
(60(0)))))) x5) Aer ++)))
Egrnge(-lor)
Ee (Ar(d", - -e
o"')²]
(Jensen's inequality)
< Exrna(-)1"))
Eg (Ai ,,0" Ae 6")]
(M. E Φ" and thus TM x*)
< 4Bxra((ld))
EE Ar( - AA ,d))']
(by Assumption 6)
[Er [Ar(o', .0)) - .
-E, (T)
22

---

Published as a conference paper at ICLR 2026
This allows to apply Lemma 17 with X, (o((d)) and Y 127.. which gives
T
T
1 _ (2()))
+ +
Lx(d)) +
16
<
[x[Le(0-)] + 36 log(1/6) S 36 36lo0(1/))
Combining this with Eq. (19) finishes the proof.
Lemma 26. With probability at least 1 - 6,
T
E Es Ey .0) A.(TM,
32
Σ
max (e(0) log [ + 72 logg
tST
Proof. By Assumption 6, we have T TM, o for all and t, e [T]. denot Té Tas, for any t. By the exponential weight update, for any 6,
T
(e(d'l)) (Deld', .)) (((TM,,)
(A) A.(T,))
log
ar(o)a (A.0) (TT)))))
0T
[=1
T
< 16 pr log O
gelob ())((() -
(((T,, o))²
IST
16
1=1
Rearranging and summing over d:
Egrup Egrna
A(d''))
1 -)
16
< 16
Σ
max Pt (6) log //.
(20)
KT
Define
X, Pegnpp Eug (-)0) AA( ()) (T(T
Y, Bappi By (((l))
(A. x) (T o))
By Assumption 6 we have Re[Vi] & [x( By Jensen's inequality, [X & 4B²HE s
4 4B² HE, (X.). Invoking Lemma 17 and using Eq. (20) give
T
1 1 }1)
x
X
+ 36 (ogg(1()) & 16 Σ
max (c( log / + 36 log (1/6).
TST
proving the desired inequality.
Lemma 27. With probability least 1 6,
Earp, (A(()) +) - A.(TM.
(Fr(do:) - Fe(er+1) - Bregg, (6 pt+1)) + (log" ((
23

---

Published as a conference paper at ICLR 2026
Proof. By Assumption 6, we have TM @ TM, o for all and all t' E [T]. We denote To Tas, for any t.
Bg [L(( Eg pe (o 6) - B (10) ( ,]]]
= -Erppi Ar ()) A.(To, Ø) (10)) - A.(To, 0))]
Combining this with Lemmaa 25, we get
T
E Egppp ()) - (.(To,))
log +
1
(pr, be) + be(00) F((dor) Fe(p(+1) Bregz, (ōør (
T
O (log(1/6)
Bap By (x)) (dl A.(TT,)))
1=1
T
<
(pr, b1) + bb((0") + Fe(d - Fe(pe+1) - Breg (6p (60.:PPtt)) (pt.:)t)))
(log ((01/)) + 32 Σ
max
(e( log (+)
(by Lemma 26 and the value of y)
1ST
Note that
32 log +
Σ
max (o( log Σ 1T
pi(0) + D (p(()) max Po(
(p:(0) - max (b)]
32 log ①
Σ
PI(() + Σ pc(0)
pr(
1=2
1 T
(pt bt)
2
t=1
and
maX Po( (
max Po(
Σ br(0") Olog (1))
max Ps (x))
max Po(o")
< Olog (b))
1 In
(1 a-xShh
max, max P=(0-)
< 0 (log² (
Combining inequalities above proves the lemma.
24

---

Published as a conference paper at ICLR 2026
G OMITTED DETAILS IN SECTION 4
We define batched version of Algorithm I in Algorithm 4. When the batch size 1, it is exactly Algorithm 1. One can also think of Algorithm 4 as a special case of Algorithm where POSTERIORUPDATE makes a real update only when t kT for k 1, .,..., and keeps P++1 P otherwise.
Algorithm 4 General Batched Framework
Input: Partition set and its union V/ (defined in Section 2.1). Batch size т. (i()) = |/ Vo E Φ for k 2, ................................ ... K do
Set Pk, P% as the solution of the following minimax optimization (defined in Eq. (2)):
min max PεA(II) vEA(V)
AIR (p, Pk).
(21)
Execute nu in rounds & {(k 1)T + I,... KT} = In and receive observations (ot)tEI.
Update Px+1 POSTERIORUPPATEE(N Phs The (0t)1ET,)-
(22)
G.1 ASSUMPTION REDUCTIONS
Proof of Lemma 8, In the stochastic setting, by Assumption we have a) = Q" ( az M) and fo(s) V*; M) for any M Φ. Hence
A. (1b on)] = MM (Sn, an) - Th - (o(hht)
= F. M Q"((sn ani M) rh - V (sn+1: M)] = 0.
In the hybrid setting, we have by Assumption 2 and Assumption 3 that fo a; R) (** a; (P, R)) and (s; R) = (s; ((: (P, R)) for any P E ø. Hence, for any [d]. defining H' such that (s, a) a)s,a)j, we have for (P,R) E Φ.
ET.(P.M (Cx((OO))) = (f ap; R) R'(s,, an) (s R']l
-QT (sh, abi (P. R')) - R' R'(s, a) - (sn+1: (P)R))) = 0.
Finally, note that in the stochastic setting Mt = M and the hybrid setting P. = p*, so the additional assumption always holds.
Proof of Lemma 12. In the stochastic setting, with Assumption and the Bellman completeness
assumption (Definition 9), for any M = (P, R), we define TM E t as the &' such that
(s, a) = R(s, a) + Exn-r((aaa(((()))
By Definition 9, such o' always exists.
In the hybrid setting, with Assumption 2, Assumption 3 and Assumption 4 and the Bellman com- pleteness assumption (Definition 10), for any (P. R), we define Tar E to be the ø' such that Te ne and for all R.
R(s, a) + Ev Po
By Definition 10, such ø' always exists.
Below, with a slight overload notation, we denote in the hybrid setting fo an) e B as the vector (fo(sn, an; (e)) and fo (s1+1) Rd as the vector Eawas( *xa1) [[ a; ee4)) Furthermore, we use the notation yr, to denote yy E I in the stochastic setting, and (ps,, a;) Rd in the hybrid setting.
25

---

Published as a conference paper at ICLR 2026
Then we have by our choice of En:
E [En(d', dh; on) - En (Tard, 0;; on)]
E [llfor an) V/ fa(sn+1)l1 (s)h yh fs
-BRM (on an) (T ]}
+ +2. BT. Kf (sh, an) - T an), (TNoolsh yh - -f((snt)))
= =ET. [1for an) - (TMO(SH, a=)
(23)
where the last line follows from ET. [ub. + fa(sn+1)] [Tuo an) by definition of Tar On the other hand,
ET.M
(E:(d'.o:on)) En(TMM o0; on))
= - (11,
sa(sn+ Il (sn, an) - y/ - fo(sh+ (313)+
= =E (fo. an) (TMOlSh. an), f and + (sn, an) - 2yn - 2ff(
- <T [1.for (sh, an) (T an)l"
where 8² in the stochastic setting and B² d in the hybrid setting. Combining both finishes the proof.
G.2 BOUNDS ON Est
With the specific form of divergence
(wllp))) = Eo
KL (-IT,)))), + Eopu D [01())
(24)
the estimation term in Eq. (6) for an epoch algorithm with epoch length r' and K epochs is given by Lemma 28. Est in Eq. (6) can be written as
(2(0011, p((0))
T
Est Σ E Ep Bo-
log
E Carpp,Ernee
D (b
(25)
Proof of Lemma 28. From the definition of divergence in Eq. (24) and Eq. (25), let dør E A(Φ) be the Kronecker delta function centered at Φ² Then
Est
log
()()))) +
D (ollaM))
1=1
Earn Bow
KKL (dor, (+ 0))]
Σ Egr E M.( log
E Eg E Egrops D (((()
(26)
()()
where the first equality uses the fact that for any p.
o), (re) (v,v)) EM KL ()) (1) o))]
26

---

Published as a conference paper at ICLR 2026
Proof of Theorem 7. With abuse of notation, we use Pt, Mt Pt to denote the pk. Pk. Ps: where & is the epoch where episode lies. We start from the estimation term in Eq. (25) using the definition of D:
(u(o0(110) De(()*)
}
T
H
Est
Bacp BowM(())
log
E Enco Boupe
max JE[N
E Me (()())))))))
B
1=1
4=1
MR((s (TT Pk((*))
E Bappp
Σ Mow
log
DEIx
K
H
Σ
TE [Cn (0: on on)
+
Earpp Ed
max JEIN
1
H
HEI
Applying Lemma with F((p) KL(A, (vk) ( (Tk 0z)) for t E Is. we get
K
log (V(001T
}]
E Est < E
E
Encope
Σ
+ +0 (Nlog((01)23
(x((
AEI
(pH:1(0)) )
1
log uk (N((t))T.
(L(p,,,,, (uk) 01)) log
I=
K
"Me(tb" (TE,)) + log Pk((tt)
Pk+I(10*)
+ +0 ( ( )))]
< E
log
V (Tk, 01)
A= 1 1
+ (N [N (og(()))77)
S r log
P1 (1(())
= 0 log (1)TT))
Proof of Theorem 11. We start from the estimation term in Eq. (25), using the definition of D:
T
log
)
Est
E E,
E Mam
pr(0*)
H
+
B Exppe Egpeps
Σ Lh
BE..M (e, on) CT
Applying Lemma 27 with Fr(p) = KLLO, (vr) (- or)), we gett
log (T,
pr(0t) ]
Est
<
E
Σ
E pm Bow
+ +0 (log* |&b)
12( ( 1n)..))) KL(pt41, (v)) 0x)) log
log
(p
T
( pe((t)) )
<
log
+ (log² ( = o (log² (Φ))
27

---

Published as a conference paper at ICLR 2026
H RELATING dig-dec TO EXISTING COMPLEXITIES IN THE STOCHASTIC SETTING
H.1 SUPPORTING LEMMAS
Lemma 29. Suppose that (M, b) satisfy Assumption 5 with estimation function Eu(ó; 0h) fo(8n, (+) - Th Lo (8h+1). Furthermore, assume that (M, ②) is Bellman complete (Definition 9). Then Assumption 6 holds with En( Φ; on) (fo (8h: an) Th (0 1)² and
dig-dec,, T. < dig-dec, D.D..
Proof. It suffices to show that (oll S (0ll M) for any n,, b, M:
H
1
D 5q
(0ll =
E
M
(En o; - En (TM di on)l
B²H
h=1
H
E E..
[Fo(sh)
- ST an))²
B
H
h=l
(by the same calculation as Eq. (23))
H
T.. [fo(sn, [TuO(SH, an)))
(Jensen's 's inequality)
B²H
hml
H
(E [fo(Sh, ax) - Th - -o(())+)))
B
h=1
= (oll
H.2 RELATING dig-dec o-dec
Proof of Theorem 13. In the stochastic setting, by definition,
dig-dec
4D
min PEA(H) PEA(T) NEA(M)
E BRNDEMMN VM((TM) VT)(T) (i (KL(vx(-1z,))
1
E
D [6)))1)
1
and
o-dec
4.D D.D
max min max EM Vo(TT) - VNs(T) - (61111) (
PEA(O) PEA(I) (EA(M)
17
For any we have
Eg Ex-pEMse (Tr(TTN)- VM((T) B (L((x(-IT,0),p)) 1 -1 Esmp DD' [6n)1n)
17
EM (T((TM) - (T(T) (K((U)))) P)
1
Boo (KL (T, vz))
11
terml
+ ErraEEss Egrp
Va(TT)) - VM( 17
To bound terml, observe that
EM [TN(( Egg [Vo(TT))
28

---

Published as a conference paper at ICLR 2026
Thus,
terml Eg
B [V((T))] Eg ( (K6 S
(Lemma 19)
This implies
dig-dec,, #.D
S1 + max min max Ba PEA(T) (EA(M)
Bas Bapup VØ(TØ) - -VM(TT) D (oll
1 "
B (LL ub))
Vo(TT) - VM((T) 1 (0)lMM)
11 + max min max Ba Bepup PEA(S) PEA(T) (EA(M)
o-dec, 0.D
H.3 RELATING dig-dec TO BILINEAR RANK
Bilinear rank is complexity measure proposed in IDKL++11.. is defined as the following.
Assumption 7 (Bilinear class [DKL 21]). model class M and its associated & satisfying As- sumption is a bilinear class with rank d if there exists functions Xn. + x M - Rd and W₁. & M Rd for all h [H] such that
1. For M E c. holds that Wa (6; M) = O. 2. For any & 4 and any M M,
(L()=) - VM((T)) S Σ (x)(); Wa M))I
3. For every policy there exists an estimation policy est Also, there exists finncp Ln de O R such that for any d', and any M M,
(Xx(d: M), W (0; MY
x M
[e ow)]
where On = (Sh, ah. The 81.+1) ) and x on nett denotes a policy that plays π for the first steps and plays policy ost at the h-th step.
We call an on-policy bilinear class est n for all a E II, and otherwise an off-policy bilinear class. As in prior work [DKL+21, FKQR21], for the off-policy case, assume [Al is finite, and ast is always (AA). We denote by T the policy that in every step L,...,EE H chooses π with probability
and chooses rh with probability ğt
Lemma 30. Bilinear classes (Assumption 7) satisfy Assumption 5.
Proof of Lemma 30. For any d' E t and any (M, 6) such that M E á.
R wa (e [n)] = (d'; M), Wa M)
(by Assumption 7.3)
0.
(by Assumption 7.1 and that M E ()
Lemma 31. Let (M, ②) be bilinear class (Assumption 7). Then
dig- D.D.. < O2B2H22d in the on-policy case.
dig- dec, D,D., < H²H in the off-policy case.
Proof of Lemma 31. We first use Theorem 13 to bound dig-dec,
S.D,, o. 0,D, by o-dec, 17, and then
Lemma 32 relate o-dec & D.r bilinear rank.
29

---

Published as a conference paper at ICLR 2026
Lemma 32 (Proposition 2.2 of (FGQ+231). Let (M, 1) be bilinear class (Assumption 7). Then
o-dec,
Dw v O(B2 in the on-policy case; n 9. a,D < BBddd in the off-policy case."
o-dec,
H.4 RELATING dig-de dec TO BELLMAN-ELUDER DIMENSION
Lemma 33. Let (o ok) = fa(sh: an) rh fo(sht1), and let Dav be defined with respect to this li. Then
the Q-type Bellman-eluder dimension of (M, ②) is bounded by d, then dig- dig-dec, D.D,, < ((H))) If the V-type Bellman-eluder dimension of (M, ②) is bounded by d, then dig dig- Dur - 0(H / Aln)
Proof. We first consider the Q-type setting. Define gn ( o; M) BFV, (F 0n)). For fixed M, we have by the AM-GM inequality
A 4
gh(db o; M)
Egep (g, 05 M)] S
+
Eddp [an 0z M)
E Bar-p [9h (0', d; M)2]
X
for any 0, implying that
o-dec, Dw
"
= mmx max Banp Mon
Vo(To)- - VVs(TT
B (6:
nB²H
< max max Eg D
Vo(TT) (ar(TT)
M M (n((::o)))) 2
11B211 H
H
max max Be
gh gr dh: M)
Σ
(ol db M2²
BB² H
h=1
B
H
(o, di M)²
max max
E
4
E Bag ( (6,0 di M)
The rest of the proof goes through standard steps. First, bound Egpup Egrnalan (d' (()))] by the dixagreement coefficient of the function class Fm = (So Tws : @ E )) where (Tar (h,)) e R(s, a) +Eg-P((-ss.a) [f(s)) under the probability measure Egnup adf (Lemma E.2 of [FKQR21]). Taking a maximum over p. this can be further bounded by the distributional eluder dimension of
())
FM over the probability measure space Da.M = (df o E Φ)) (Lemma 6. of [FKQR21] and Theorem 2.10 of [FRSLX21]), which equivalent to the Q-rype Bellman-eluder dimension in M defined in [JLM21]. This then allows to bound o-dec & D... < nd H2, where d is the maximum Q-type Bellman-eluder dimension over all possible M.
Next, we consider the V-type setting. Define gn (Φ', 00 M) o M(fn (0; on)]. For a fixed M, we have by the AM-GM inequality
À Egpip (g, di M) < 1
gn (n 0: 2) ES'~p (0', di M)
Egg
+ X
Eanp [gn d;
'In [FGQ* + 23), the bounds on o-dec,) d Dao have different scaling of B, H than ours. This is because their average estimation error does not involve the normalization factor B like ours (Theorem 7). We normalize Ti., to keep the two information gain terms in Dig- Dig-DEC of the same unit. Equivalently, one can view our scaled version of theirs.
30

---

Published as a conference paper at ICLR 2026
for any À > O. Below, let x² be the policy that in every step h, with probability 1 executes policy π, and with probability a executes uni Then we have H
o-dec, D..
max min max BappEgr (((T))-Vu(T) Vv((T) 11 H
(ET.M (d((oon)))
0 P
Σ max max E By Banp EM Vo(To) Vo(To)-Va(TT))
B (d on))
nBa H
1
max max EE So MNN
Vo(To) VVM(TT)
[ on To.M [ex(
nB3H
3H A
a max max Bp D M
(. B1
9 o. M)2
P
gh di M)
4a
max max
Edp
E Eggiop 99h (2) 6; M)²
where the second inequality is because with probability at least (1 - 11
A the
M
policy z.. chooses the same actions in steps I.....h as the policy Tेr on Te. Similar the Q-type analysis, the last expression can be related V-type Bellman-eluder dimension (notice that the definition of Oh. is different for Q-type and V-type.. This gives o-dec o-dec..I. D.D... S a n
O(v Dd Aln) by choosing the optimal a.
Finally, using Theorem 13 finishes the proof.
H.5 RELATING dig-dec TO COVERABILITY UNDER BELLMAN COMPLETENESS
Lemma 34. Let (M, 4) be Bellman complete (Definition 9), and suppose the coverability of every
model in M is bounded by d. Then it holds that o-dec, Dr S ndHl where Deg is defined with En o: on) = (for an) Th fo(sn+1))
Proof. For M (P, R). define
(s, a, Φ; M) fols, R(s, a) EynPtyta) fo(s, (T
do.M( (s.a) a) Esprup ( (s,
By the AM-GM inequality, for any X >
E Ex [gh (Sh, ag. d: M)]
= EgnpE (aa) on lon (s, a, Φ; M)]
M (8,
as
do (s,a)
A d M (s)
< EEg (e M
do. (s,a)2
df Fa (s,a)2
Egpup Σ
Ber
BFo [gn(on, an, d, M)
(27)
do. (s,a)
Note that
BFo.d (8n, an, 0ū M)]
Egep (Vo(TT) VM((TT))
31

---

Published as a conference paper at ICLR 2026
and by the same calculation Eq. (23), have
E ET
[gn On, 9, M)
Σ B M (En(d', 23
En (TM 0z D'a (ø]
B
B
By the definition of o-dec and combining the inequalities above,
o-dec, D.D
max min max Ba Earp Vo(TTO) Vis(TT) _ D (1llM))
0
P
1)
DD (0l1ar)
max max Eyy up Bopp E
Vi (T(O VM((TO)
P
1)
11
max max Ey Bp E
BT
99 (8p, an Φ3 x;M
Σ h=1
E
E M [on(sp. an Q, M)
BB
h=
nB
H
To.
(s,a)²
max max LE M M~ Boup
h
(by Eq. (27))
dh
(s,a)
A=1
8,0
Let dh be any occupancy measure over layer that depends on P. Then
dhe.' (s, a)2
T. (s, ((
(s,
E Egup
Σ
= Edprup
(
(s
s.a
s,a
(s,
max (s,a) 8,0,5 M4 (s,a)
(s,a)
< Eppu
(s,
J..P (s,a) max 4
M (s,
8.0,5
M (s.a)
Th. (s,a)
max 8,0,8 / (s,
df (s,a) (.,(
We let Uh be the minimizer of max
The coverability in MDP M is defined as
(s.a) [3FB+23]. Combining the inequalities proves o-dec D. S ndB 112
min, a h 2 (s,a)
32

---

Published as a conference paper at ICLR 2026
1 RElATING dig-dec TO EXISTING COMPLEXITIES IN THE HYBRID SETTING
1.1 SUPPORTING LEMMAS
Lemma 35. Let g: +b [0,G] Gl. For U, E ( we have
Ex-olg()) I 31 3LEn)llg()]] + +G (V)))))
where Di is the Hellinger distance.
Proof.
[B@ [0()]]
Bowe [g(
-(o(o))((o))
(p(0) - v(d))²
V Σ (p(0) + =(0))((6)2
Σ
p(0) + v(6)
E [ + Baw [o( 1 Da(l,p)
G
(28)
2
where
Da(k,p) = Σ (0(0) 2())2²
p()) + m())
is the triangular discrimination. We can further bound as
DA(U, p) = Σ (0(0) v()))² p( + v())
Σ (Ve(o) vu(o))((VP()) vo())² $2D((v.p). p(6) +v()
Using this in Eq. (28) and rearranging gives the desired incquality.
Lemma 36. Suppose that (M, b) satisfy Assumption 5 with estimation function &g (d; on); [o(s,, On; eÿ) - (psh, T e; fa(snt1eez) Farthermore, assume that (M, 1) is Bellman com- plete (Definition 10). Then Assumption holds with En(d' 0z;0) Σ}=ı (Sh, (8h, Oni ez) spsn,, an) e; - fo()n+1;e)))² and
dig- dig-dec D.Dm < dig-dec D.D.,
Proof. The proof similar to that in the stochastic setting (Lemma 29).
Lemma 37. Under Assumption and Assumption 4, Pf d. then they share the same d H dimensional vector:
E [p((h,
anll hE[H]
(ETT..P' [p[(n, an)! hE(H]
Proof. Given linear reward with known feature (Assumption 4), we have R(sh, as) sp( (88h, ax) 0g ()) where y is known feature. For any P, R, n, we have
VP,R(=) = Σ TT.P (n(ss,
an) (n))))
Fix a ó and consider P, Pr E Φ. By Assumption 4, Vp,R(Ts) = VP)R(TT)) for any R. For each h, by instantiating 0, (R) as all basis vectors in the d dimensional space, prove that P (p(s)) F [yp(8,, an),) for any h E [M] and any j [d].
33

---

Published as a conference paper at ICLR 2026
Definition 38. We define several quantities that will be reused in Appendix 1.2 for hybrid bilinear classes and Appendix 1.3 for coverable MDPs. We fix a E [0, 1]. and define x as the policy that in 3 and chooses unif (A) with probability We also fix D. which will be instantiated as Dav and Dag in later subsections.
every step h 1, 2, ..... H chooses with probability
a
H'
With them, we define (with M = ())
TermA "1 (v)(v)
EMs Bar Volu((T)) VAs(TT) 1 D (0l)
9nj
2
TermB " (DD(v) = 6v 6vdH 3 3E (iR (Vo,n(TO) (RR((T))
EM Barw
D (oll
9n
Term
1 " (.P((v) Dee Var( - VoRR(TT)) 1 -Eona((Hyy) 17
2 D (d))MM)
(00()))))
9r)
Lemma 39.
min max AIR v)) S max TermA (PP(v) max Term D.D (v))
Proof.
AIR, & (p.u:p)
1
D [
B )
VM((T)) - (T)
BowM() (-
(T,
17
17
Be you
Vxr(T*) - VT(
[KL (us BowM(-Im
[b)]
-
1
Epup
(T((Il
-
1 KL (up. 0)
7)
1)
"
1
VMr(T*) - VM((T)
(o
[KL. (. 0), Ub)
17
1
Exnn (D" [0([))))]]
+
2
Dig (US,,)) p)
- KL KL (vbi
(Lemma 35)
31
31)
VaLa(T)) VTr(T)
T T (1)
S Ban Bane
9n
Vo.R(TT) 1
2 2D [d((a)))))] 9v)
+ EErppl ( ) VM((T))
[6] -Bo (v 0),
1)
We have min, max, AIR, (p, p) = max, min, AIR, (p. p) because AIR is convex in p and concave in v. After the min-max swap, for each v, we choose p to be such that ~ p equivalent to first sampling ø' ~ v and then setting = Tg. This gives
min max AI, (p,up))
< max Ey EM Exree (VLA(TT) - -Va (TT)
D (0)lM)
91
+ (M [M((T')- - -VoLn(TT)
1 Boone((lng) (KL(vo((TT,)))
0), o), 2 = (6ll
911
S max TermA R.D (v) + max Term n
Lemma 40.
Term P()) < OljdH + a) + TermB (PP))
Proof. By Lemma 37 we can define with any P E Φ.
xx E
[ep(sh, aw))
34

---

Published as a conference paper at ICLR 2026
Furthermore, define
X (X)(m) e RaR,
((R) (0n(R) (R)) TRoH.
With this, we have
B Baa (TT(TT) - Vo,n(
Eo E (o,)( EONyER (o.n(TT))
[(()) (ERNe(-10) [0(R)] - En ((RR))
I Bowy [1(()) |R [0(R)] - ER |0 R) s3,
(E, = Exiiv [x())X(0)T)
Edivs [1x 1 Egwn E 1m)((110) [0(R) ER [8(R)]]] x
-VHH
Bapwer (R( (0(R) X (x (0(:)))
3V
E ExinyEE (B(r)))))o(11) [VP.R(TT)))]] (P, (Vap:/oWWPPPPReea )1
Div1
3VdH
Exinn (X()) En (4) [[R)] ((r (()))())))
(
Div2
+ 3 ExrayEer
(X(d') ER [0(R)) ('d')TERo
Eyr (V)
(29)
Div3
For any observation (81, (s,, 8n,
"an""""...,,,,,,,".. an, = = The have
(B(P,R)-u(11)) (Vr,n(TT)) () Vr. )]]"
Divl= = Eggin E
< 2E ~o Exba
(E(P))0)~)(1)) [V Esp. [VP }])² + Sa²
(B(P.M)=((0)) Bow [r(O)]] E (BomM.n(lng)) I(ol)) + Sa²
2Ey
(Bonu [F(o)] - Bowg (m(o))) }
27
+ Saz
27
< 2B ~e Eeprav
Σ [u(obo, mz) - v(o/TT))))
+ 8a²
EEy Enprar
Div (vo(:1d) T&)) 1o v-((1==))) + 8
< SE wy E Esru
KL (1o(-10, TB) )o [o( + 8a²
SE Ense Bor
KL (1g (1 [2)) Sa2.
On the other hand
Div2 = Ey ou Born (x(6')) E [0(R) E o) (V..((T)))) "]
Eye Barw
(E (V ((P.)))0(1)) (Vr.((T>)))
Ey Ee Be (FFP))o((1)) (Vorn(ta)-VvRRRnn
- VVR
E RY-0 (Vor
V).
35

---

Published as a conference paper at ICLR 2026
Similarly,
Div3 Bow (x(6') ER [0(R)] E [p ]
Bo'ny Boru
(Eno [V - (( [V.n((=))))
S E P,Rw (Va. ((TT) (D,R(=T)))
Combining these equations back Eq. (29) and using the definition of Term P P(()), we have
Term TermC,,DA (v))
$ 31/ To Bar M(
KI. (up(1122, vb) + Sa²
+ 6VdH 3R (P,R)
(Vo.R(TT) - Vp)n(T=))))
1 BM
[L (vol ( o), ub) 2
D (0)l
1
9n
O (ndH a) + 6v dH
3E B (Vo. (T,n(T+)))²
2
D 2 (0l1ar))
911
O (idN + a) + (
I.2 RELATING dec TO HYBRID BILINEAR RANK
Assumption 8 (Hybrid bilinear class [LWZ25]). A model class M and its associated tb satisfying
Assumption 3 is hybrid bilinear class with rank d there exists functions X $ Rd and Wa 1 x R x P > IRd for all h E [H] such that
1. For any M = (P, E d. it holds that Wa(6, Rt; = 0 for any it E R.
2. For any & E 4 and any (P M.
(o.u(To) VP,N(TT) S Σ (.,
3. For every policy there exists an estimation policy ost Also, there exists discrepancy such that for any &', & and any M (P, R) E M.
En tb R
IXx,'' P), W.(6 R. P)) = B on a
(d, R; R.)n)]
where On = (Sh an. The S141)) and x on rst denotes a policy that plays π for the first h steps and plays policy n est at the h-th step.
We call an on-policy bilinear class if est = for all π E II, and otherwise an off-policy bilinear class. We denote by T the policy that in every step h 1,..., H chooses with probability and chooses est with probability a
Lemma 41. Hybrid bilinear classes (Assumption 8) with known-feature linear reward (Assumption 4) satisfy Assumption 5 with N = d.
Proof. With the estimation function (, R; on) defined in Assumption 8, we define for j [d].
En on), (x(
where ey reward represents the reward function defined R(s,a) ((8,,) ()),
36

---

Published as a conference paper at ICLR 2026
For any d' E d and any M (P, E
E Tonnn ,P' (0:
1nt [ln 05;
(Xalld'; P), (1, ez P))
(by Assumption 8.3)
O.
(by Assumption 8.1)
Lemma 42 (Lemma 20 of [LW725]]. Lei (M, Φ) be a hybrid bilinear class (Assumption 8). Then
max, TermA, Q.D "aarmA (v) - ((B2H)d)) in the on-policy case.
max, TermA D. (p) s O + (n//o)) in the off-policy case."
Lemma 43. Let (M, b) be a hybrid bilinear class (Assumption 8). Then
max, TermB 4: D. (v) 2 (
in the on-policy case.
". max, TermB D_ D.() < ((BP11B8n)))))) in the off-policy case.
Proof. From the definition of hybrid bilinear class in Assumption 8, we have
(r.
(Vo.n(TTo) Vr,,((=s))
27
(ill,.)), Σ
< Ee
11
Σ E
Wh
Define Σn,p = Eggae (x P))n (c: P) We have
E (Xn(d: (n R; PW}
$ Edn 11(xn P), Wo R: P)D]
[IXa(or S I Boww [1 R; P)I En.P
Bonn
V
de dBpnoeBrr (E P (en(o,
R;on)] 27 g).
(Assumption 8)
Thus,
E Eg (( (Vo.n(TT)
Vr.n(TT)))
H Er
(ETW rey (ello, 27
"As in Footnote the bounds different from [1.7725]ss adopt different scaling.
37

---

Published as a conference paper at ICLR 2026
(1) In the on-policy case, we have 0 and
6/ 33
R(p,R) RCP (VoL)(TT))
2
EBg ExswuBon Dav (01)Ar)
9r)
11
s 6
3d H²
V (Brn
(BTOr.P (es R: on)))
(e:(O,
h=1
2
Bepnu LPP
Σ BFaer [(n(d)on)))))
9n
H
h=1
d8 $0(dà H3
00
1
E (P.
V Bi
(BAOr [enlØ Ri o
43
h=1
2
(P
(RTON [enl0, R; on))
9n
<o 8 112
7
-0 ((BP(((())))
(choosing optimal 3)
(2) For the off-policy case, we have
vv
(P (VoLA(TO) (T)
Ed' Eas 9n
2
Dav (oll
The
< 6
dā 2²
E Ry
( Bere
E
(0, R; R:ol))
h=1
2
E Ex Ey BiP
9n H
H
00
+
E(P.R) ~0 V R Barnu
(B [C, R; Rio)l)
43
h=1
2
E E Bow ( (DTTOONNEE ,P [lalo R: ow))) )²
3H
9mB²H
H
1=1
so
11
nB² H2
o (1/)))/
(with the optimal 3)
a;32
where the second-to-last inequality is because with probability (1 4 n h- chooses the policy Tay of 7
policy T
3H
est
Lemma 44. Let (M, ②) be a hybrid bilinear class (Assumption 8). Then
;ig-dec, I.D.. <0 B2 dm + (B²H+&n') 8) in the on-policy case;
dig-dec, @ DDD <0 0
B2H (1FPd)+ in the off-policy case.
Proof. This can be obtained by directly combining Lemma 39, Lemma 40, Lemma 42, Lemma 43. In the on-policy case,
dig-dec DDD
In the off- tificpoicy case,
dig-dec D.Dm (a (B
=0
(B² (
(with optimal a)
38

---

Published as a conference paper at ICLR 2026
1.3 RELATING dig-dec TO COVERABILITY UNDER BELLMAN COMPLETENESS
Lemma 45. For hybrid MDPs with Bellman completeness and coverability bounded by d, it holds that
TermA max TermA, (v) 0 (ndB²
Proof. For M = (P, R), define
gh(8, a, R, P) [o(s, R) R(s,a) Bx=p((aaa)lals R)), d (s,0) Exprer [ch (x.
By the AM-GM inequality, for any X > 0.
Es (sh, an, 0; Ri P)] Eg (sa))d P (sn a, o: R,R)
d (8,a)
-Egny (s,a
9h (n a, o; P)
d P (s)
A d os)
S (E
+ a9
4 dh as
Me as,
Σ 5,
+ x
[yn(on, un, 6, R, P)
(30)
do (s)
Note that
H
E Egp BFo. (8h, an, Φ: R, P)] = Egino (Vo,e(TT) - Vas(
h=1
and
1
B. [gn(sn, an, 05 R, 2)
B [gh, an, ej, ej, 2)
A=
E B (Jo(Sh an: spsh, ( - - -Eg=:((aao(lbb(::]]]]]
E (fo(sh) STarossn, ani en)))))
1=
PP [1lo(sh) (Th
Σ P. [n d: 0h) En (Tarh, oz)))
(by Eq. (23))
Bd HD M)
(31)
39

---

Published as a conference paper at ICLR 2026
Thus,
TermA, 9.D (v) ?
-EM Ber
(TT - Vir(TT) - -
Di Ded (6)1
11
S Booyy Bare
B [gn B an, d5 R, P)]
Σ h=1
B [gh (Sh, an, db R, P)
BB²H
A=1
nB2H H EM EM Bebrs
C (s, a)
(by Eq. (30))
(s, a)
Let 1 P be any occupancy measure over layer h that depends on P. Then
dh (s,a)²
(s. (8.0))
(s..)(
E anvv
Σ
E
dx
(8,
(8,0) 8,0
1 (s)
5,a
(s, (
dh (s.
max
dn
P.P
(s,
3,0
/ (s.a)
2,0
P. (8,0) max
Σ M (8, 8,0
8,0,7
11 (s,
dr. (s,a)
max
M (s,a)
(32)
d (s.a)
We let 2he be the minimizer of max
The coverability MDP M is defined
K (s.a)
(o,0) ag (s.a)
[XB 233. Combining the inequalities proves TermA 0.Dm PM <
as min, max
O (ndB2H²)
Lemma 46. For hybrid MDPs with Bellman completeness and coverability bounded by d, it holds that
B0 D.D P. (O(BB))m))))
max TermB
Proof. By definition,
TermB
BarmBB.a(e Pa(p) = GvdH Bi (Vo, - Vr,R(TT))
9n Ey Ear-EErrar E [ (0))
Define
9h(8, a, 0; R. P) = =s; R)) R(s,a) a) - -Bs-P((sa)UO(s' R)),
dh (s, Eggne [amto (s, a)
40

---

Published as a conference paper at ICLR 2026
We have
Egga -Vo.n(ro)-Ve..tt)) -VP,n(T)))
H
B (e,a) a. (n P)
h=1
<
H
Bejnee (B,0)add s. [1,n(3, a, sb; R, P)
h=1
thoi (s,
H
E Edpry (s (s
19h (9h a; R.
dh (5, (s,
P..P
H
dh di (s, V ( a R, P1)
d dh (s,
<
H
E Ex (a
h=1
H
dR ( (s (s, o; R, P)3].
(by Eq. (32) and that coverability S d)
Thus,
dHl
3B BE Nw (Vo.n(Ts) - (T,n(T=))²
2
By By WeE
DDa (0llM)
9r
2
d 2
E Eyr (B d;
Es EMrn
D (d)l
9r
h=1
H
d 2
+
E( (V ( [h as, R, PY3]
48
h=1
2
Bay - Eas-u E (e.a)dd wo [gn(s, or R, _)
(Eq. (31))
9nB²H H
0o
d
H2
BB²H H
= = ((
3²
Lemma 47. For hybrid MDPs with Bellman completeness and coverability bounded by d, it holds
that
dig-dec, D,D., p. ( (B
Proof.
This can be obtained by directly combining Lemma 39, Lemma 40, Lemma 45, Lemma 46.
41

---

Published as a conference paper at ICLR 2026
J OMITTED DETAILS IN SECTION 6
J.1 PROOF OF THEOREM 14
In this section, will use Ber(p) to denote Bernoulli distribution with success probability We consider parameters and with < A TpvT S Té- Define p* = + A and
A. Let
H(()) denote the entropy of distribution v. We assume learning rate 1.
Consider a three-arm bandit environment with model class M [ M2] where
Mi = (Ber (p-), Ber ( The reward distribution is Ber (y-) for arm a and Ber (p 1 for arm ag. Arm 0g reward is 0 and with equal probability.
*
M2 (Ber (p*), Ber (p 0.5cc. The reward distribution is Ber (p*) for arm d1 and Ber (p for arm 0g. Arm ag 's reward is 0.5c deterministically.
In this setting, 4 contains two infosets (based on Assumption 1):
Φ1 {(M1, m,)) 2 = (M,))
In the rest of this proof, we compare the optimistic E2D algorithm [FGQ* 223 and our algorithm in this environment.
Optimistic DEC algorithm [FGQ* 23] Given P E A(D), the algorithm chooses action distribu- tion via
Pt = argmin max PampBBrpp EM- VVlas) (ar(a) - (+)))))))) (TA(IT) vEA(V)
(33)
77
where ag is the optimal action of infoset é. In this simple bandit setting, the bilinear divergence and the squared Bellman error coincide with
(e M) = (Ev.MIVoo) r1)² = -
We first consider the divergence term, for action a E {a1, )2). we have EMw (+ll ( (M, (a)) + (o(o))u
VMr, (a))²
(M)) (Mb)))))))))))) A
(34)
For action a = 03. we have
Egrep EM (+] () ( (a) (a) (((o))( VAs, (a))
(35)
Thus, for any and we have
(*)())))) 4(1 p(as)) (p((o))u(Mz) + p((e))u(M)))
EunpE EMs
"
which is monotonically increasing in p(ag).
We then consider the regret term. For any p E A (II), define p I-p(as]: T-p(as) 0) p(aa) < 1.
p(a:)
plaz)
and p ( 1 0) otherwise. For any M E M, when p(as) < we have
Eaup [V)(a)) - Ea-p [V](a)] = Σ
+ plax)VM(as) (p(a) - p(a)) (M
ac (a),ag)
-p(a3)
Σ
+ (
p(aa)
aE(a).02)
5 -p(as)
p(as) (p(ar) + p(az)) p + + Var
(Va((a) 2 p for any M and {az, az), and p(as) 1)
1
Vas(as) =(ass)
2
1
<p(as)
0.5c + A
50,
(c < AsASi 1
2
42

---

Published as a conference paper at ICLR 2026
and when p(as) = 1 also have Ba-p [as Bamp VVs - 0. Thus, for any Pe, v. and p.
Ban EM { (Vo(as) - Var(a)} S Bumppor EMS- (Vo(as) Var(a)).
Combining the discussion of the above two terms, for any Pr. and p. we have
BanpBBppp EM Volas) - Vir(a) - - D S Banp EMw Vol(s) VM (a) "
1 (ollin))
(36)
Given Eq. (36), the minimax solution of Eq. (33) must have (3) for any Pt and any This implies that the optimistic DEC algorithm will never choose and the problem degenerate to standard two-arm bandit, so the policy derived from optimistic DEC objective Eq. (33) must suffer standard regret lower bound IE [Reg(FM-)) )] 2 ((vT) given A θ
Our algorithm Given P1 is a uniform distribution, we consider our first step optimization where
P1 argiiin max Ea B VVr((ar) Vis(a) "j 1 -BwM((10)) [KL(vp(+la,)), pi)l - D
PЕΔ(T) DEA(V)
(37)
Below, we discuss the four terms in Eq. (37).
The Var (am) term For any v, we have EMsw [vr(a)]] = =pt, which is a constant. Therefore, this term be ignored in the objective.
The VM (a) term By direct caleulation, have
Ea [V)( p(az) + p(az) + (p(a1) - p(az)) (v(M2) - v(Mi) A + 0.5p(az)e.
2
(38)
For any p (p(a1), p(az), p(az)), consider p (pla))) plar)-p(az)) .((aa)) By Eq. (38)
have
T. Paw (a) S
Ban Ba ( (v) wEA(V)
(39)
vEA(S)
The Dd [M) term Given Pi is uniform distribution, for action (1,2), from Eq. (34), for any V we have Egpp, E E [ol = 242. For action 3, from Eq. (35), for any v, we
have Egipps EM (o]lM) O. Hence, EaappE EM (6] Note that now this is independent of v, and only related to p(a3) or p(a1) - =(a2)) but not p(a1) or p(a2) individually.
2(1 p(a
The KL term Notice that
vo(- ②1) = Ber (p-), vol- 01) ) = Ber (p+), vol-aa,, = Ber (p"), vol-la2, 62) = Ber (p-).
(-(a)) = Ber (m1),
vo(-laz) = Ber (mz).
where m. = w(0))p= + v(02)p+ and m2 = v( )pt + v(o2)p and it holds that my + m2 1.
Given that KL. (Ber (p) Ber (q)) KL (Ber (1 p), Ber (1 9)), we have
Ba (o-a((a) KL (1)((-la,))
= Ea (L(vo 1). (o(( KL(V
=p(ar)u(0))LL (Ber (p Ber (m) + ((2)) KL (Ber (p+) Ber (mz)) + KL(V,,
+ KL (Ber (p+). Ber (m1)) + ((a)))()))) (Ber (p-) Ber (mz))
+ = (Ko (:la,, Φ), vo(:
(p(0r) + p(az)) (p( JLL (Ber (p-) Ber (m1) + w( (Ber (p*). Ber (m1)))
+ H(a + (1)
(1 - p(aa) (H (Ber(m1)) - IHI (Ber (p+))) + p(a3)(H(v) + KL(vs,P1)
43

---

Published as a conference paper at ICLR 2026
Note that this term is only related to p(as) or p(a1) p(a2), but not p(az) p(az) individually.
Combining terms
Combining the case discussions above, for any p (p(a1),p(az) p((z)) with
ÿ (((=)) Hp(az) p(ai)))(a)) ,p(as)), we have
2
BamplEs -Vi((a) - -Bows((a) (a) 1 Bomun 10 (000010000)1)0)1
max WEA(V)
-Vas(a) - B (KL (1a, p1]
1 Edupp 1D (011N))))]
< max PEA(W)
E EaNpEMIN
17
To calculate the max value of the left-hand-side, consider policy distribution Ps = ( - have
_e, s). We
1 -Vas(a)= - M(a) (v Epspp (D)(((
_
Eaxp, E EMaN
8 --1
((1 8) (H (Ber(m11) H (Ber(p*)) +222)= KL (us. P1) sH()))
2
1)
(40)
where mi
=v(bi>> + v(d2)pt. Define
G(v) = (1 (Br((()))))) + KL (vp, P1) + sH(().
To calculate max, of Eq. (40), we only need to consider min, [G(v)). By setting 11-v(i)) function G is only related to v(01) and we denote it G(v(Φ1)). )). after taking derivative, we have
[-m=
1 m1
u((1)
1 (--((r))
G'((((b)) = (1 - 5) In
(p - -p*)= + log
+ +loog
m1
1 1- ((()))))))))))))))))))))))))((
v(01)
(1-m1 m1
v((1)
(1-v(L))
1 v(O1)
= 3) In
+ log
(I-
+ log
mi
v(Oi)
where my =(01)pp + (1 v(o1))p+ and we use the fact that de((er(p)) In 1_ Note that
dp
when v((n) 2 we have mn = and (² = Thus, 1 is a stationary point. On the other hand, we have GO( = 4(1 -s 2 - s) ) 2 0 and G(v(01)) = G(1 ((1-v(e) (01)) This implies v(ó1) = 1 is the unique minimizer and the minimal value is G(+) = In(2).
2
Thus,
1 1 Baxp, EMNU -Vm(a)= - EowM(a)) KL(us(- P1)] - Banpi (D(()))))) 17
1
max PEA(W)
11
$ sc
(1 - 5) (-H (Ber(p*)) (-H(Ber(p")) )) + 2
ln(2)
2
2
7
1
1
Hl(Ber(p+)) 24 In
(1
8)
+
(41)
2
Note that
H (Ber(p)) 2
KI. Ber Ber())) In2 - 2 Ber( (})
2 In (Ber Ber(H))
(Pinsker's inequality)
2 In2 1542
(KL,(Ber() + A), Ber( s 3A2 2 for A < 1
1
(by the assumption A
16v7 I +
2
Hence, the minimum value of Eq. (41) is achieved at s = 1 when 1 - - 2 0. By the condition 2n 7 S 1, this indeed holds. This means that our algorithm always picks the third arm in the first round. After picking arm ag, the belief of ó will be deterministic, since (Ø (őla3. o) = 0 for any o # o*. This means the algorithm will always choose the optimal action in the following rounds, ensuring that EE [Reg(TM.)) p 1.
44

---

Published as a conference paper at ICLR 2026
K USE OF LARGE LANGUAGE MODELS IN PREPARATION
We did not use large language models at all for this project.
45


Reviews:
[{"review_id": "pUGh5kv5lq", "reviewer": "Reviewer_NZXe", "summary": "This work proposes a new decision-estimation coefficient (DEC) notion, which enables conducting exploration via information gain instead of the optimism principle in a model-free manner. The first benefit of the new DEC notion is the improvement of previous results in cases of bilinear classes or Bellman-complete MDPs with bounded Bellman eluder dimension. The second benefit is that this new DEC notion leads to the first model-free algorithm for MDPs with stochastic transitions and adversarial loss functions in the bandit feedback setting.", "questions": "Please see my questions in the weakness part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. **Novelty**: The proposed new notion seems interesting and fundamental, enabling the exploration solely based on information gain.\n2. **Results**: The model-free algorithm leads to a series of new results in stochastic MDPs, with matched or even improved results. This work also resolves the open problem of previous work for solving MDPs with stochastic transitions and adversarial loss functions in the bandit feedback setting.\n3. **Presentation**: This paper is well-written.", "weaknesses": "If any, I would feel that some parts could be clearer and more thoroughly explained. For instance, from Table 1, I notice that the regret bound of off-policy exploration might be inferior to that of on-policy exploration. Could the authors explain why this happens? \n\nAlso, most previous works for tabular and linear MDPs with adversarial loss functions use occupancy measure (OM)-based or policy optimization (PO)-based methods, both of which are model-based and require to learn the transitions explicitly to construct the loss estimator. Could the authors intuitively explain how to construct the “loss estimator” without explicit learning of transitions?", "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": "mv0vBMS0QT", "reviewer": "Reviewer_L37f", "summary": "This paper introduces a new, model-free complexity measure Dig-DEC (Dual Information Gain Decision-Estimation Coefficient), which removes the optimism-based exploration mechanism (allows adversal setting ) and is upper bounded by optimistic DEC. Then, this work adopts this framework to the stochastic and hybrid adversarial MDP setting and achieves a series of SOTA results with different MDP structures (bilinear classes, Bellman-complete, etc.).", "questions": "Q1: Can this work provide experiments (even simulation experiments) to show the relationship between Dig-DEC and optimistic DEC.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "* This work achieves a series of improved results under the Dig-DEC framework.", "weaknesses": "* Since this work has provided a series of new SOTA results, it would be very helpful to add some discussion and intution after each results or assumption (for example, Assumption 1).", "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": "DwD7o0FgcX", "reviewer": "Reviewer_B9o3", "summary": "This paper positions itself as a bridge between two major approaches : model-based methods (which learn a full world model) and optimistic, model-free methods (which guess the best outcome). Its main contribution is a new, improved framework called Dig-DEC that removes the \"optimism\" mechanism. Instead of blindly chasing high rewards, Dig-DEC drives exploration  by seeking out information that helps it distinguish between different high-level \"theories\" about how the environment works. This shift leads to better performance guarantees in standard settings—improving regret bounds—under certain assumptions.\nIt aims at replacing a simple heuristic (optimism) with a  possibly more fundamental principle (targeted information gain) to solve harder problems more efficiently.", "questions": "- What would be the complexity of the minimal AIR optimisation problem? Can you give approximate solutions at a reasonable complexity? (This is one of the most crucial point that the paper does not discuss...)\n\n- Related to that last point, Im a bit lost with the \"model free learning\" terminology.  I guess for a large part of the community, model free means that you do not have access to the model ( and hence to means) but only to observations.\nWhen solving the optimisation problem, you are not model free? \nSo,  given that you claim that optimism principles should be dropped, a lot more details should be given on how a practical estimation scheme can be leveraged  for your proposal?  The regret bounds are MDPs bound? not RL bounds?\nIn conclusion,  some precisions should be given on what you call (along with other papers) model free learning and more importantly what are the contours of your results...\n\n- In Lemma 12, what does: \"In the stochastic setting, Assumption 1 together with -completeness\" mean?\n\n- It would have been helpful to have a very simple toy example to underline that the assumptions are useful...", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- the paper presents impressive theoretical developments (though I was far from being able to check all the details of the 30 pages of the appendix),\n- the paper introduces Dig-DEC, a new complexity measure for decision-making. By removing the \"optimism\" principle and replacing it with pure \"information gain,\" it provides an interesting exploration driver. \n- The theoretical proof that Dig-DEC is always smaller than or equal to the prior optimistic DEC is a strong, clean result. This gives improved regret bounds but more fundamentally could give new perspectives of what can be done structured MDPs.", "weaknesses": "Implementation challenge\nThe first major challenge lies in the computational feasibility of solving the core minimax optimization (point 2 in the algorithm) at each round. This problem seems exceptionally difficult: the learner must optimize over distributions of policies against an adversary optimizing over distributions of models, with an objective function that involves nested expectations and KL divergences over trajectories. For any non-trivial state space, the policy and model classes are likely to be enormous, making an exact solution intractable. The objective is also non-convex and non-concave in general (?). While the paper provides a theoretical blueprint, it offers no practical implementation or approximation scheme. Bridging this gap would require major algorithmic innovations,\n\n\nAssumptions\n The  core assumptions of the paper present a significant gap between the theory and the reality of most RL problems. The most restrictive assumption is possibly the requirement for a pre-defined, finite partition of the model space into infosets where all models within an infoset share a unique optimal policy and value function (Assumptions 1 & 3). In practice, such a discrete and perfectly aligned partition seems unavailable; the \"optimal policy\" may not be uniquely defined or may change during learning. Furthermore, Assumption 4 (linear rewards with known features) for the hybrid setting is a strong structural limitation, as it assumes the learner has perfect knowledge of the reward representation, which is often the very thing that needs to be learned in adversarial settings.\n\nPresentation\nA major weakness is the presentation. The paper is very difficult to read. Many notions are supposed known to the reader and there is no attempt to aim at a bit of self contained presentation.  For instance, the assumptions 5,6 are difficult to grasp. This makes the contribution of the paper less valuable because more difficult to gauge.\nThe presentation of the assumptions could be done differently by first describing informally the context and main restrictions and then making them mathematically precise.", "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": "OIugFxafBW", "reviewer": "Reviewer_Z8zP", "summary": "The author proposed the information-theoretical notion of complexity and a model-free algorithm for the general decision-making problem with structured observations (DMSO). The proposed Dig-DEC mechanism works seamlessly in both stochastic and adversarial environments (with stochastic transitions and adversarial rewards). It achieves the first model-free regret guarantees with bandit feedback in many general settings, resolving the existing open problem.  Additionally, the proposed approach improves the regret bound for Bellman-Complete MDPs to match classical optimism-based approaches.", "questions": "- What are typical values of $\\log|\\Phi|$ in the examples described in Section 5 (for example, in the case of worst-case finite MDPs)?\n- How is DigDEC connected to a classical DEC in terms of regret lower bounds?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- General framework that covers many existing RL settings and improves upon the existing optimistic DEC bounds.\n- Guarantees for model-free algorithms in adversarial settings.\n- Interesting online learning technique for the posterior update that seems to be of independent interest.", "weaknesses": "- Restrictive linear reward with known feature assumption for an adversarial hybrid setting;", "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)