EUBRL: Epistemic Uncertainty Directed Bayesian Reinforcement Learning
Authors: Jianfei Ma
Wee Sun Lee
Venue: ICLR 2026 Poster (2026)
Keywords: Bayesian RL
epistemic uncertainty
exploration
Primary area: reinforcement learning
TL;DR: A Bayesian RL algorithm that leverages epistemic uncertainty for principled exploration, achieving near-optimal guarantees and strong performance in sparse-reward environments.

Abstract: At the boundary between the known and the unknown, an agent inevitably confronts the dilemma of whether to explore or to exploit. Epistemic uncertainty reflects such boundaries, representing systematic uncertainty due to limited knowledge. In this paper, we propose a Bayesian reinforcement learning (RL) algorithm, $\texttt{EUBRL}$, which leverages epistemic guidance to achieve principled exploration. This guidance adaptively reduces per-step regret arising from estimation errors. We establish nearly minimax-optimal regret and sample complexity guarantees for a class of sufficiently expressive priors in infinite-horizon discounted MDPs. Empirically, we evaluate $\texttt{EUBRL}$ on tasks characterized by sparse rewards, long horizons, and stochasticity. Results demonstrate that $\texttt{EUBRL}$ achieves superior sample efficiency, scalability, and consistency.

Published as a conference paper at ICLR 2026
EUBRL: EPISTEMIC UNCERTAINTY BAYESIAN REINFORCEMENT LEARNING
DIRECTED
Jianfei Ma, Wee Sun Lee
National University of Singapore {ma-i, leews [ @comp nus edu.sg
ABSTRACT
At the boundary between the known and the unknown, an agent inevitably con- fronts the dilemma of whether explore to exploit. Epistemic uncertainty re- flects such boundaries, representing systematic uncertainty due to limited knowl- edge. In this paper, we propose a Bayesian reinforcement learning (RL) algorithm. EUBRL, which leverages epistemic guidance to achieve principled exploration. This guidance adaptively reduces per-step regret arising from estimation errors. We establish nearly minimax-opiin optimall regret and sample complexity guarantees for class of sufficiently expressive priors infinite-horizon discounted MDPs. Empirically, we evaluate EUBRL tasks characterized by sparse rewards, long horizons, and stochasticity. Results demonstrate that EUBRL achieves superior sample efficiency, scalability, and consistency.
INTRODUCTION
In a completely unknown environment, what compels an agent to seek new knowledge? This drive captured by the concept of exploration, which lies at the heart of reinforcement learning, from e-greedy to Boltzmann exploration (Sutton & Barto, 2018), Yet, these heuristics often fall short in more challenging enviromments, particularly those with sparse rewards, long horizons, or stochas- ticity. Epistemic uncertainty (Der Kiureghian & Ditlevsen, 2009) characterizes the degree of un- knownness, providing principled basis for exploration. However, it remains unclear how to most effectively leverage this uncertainty to guide learning.
Bayesian RI (Duff, 2002) provides a framework for modeling a world of uncertainty. An agent seeks to maximize cumulative rewards based on its current belief, interact with the environment, and update that wethof- knowing the true dynamics and rewards. From the agent's perspective, the world is epistemically uncertain. It must balance exploration and exploitation to find a near- optimal solution. By placing a prior over both transitions and rewards, epistemic uncertainty arises from limited data: the less familiar the agent is with region of the environment, the more it is incentivized to explore it. Nonetheless, higher uncertainty also raises the risk of unreliable estimates. A common approach is add the uncertainty
"bonus" directly to the reward, strategy known as optimism in the face of uncertainty (Kolter & Ng (2009); Sorg et al. (2012)). However, even small errors in the reward can propagate into an inaccurate value function, potentially resulting in unnecessary exploration and slower convergence.
When measuring the efficiency of algorithm's exploration, metrics such regret (Lai & Robbins, 1985; Auer et al., 2008) the cumulative difference from the optimal value function-or -or sample complexity (Kakade, 2003)-to00 the number of steps that are not e-optimal are commonly used. An algorithm is said to be minimax-optimal (Lattimore & Hutter, 2012; Dann & Brunskill, 2015) if its bounds match the corresponding lower bound up to logarithmic factors. While previous works based on optimism (Kakade, 2003; Auer et al., 2008; Strehl & Littman, 2008; Kolter & Ng, 2009) or sam- pling (Strens, 2000; Osband et al., 2013) have been shown to achieve strong theoretical guarantees, their of uncertainty quantification and empirical evaluation of exploration capabilities remain limited, leaving room for improvement in practical problems, particularly those requiring sustained and efficient exploration.
In this paper. we propose EUBRL, an Epistemic Uncertainty directed Bayesian RL algorithm for principled exploration. We use probabilistic inference to model epistemic uncertainty as part of the

---

Published as a conference paper at ICLR 2026
agent's objective. This approach guides the agent explore regions with high epistemic uncertainty while mitigating the impact of unreliable reward estimates. Our contributions are both theoretical and empirical:
We prove that EUBRL is nearly minimax-optimal in both regret and sample complexity for infinite-horizon discounted MDPs, with epistemic uncertainty adaptively reducing the per-step regret.
We instantiate prior-dependent bounds and demonstrate their applications using conjugate priors.
We demonstrate that EUBRL excels across diverse tasks with sparse rewards, long horizons, and stochasticity, achieving superior sample efficiency, scalability, and consistency.
To the best of our knowledge, result is the first to achieve nearly minimax-optimal sample complexity in infinite-horizon discounted MDPs, without assuming the existence of a generative model (Gheshlaghi Azar et al., 2013).
2 PRELIMINARY
An infinite-horizon discounted Markov Decision Process (MDP) is defined by tuple M (S, A, p.r,y), where S and A are the state and action spaces. both of finite cardinality, denoted by S and A, respectively, P the transition kernel P(-ss, a), the expected reward function, and 7 E 1) the discount factor. We assume the source distribution of rewards has bounded support in [0, Rmax] A policy π is mapping from states actions, whose performance is measured by the
expected return (s) E
Σ fr((str, o++1)(s: s. The goal is to find the optimal policy 1=0
(s) = arg max, (s), Vs E S, whose value function (s)... We denote the maximum value function as V = I-
Ras and, whenever applicable, Vi := H Rmax for its finite-horizon counterpart.
2.1 BAYESIAN RL
We consider the layes-adaptivv MDP (BAMDP) (Duff, 2002) to model the agent's learning process. Given a prior bg. the uncertainty over both the transitions and rewards- or equivalently, possible MDPs-is explicitly modeled. A policy is Bayes-optimal if it maximizes expected return in the belief-augmented state space (s, b) E S x B, where is a belief over MDPs. Formally, it solves the Bellman optimality equation under the posterior predictive transition model P, and posterior pre- dictive mean reward гy of the corresponding BAMDP. However, this solution requires full Bayesian planning (Poupart et al., 2006; Kolter & Ng, 2009; Sorg et al., 2012), which is computationally expensive and typically intractable because the belief-augmmetted state space can be too large to enumerate, and the belief must be recalculated every time new state is encountered. Consequently, agents generally must approximate Bayes optimality. One simple yet effective alternative is the mean MDP (Kolter Ng, 2009; Sorg et al., 2012), which fixes the belief during planning. This essentially equivalent to an MDP (S, A, Pb, Tb, 7) given a belief b. When indexed by time, b, refers to the posterior given all data up to time t. By solving the corresponding mean MDP, we obtain a policy derived from the subjective value function V and its objective evaluation in the underlying MDP, V Our goal is to find the optimal policy "¹ by repeatedly solving the mean MDP during interaction, alternating between posterior learning and policy optimization.
2.2 METRICS FOR EXPLORATION
We define per-step regret as A, == V*(+t) - 4 (st). Regret and sample complexity are defined from different angles:
Regret
A..
Sample Complexity
1(0, e).
Low regret does not imply low sample complexity, and vice versa. Regret, which is more cost- oriented, focuses on how much you lose while learning, whereas sample complexity cares about learning efficiency, i.e., the number of samples needed learn properly.
2

---

Published as a conference paper at ICLR 2026
A lower bound is best achievable for regret, !
VSAT (1-7)au3
(He et al., 2021), and for sample complex-
ity, 52 (( (11))) log
(Strehl et al., 2009; Lattimore & Hutter, 2012). When an algorithm's up- per bound matches these lower bounds up to logarithmic factors, is considered minimax-optimall it holds only in the asymptotic regime of large I or small e, it is considered nearly minimax-optimal.
METHODOLOGY
3.1 EPISTEMIC UNCERTAINTY
Learning an imperfect model is of epistemic nature, where the uncertainty arises from lack of knowledge and is, in principle, reducible by observing more data. In general, epistemic uncertainty captures the degree of disagreement in the belief-a distribution over model parameters w, e.g. the transition probability vector or the reward location and scale. For example, for transitions, we have: ET(s,a) f o g(Po(s')s [s,a)) Ew))(w) [f g(P(s'sss, a, (s,)))
for some functions f and g that take scalar distribution input. Intuitively, it reflects the likelihoods' deviation from the "average". When f(x) = - x², (()) = Ep(a)) [z]]. it corresponds to the variance Varw~s (E[s'[s, a, w|) (Kendall & Gal, 2017). When f(p) = (p). H() = p. it corre- sponds to mutual information MI(s,a) a) H (Po(s'ss,a) a)) Eu(w) [H (P(s'Is, a, w))] (Hüllermeier & Waegeman, 2021). A similar argument holds for rewards Ex((,, a) by substituting s' with r.
We adopt a generalized formulation of epistemic uncertainty to integrate both sources: Es a) == h(Er(s, ER(s, a))- In this paper, we consider ((z,,) y) ( + vT). where 7) is scaling factor.
3.2 PROBABILISTIC INFERENCE AND EPISTEMIC GUIDANCE
Traditionally, RL aims to maximize cumulative reward. A pivotal question how to account for epistemic uncertainty in this objective to balance exploration and exploitation. One common ap- proach is optimism- However, this be misleading when is uncertain. In this regard, utilize probabilistic infer- ence to model epistemic uncertainty directly in the objective, disentangling exploration and exploita- tion and making it more resilient unreliable reward estimates (see discussion in Appendix A).
methods, modifying rewards with an additive bonus = Tb + byoous
Probabilistic inference has a rich history in decision-makee Levine, 2018). It has been shown that standard RL can be formulated inference problem by introducing a binary "optimality" random variable O
(Todorov, 2008; Toussaint, 2009;
max Ep(r)
log
P P(. 11s), t=
with an exponential transformation P(O, = (118,,a)) & exp (r(st, oz)) and 7 denoting a trajectory.
We introduce the notion of probability of uncertainty, representing the degree of uncertainty, gov- emed by a binary "uncertainty" variable U.. Marginalizing over this variable, we obtain a lower bound on per-step likelihood:
log P (O, = 1| a.) = log Eu, [P(O, = 1|s,,, as U2) [t,, ar]
Ev, [log P(O, = 1|st, az U2) |s,, az]-
Note that since U, is binary, if we adopt the same exponential transformation, which intensifies the higher uncertainty, we obtain the epistemically guided reward:
EUBRL (s, a) (1 P(U 1]s,a)) rs(s, a) P(U 1/s, (s)
rb
Intuitively, when uncertain, EUBRL focuses more on epistemic uncertainty, as an intrinsic reward, encouraging exploration; when confident, it is more committed to exploiting what has been learned. We call this kind of behavior epistemic guidance. The probability uncertainty P(U naturally disentangles the two ends, being more indifferent reward estimates in the early stage and becoming more committed as evidence accumulates. Although its definition can vary, P(U
1[8,a)
s, a) must reflect epistemic uncertainty. For simplicity, we choose P(U = s, where Emax is typically determined by the prior, and adopt the shorthand Py Pu a) henceforth.
Es(a.a) Ens
3

---

Published as a conference paper at ICLR 2026
3.3 ALGORITHM
The full Algorithm 1 is shown below. It alternates between posterior updating and policy learning. The belief update is in closed form due conjugacy. Moreover, both epistemic uncertainty and posterior predictives can be expressed in closed form. Once a belief is updated, we derive the posterior predictive transition model Pa and posterior predictive mean reward rb. from which we construct an MDP M = AS, r 7), where r p is the epistemically guided reward. The MDP solved using value iteration (Sutton & Barto, 2018). For large-scale settings, approximate methods such as tree search may be required (Guez et al., 2012).
Algorithm EUBRL
Imput: prior bu, scaling factor y,. discount factor y horizon H Su ~ P(su)
To f Solve M = (S, Pops Pbo
FUBRL
.7)
for f + to - do
Act: = (*a)
Interact: 5t+1, Tt 7els,)
Update belief: bet1 +- Belief Update(su),,1)
if time to reset then
$1.1
Pso)
end if
time to update policy then
PURRI, T++1 + Solve M = (S,A, Po To. :))
end if end for
Notably, our algorithm is general recipe that depends on the combination of reset and policy update, and generalizes to both infinite-horize discounted MDPs and finite-horizon episodic MDPs. For finite-horizon episodic MDPs, the policy is updated and the episode is reset every H steps. For infinite-horizon discounted MDPs, the policy is updated every step and there is reset.
Unlike prior optimism-based approaches, our method features simplicity, avoiding intricate designs like knowness (Kakade, 2003; Strehl & Littman, 2008; Sorg et al., 2012) and tailored bonuses (Azar et al., 2017: Dann et al., 2019), and can, in principle, work with any Bayesian model. Compared to Bayesian RL (Kolter & Ng, 2009; Sorg et al., 2012), the key difference is our reward formulation.
4 THEORETICAL ANALYSIS
In this section, we aim to answer two key questions: (1) What is the role of epistemic guidance, and (2) How efficient is the exploration for EUBRL. Theoretically, an algorithm is considered ef- ficient in exploration if it achieves sublinear regret or polynomial sample complexity, the latter being known as PAC-MDP (Kakade, 2003; Strehl & Littman, 2008). Many algorithms have been shown to be efficient in exploration. In particular, (He et al., 2021) has shown that achieving nearly for regret possible in infinite-horizon discounted MDPs. However, is not clear whether this holds for sample complexity. We show that EUBRL achieves both nearly minimax- optimal regret and sample complexity, providing insight into how epistemic guidance adaptively re- duces per-step regret. Our analysis builds on the concept of quasi-optimism (Lee & Oh, 2025), which established minimax opttimllt in finite-horizon episodic MDPs--ett its applicability to infinite-horizon MDPs remains unexplored. Unlike finite-horizon episodic MDPs, which feature clear separation into episodes and allow backward induction over horizons, infinite-horizon MDPs are more involved due to the coupling of trajectories and the stationarity of value functions.
miiimmax-optimann
(Ni().)) where (s, a) denotes the number of visits to (s, a) prior the t-th step. Both the transition and reward are estimated using maximum likelihood estimators, corresponding to the empirical means P and f. We then extend and instantiate this framework to the Bayesian setting, deriving prior-dependent bounds for a specific class of priors and examining their applications to commonly used priors'.
We commence our analysis from frequentist perspective, with (,(s,a)
All results presented here remain valid for finite-horizon episodic MDPss
4

---

Published as a conference paper at ICLR 2026
4.1
REGRET DECOMPOSITION
The per-step regret, a central quantity in both regret and sample complexity, can be decomposed as follows:
(s) ( V- (5) (s) V' V'(s)
V*(s)
V
Quasi-optimism
Complexity
Accuracy
Each term is defined by its purpose and consequence: than typically assumed in theoretical works, allowing more relaxed requirements on algorithmic components. Complexity stems from introducing (s(),, an auxiliary value function that ensures quasi-optimism and adapts the previous analysis to our framework. Accuracy reflects the extent to which the agent's 's internal model diverges from the true environment, serving as a key indicator of how effectively an agent explores environment and builds model.
Quasi-optimism is weaker form of optimism
We aim to bound these terms individually. To do we define an auxiliary sequence {Ae
where X E (0. 1). Vt E N. These values, derived from Freedman's inequality (Freedman, 1975) and refined by Lee & Oh (2025), are used to bound quasi-optimism and accuracy. Furthermore, to bound the accuracy term, we require (s()) = O(V))) to ensure the agent's subjective value function remains bounded. Without loss of generality, we set the positive multiplicative constant C' = 1. In
addition, for notational simplicity, we denote 4 == Rm
Consequently, by invoking Corollaries 2-3 and Lemma 14, we bound the terms with respect to the epistemic uncertainty Es, the maximum value function VJ,, and the auxiliary sequence {A combining them yield:
Theorem (Bound of Per-step Regret). For infinite- discounted MDPs, with probability at least 1 8, it holds that for all & E S,t E.N,
)
- 2
-s))) AN (5)
& Vg
( <
1+
where we define the following as Epistemic Resistance
(t) = 2Pt (8, ms))) 2P Po (x,
Here, (s), Bellman-like function involving error terms, is bounded in Lemmas 20-21 I by ad- dressing the challenge of trajectory coupling through a simple observation that grouping terms by time step creates martingale difference sequence (Durrett, 2019).
Intuitively, epistemic resistance adaptively reduces the per-step regret based on the unfamiliarity of the actions chosen by the current policy and the optimal policy. The greater the uncertainty of these actions, the lower the per-step regret, which highlights the critical role of epistemic uncertainty. In fact, the reduction of total regret is more pronounced, as indicated by the following bound.
Lemma (Lower Bound of Epistemic Resistance). Given uniform d A, Vt N, it holds that
T
n' (s.)A,, 2 23Rmax
(VT
+ +1) x - (VT-
7(1 - 7) Emaax
for any E N.
That is, the regret bound of our method must be no worse than that without epistemic guidance.
4.2 FREQUENTIST BOUNDS
Theorem 2. For infinite-horizon discounted MDPs, for any fixed E N, with probability at least
1 - 8, it holds that
VSAT (1-7)15 +
S2
(Tg
(1 7)
5

---

Published as a conference paper at ICLR 2026
Note that when T 2 A the regret matches the lower bound, implying nearly minimax-optimalin This result improves the state-of-the-ar frequentist bound from (He al., 2021).
1-y"
Theorem 3. Lete (0, V.7] å E (0, 1], and M = (S, be any MDP. There exists an input 77 Emax Y Rmax / m, such that if EUBRL is executed on MDP M. with probability at least 6, V (5t) 2 (s() c is true for all but Ô ((=114)) +
8 log !) steps.
<(1-7)²
Here, Y is a function of A, 6, X, V,D,, and m a critical point where the complexity term is suf- ficiently bounded (see Table 4). Note that when E [0, | the sample complexity matches the lower bound, implying nearly minimax-optimality. This result, to the best of our knowledge, the first online algorithm to achieve such a bound without assuming generative model (Ghesh- laghi Azar et al., 2013).
4.3 FROM FREQUENTIST TO BAYESIAN
In this section, we instantiate prior-dependent bounds and demonstrate their applications using con- jugate priors, building upon the frequentist results. To bridge the gap between the frequentist and Bayesian settings, we formalize key properties of priors that ensure expressivity while facilitating the analysis of regret and sample complexity.
Due to space limitations, we only outline the conceptual ideas here and defer the details Defi- nitions 13-16. A prior is decomposable if the difference between the posterior predictive and the ground truth can be decomposed into frequentist bound and a prior bias; a prior weakly informa- tive if the posterior predictive is close to the empirical mean. If the prior is uniform, the prior bias admits universal constant, and if bounded, the prior predictive mean of the reward is bounded.
Definition Let E be defined by the class of decomposable or weakly informative priors whose rate of epistemic uncertainty is + Vx
This class can be quite expressive, as it can be either correlated or independent over state-actions, including hicrarchical priors (Neal, 2012).
Let M = (S.A, be any MDP. For any prior by E C, there exists an instance of EUBRL such that, when executed on M, achieves, with probability at least - a prior- dependent bound on regret, or alternatively, on sample complexity, depending on the choice of 1, If, furthermore, is assumed to be uniform and bounded, these bounds are nearly minimax-optimal.
Theorem 4.
The significance of this result is that, depending on the priors, we can achieve even tighter bounds. In addition, it can be nearly minimax-optimal despite dependence the prior. We demonstrate its applications with the two most commonly used priors: Dirichlet for transitions and Normal or Normal-Gammn for rewards.
Corollary 1. Let bo denote the joint distribution consisting of Dirichlet prior sx)(alsx1) on the transition probability vector and a Normal prior N( _ on the mean reward with known precision T for all (s, a) E S x A. Then by E E and is uniform and bounded, and hence achieves nearly danimax-oppimaliiy when used with EUBRL.
To the best of our knowledge, this is the first nearly minimax-optimality result in the Bayesian setting. Nevertheless, we also find that EUBRL can fail in certain special cases.
Proposition 1. For Normal- Ganma prior NG Ao, cug, Bo), there exists parameterization and an MDP such that 3t E I for which quasi-optimism does not hold.
Intuitively, since the epistemic uncertainty of the Normal- depends on the sample variance, when the environment is deterministic nearly deterministic, this term can be zero, leading to de- generate rate of epistemic uncertainty that violates the requirement of quasi-optimism. Nonetheless, this issue can be alleviated by using sufficiently small prior parameters control prior bias.
When the prior misspecified such that the initial epistemic uncertainty is very low, the method may also encounter difficulties and could fail converge.

---

Published as a conference paper at ICLR 2026
Table 2: Summary of tasks. For Loop, denote as the number of loops and La as the k-th loop; for DeepSea, N is the side length; for LazyChain, N is the balanced length. "D" stands for deter- ministic and "S" stochastic.
Table Results on Chain environment. The average return and standard error are com- puted across 500 random seeds, with each run consisting of 1000 steps.
Algorithm
Average Return
SE
TASK
S
A
TYPE
CHAIN LOOP
10 (01
S
PSRL
3158
31
4L +
2
2 21 wo)
+
D
RMAX
3090
(1==1 AND (222)
BEETLE
1754
DEEPSEA
N x N
2
X())(N,)))
D
BOSS
3003
(a-mary
Mean-MDP
3078
49
DEEPSEA
N1 (/ A( (V..))
BEB
3430
MBIE-EB
3462
(a
D.0
VBRB
3465
20 ~ 50
LAZYCHAIN 2N +
3
(2N 1) 1p
S
EUBRL
3473
16
(N 1) (6
(amoo XOTHING)
(omEBwSE))
Theorem (Prior Misspecification). Let 17 = 1. There exists an MDP M, a prior by, an accuracy level eg and a confidence level ón E (0, 1] such that, with probability greater than ōg.
V**(s) < (*)) 60
will hold for unbounded number of time steps.
We construct a two-armed bandit with a misspecified prior such that the prior is confidently wrong and produces low epistemic uncertainty, leading repeated commitment the suboptimal with high probability.
In other words, this counterexample highlights the vital importance of the scaling factor v and the priors in enabling efficient exploration.
EXPERIMENTS
In this section, we aim to measure the exploration capabilities of EUBRL on tasks with sparse re- wards, long horizons, and stochasticity. We focus sample efficiency, scalability, and consistency, as reflected by metrics such as the number of steps or episodes required to fully solve task, scal- ability with respect to problem size, and success rate. We find that EUBRL generally matches or outperforms previous principled algorithms, with the advantage increasing as problem size grows. We compare EUBRL with both frequentist and Bayesian methods. Our benchmarks include well- known standard tasks in the Bayesian literature, Chain and Loop (Strens, 2000) the former highly stochastic, the latter deterministic and emphasizing state-space structure-as as well as more complex environments: we study DeepSea (Osband et al., 201 (b;a))) and design LazyChain, both featuring sparse rewards, long horizons, and deterministic and stochastic variants. A concise summary is provided in Table 2, with detailed descriptions available in Appendix C.I.
Baselines Frequentist algorithms based on optimism include RMAX (Brafman & Tennenholtz, 2002), which assigns unknown state-action pairs the maximum possible reward, and MBIE-EB (Strehl & Littman, 2008), which uses Hoeffding's inequality to derive a reward bonus bonus (s.aa where ne a) is the number of visits up to and including the t-th step. Bayesian meth- ods are flexible in incorporating prior knowledge. Sampling based methods include PSRL (Strens, 2000; Osband et al., 2013), which acts optimally with respect to a model sampled from the belief, and BOSS, which samples multiple models and solves merged MDP. Optinism-based Bayesian methods include BEB (Kolter & Ng, 2009), which is based on the mean-MDD with an additive bonus "oouss (3.0+) where are the prior parameters of the Dirichlet distribution: however,
based

---

Published as a conference paper at ICLR 2026
Average Return upon Solving Task
Loop Scaling
400
EUBRL
Table 3: Results Loop environment of 2 Loops. The average return and standard eπτоr are computed across 500 random seeds, with each run consisting of 1000 steps.
350
RMAX
300
250
Algorithm
Average Return
SE
200
PSRL
377
1
RMAX
394
150
Mcan-MDP
233
3.4
8
# Loops
BEB
386
0
EUBRL
395
0.04
Figure I: Scaling of number of loops, leading to more sparsity and structural difficulty. Averaged over 500 random seeds.
assumes the reward function known, and VBRB (Sorg et al., 2012), which is based on the vari- ance in the belief over both reward and transition. VBRB is similar to ours but, being tailored only to variance, does not include epistemic guidance. Moreover, classic Bayesian methods are worth comparing: BEETLE (Poupart al., 2006) provides analytic solution to BAMDP, where the Bayes-optimal policy implicitly trades off exploration and exploitation, and Mean-MDP (Poupart al., 2006; Kolter & Ng, 2009; Sorg al., 2012) approximates BAMDP without any reward bonus.
Results As shown in Table and 3, in Chain and Loop, EUBRL not only outperforms all rele- vant baselines but also exhibits low variability. Notably, Mean-MDP consistently performs subpar, highlighting the importance of reward bonus for sustained and efficient exploration. Furthermore, we evaluated EUBRL against RMAX-whold Loop by increasing the number of loops, which leads to more sparsity in the state space; surpris- ingly, even with a perfect prior-so so that RMAX knows the transitions and rewards after experiencing them it scales less favorably than EUBRL. This suggests that the priors in Bayesian methods may have a smoothing effect, enabling more scalable performance in sparse environments.
inductive bias favors deterministic environments-44
Another standard benchmark is DeepSea, hard-exploration problem where dithering strategy may require an exponentially large amount of data, and the success probability decays exponentially as the problem size increases (Osband et al., 2019b). As depicted in Figure 2, for the deterministic variant, most methods are able solve the task. Surprisingly, PSRL (or Thompson sampling in being an effective sampling strategy for exploration-doc not scale well the problem size increases. likely because their sampling is excessively frequent, causing unnecessary exploration and fluctuations near convergence. Additionally. BEB, a Bayesian method, also based on the mean MDP, does not leverage any posterior information in the reward bonus, making it less flexible across different environments and resulting in slower convergence. On the other hand, the stochastic variant a harder problem, with stochastic rewards, additional competing sources, and randomized transitions. We consider two priors for EUBRL: one more conservative and the other more exploratory, denoted EUBRL+. We find that our method is more sample-efficient, requiring fewer steps to solve the task, and more scalable and consistent. Notably, EUBRL+ perfectly solves the task without failure result observed in previous works.
the bandit
Lastly, we introduce a new environment called LazyChain, which involves long horizons, sparse rewards, and myopia. The only positive rewards are the two ends, with the left end being subop- timal. Starting from the middle of the chain, the agent can move at a per-step cost or choose to do nothing, incurring no cost but making it impossible to obtain higher rewards. Even upon reaching the left end, the agent receives positive immediate reward, yet the cumulative reward remains zero, hindering effective credit assignment. To succeed, the agent must sufficiently explore the chain to reach both ends and overcome the myopia. Results in Figure show that EUBRL consistently out- performs other methods, exhibiting better sample efficiency and scalability, even under heavy noise injection in the transitions. A comparison with DeepSea provided in Remark 1.
8

---

Published as a conference paper at ICLR 2026
DeepSea Deterministic
DeepSea Stochastic
1.0
1.0
Success Rate
0.8
0.8
0.6
0.6
0.4
0.4
Avcrage Episodes to Solve Tōsk
0.0
10
20
50
0.0
10
20
50
2500
2500
PSRL
PSRL
BEB
BEB
2000
2000
VBRB
VBRB
RMAX
RMAX
1500
EUBRL
EUBAL
Uniform
EUBAL
1000
1000
500
500
0
10
20
50
10
20 Problem Size
50
Problem Size
Figure Success rate and average episodes solve task, reported for both deterministic and stochastic variants over different problem sizes (S = N x N). Averaged over 20 random seeds.
Prior Selection We discuss the selection and incorporation of priors. We use independent Dirich- let (Dearden al., 1999) and Normal-Gamma priors for transitions and rewards. Although Propo- sition suggests that ceamal-Gamaa may be degenerate, we find that adapts more smoothly to changes. Since have diverse stochastic environments, the sample variance can help inform epis- temic uncertainty. In contrast, Normal-Normal assumes the precision (the reciprocal of variance) fixed, entirely disregarding variability.
Moreover, in practice-for for example, in navigation tasks where per-step transitions are similar across different states-it is beneficial use tied prior, maintaining single global Dirichlet prior that is aggregated and shared among all states. As shown in Figure 3, EUBRL (Tied Prior) indeed reduces the number of samples required for convergence and achieves a higher overall success rate.
From Section 3.1, we know that the definition of epistemic uncertainty is not unique. Beyond variance, one information-theereti measure is mutual information, which quantifies the reduction in uncertainty after collecting additional evidence. We find that mutual information is more exploratory than variance. shown Figure 3, EUBRL (MI), although taking slightly more steps, achieves the highest overall success rate.
RELATED WORKS
Bayesian RL Bayesian RL maintains a posterior over uncertain quantities and uses this uncer- tainty to guide policy selection. From bandits (Thompson, 1933; Kaufmann et al., 2012) to MDPs (Dearden et al., 1999; Strens, 2000; Kolter & Ng, 2009), this idea enables effective exploration strategies that are otherwise impossible with simple dithering. BAMDP (Duff, 2002) formally represents uncertainty over MDPs by augmenting the state with beliefs, allowing derivation Bayes-optimal policy, though it is generally intractable. Approximate methods include mean-MDP (Poupart et al., 2006), sparse sampling (Wang et al., 2005), and approximate inference (Wang et al., 2012). Despite being Bayesian, most of these works make limited use of uncertainty quantification, without fully leveraging the posterior. VBRB (Sorg et al., 2012) employs variance similar to ours; however, it motivated by Chebyshev's inequality and lacks epistemic guidance.

---

Published as a conference paper at ICLR 2026
LazyChain Deterministic
LazyChain Stochastic
1.0
Success Rate
0.6
0.6
0.4
0.4
0.0
0.0
Avcrage Steps to Solve Tbskk (k)
10
20
50
100
200
10
20
50
100
200
200.0
200.0
PSRL
PSRL
BEB
BEB
150.0
VBRB
150.0
VBRB
RMAX
RMAX
100.0
EUBRL
100.0
EUBRL (M))
EUBRL (Tied Prior
50.0
50.0
10
20
50
100
200
10
20
50
100
200
Problem Size
Problem Size
Figure 3: Success rate and average steps to solve task, reported for both deterministic and stochastic variants over different problem sizes (S 2N + 1). Averaged over 20 random seeds.
Provably Efficient RL The idea of knownness (Kakade, 2003), combined with Hoeffding's s in- equality, underlies the PAC-MDP (Strehl & Littman, 2008; Strehl et al., 2009) and PAC-BAMDP (Kolter & Ng. 2009; Araya-López et al., 2012) guarantees, though these bounds loose compared to our frequentist results. He et al. (2021) shows that nearly minimax-optin infinite-horizon discounted MDPs, but whether similar sample complexity guarantees hold remains unclear. Although several works achieve nearly minimax-optimal regret (Azar et al., 201 77) or sam- ple complexity (Dann & Brunskill, 2015; Dann al., 2019) 9) in the finite-horizon setting using refined concentration bounds (Lee & Oh, 2025), the infinite-horizor setting is generally more challenging due to trajectory coupling and value function stationarity.
regret is achievable in
Uncertainty Quantification Epistemic uncertainty- from knowledge gaps- has deep roots in cognition: it elicits curiosity (Kidd & Hayden, 2015) and enhances memory for surpris- ing information (Kang et al., 2009). Mathematically, this manifests surprise disagreement in one's belief, captured by mutual information (Hüllermeier & Waegeman, 2021) or variance (Kendall & Gal, 2017). Despite this rich foundation, formal study of epistemic uncertainty in Bayesian RL remains limited. As an intrinsic motivation emerging naturally from Bayesian inference, epistemic uncertainty offers versatile, principled approach to learning grannggg-e&&& critical open question remains: how to capture it across multiple hierarchies, minimizing the need of hand-crafted rewards.
7 CONCLUSION
In this paper, we introduce EUBRL, a Bayesian RL algorithm that leverages epistemically guided rewards for principled exploration. The epistemic guidance naturally disentangles exploration and exploitation and adaptively reduces per-step regret. Theoretically, we prove that EUBRL achieves nearly minimax-optimal regret and sample complexity for a class of sufficiently expressive priors, with concrete instantiations for the two most commonly used priors. Empirical results demon- strate the strong exploration capabilities of EUBRL on tasks with sparse rewards, long horizons, and stochasticity, achieving superior sample efficiency, scalability, and consistency. Scalable epistemic uncertainty estimation and efficient Bayesian planning with function approximation remain open and promising directions for future research. See discussion in Appendix B.3.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This research is supported by the Ministry of Digital Development and Information (MDDI) under the Singapore Global AI Visiting Professorship Program (Award No. AIVP-2024-002).
REFERENCES
Mauricio Araya-López, Olivier Buffet, and Vincent Thomas. Near-optimal BRL using optimistic local transitions. In Proceedings of the 29th International Conference Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 July I, 2012. icml.co / Omnipress, 2012. URL
http://
/ttp:/iccmm cmw.m.mmm..mmmmmmmmmmm/mmmmmmm/. ccc.0lccc111111 httpppaaaaa//aaaaaaa / pdd..
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International conference on machine learning, pp. 263-272. PMLR, 2017.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International conference on machine learning, pp. 1613-1622. PMLR, 2015.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(0c1):21)))3,, 2002.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances Neural Information Processing Systems, 28, 2015.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Richard Dearden, Nir Friedman, and David Andre. Model based bayesian exploration, In Kathryn B.
Laskey and Henri Prade (eds.), UAI '99; Proceedings of the Fifteenth Conference Uncer- tainty in Artificial Intelligence, Stockholm, Sweden, July 30 August 1, 1999, pp. 150-159. Mor- gan Kaufmann, 1999. URL http://pppe/eapp......oooo//a/aa http://seeaattcceeeeeeeeeeeeeeee
jsp
Armen Der Kiureghian and Ove Ditlevsen. Aleatory epistemic? does it matter? Structural safety, 11521100-112, 2009.
Michael O'Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy. Hypermodels for exploration. International Conference on Learning Representationss 2020. URL https:://// wwwp/eviee.....e////pp/ http://wwweeeee.eee.eeeeeeeeeeee wtt.://oeooommmeeerlllllleee
Ying Fan and Yifei Ming. Model-based reinforcement learning for continuous control with posterior sampling. In infernational conference on machine learning, pp. 3078-3087 PMLR, 2021.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100-118. 1975.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059. PMLR, 2016.
11

---

Published as a conference paper at ICLR 2026
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Interaational conference on machine learning, pp. 1183-1199 1192. PMLR, 2017.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3); 325-349, 2013.
Arthur Guez, David Silver, and Peter Dayan. Efficient bayes-adaptive reinforcement learning using sample-based search. Advances in neural information processing systems, 25, 2012.
Danijar Hafner, Timothy P. Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
https://openreet ew net/ forum?ide 1o.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Information Processing Systems, 01122288-223000 2021.
Nicolas Heess, Gregory Wayne, David Silver, Timothy P. Lillicrap. Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural In- formation Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp- 2944-2952, 2015. URL https: httep:::/prrcceednggs neurips cctpppppe///1//heeeeeeeeeee -btteaaaaaacs44411aaaaaattttatte html.
Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine learning, 110(3):457-506 2021.
Haque Ishfaq. Qingfeng Lan, Pan Xu, A. Rupam Mahmood, Doina Precup. Anima Anandkumar, and
Kamyar Azizzadenesheli. Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo. In The Twelfth International Conference on Learning Representations, 2024. URL https: /pppnevveew n forum? d=nf IAEJFIBZ.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom). 2003.
Min Jeong Kang, Ming Hsu, Ian M Krajbich, George Loewenstein, Samuel M McClure, Joseph Tao-yi Wang, and Colin F Camerer. The wick in the candle of learning: Epistemic curiosity activates reward circuitry and enhances memory. Psychological science, 20(8))963 973, 2009.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pp. 592-600. PMLR, 2012.
Michael Kearns and Satinder Singh. fcar-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2):209 232, 2002.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? Advances in neural information processing systems, 30, 2017.
Celeste Kidd and Benjamin Y Hayden. The psychology and neuroscience of curiosity. Neuron, 88 (3):449-460, 2015.
J Zico Kolter and Andrew Y Ng. Near-bayesian exploration in polynomial time. In Proceedings of the 26th annual international conference on machine learning, pp. 513-520, 2009.
David Krueger, Chin-Wei Huang, Riashat Islam, Ryan Turner, Alexandre Lacoste, and Aaron Courville. Bayesian hypernetworks. arXiv preprint
2017.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in applied mathematics, 6(1):4-22, 22, 1985.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances neural information processing systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2026
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference Algorithmic Learning Theory, pp. 220--33. Springer, 2012.
Harin Lee and Min-hwan Oh. Minimax optimal reinforcement learning with quasi-optimism. In The Thirleenth Internaiional Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL http:://///// ptttps::/opeereviieet. wwwp//pppeeeew..eoo/ee/ee......m net forum? ?id 18L.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv:1805.0000 1805.00909, 2018
Advaaces in neural information processing Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. Advances systems, 30, 2017.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvari, Satinder Singh, et al. Behaviour suite for reinforce- ment learning. arXiv preprint arXiv: 9008 03568, 2019a.
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124): 2019b.
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard S. Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:://ppereriii net forum?id= XYGE=XSYwH.
Pascal Poupart, Nikos Vlassis, Jesse Hoey, and Kevin Regan. An analytic solution to discrete bayesian reinforcement learning. In Proceedings of the 23rd international conference on Ma- chine learning, pp. 697-704, 2006.
Tom Rainforth, Adam Foster, Desi R Ivanova, and Freddie Bickford Smith. Modern bayesian ex- perimental design. Statistical Science, 39(1):100-114, 2024.
Remo Sasso, Michelangelo Conserva, and Paulo Rauber. Posterior sampling for deep reinforcement learning. In International Conference Machine Learning, pp. 30002-000601 PMLR, 2023.
Jonathan Sorg. Satinder Singh, and Richard Lewis. Variance-based rewards for approximate bayesian reinforcement learning. arXiv preprint arXiv: 2012.
Alexander I. Strehl and Michael I. Liuman. An analysis of model-based interval estimation for
markov decision processes. Journal of Computer and System Sciences, 7408):1309-131,, 2008.
Alexander L Strehl, Lihong Li, and Michael L Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Machine Learning Research, 10(11), 2009.
Malcolm Strens. A bayesian framework for reinforcement learning, In ICML, volume 2000, pp- 943-950, 2000.
Bhavya Sukhija, Lenart Treven, Cansu Sancaktar, Sebastian Blaes, Stelian Coros, and Andreas Krause. Optimistic active exploration of dynamical systems. Advances in Neural Information Processing Systems, 36:38 122-38153, 2023.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http: http:://inncompeeeeeeeeeee net /bwp////eoeooookkkkeee 2nd. html.
13

---

Published as a conference paper at ICLR 2026
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-255 -244, 1933.
Emanuel Todorov. General duality between optimal control and estimation. In 2008 47th IEEE conference on decision and control, pp. 4286-4292. IEEE, 2008
Mare Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference on machine learning. pp. 1049-1056, 2009.
Tao Wang. Daniel Lizotte, Michael Bowling, and Dale Schuurmans. Bayesian sparse sampling for on-line reward optimization. In Proceedings of the 22nd international conference on Machine learning, pp. 956-963, 2005.
Yi Wang, Kok Sung Won, David Hsu, and Wee Sun Lee. Monte carlo bayesian reinforcement learning. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 July I, 2012. ieml.ec Omnipress. 2012.
URL http:
//icml. cc//012/papaaeececcc http/ppppr////22 pdd......
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICMI.-1)), pp. 681-688, 2011.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
14

---

Published as a conference paper at ICLR 2026
8
Standard RL
0
a
Ours
U
O
Figure 4: Comparison between standard RL and our formulation as represented by probabilistic graphical models (PGMs). We introduce the variable of "uncertainty" U, which partitions the opti- mality O into distinct cases: one is when certain, the other when uncertain.
A CONTROL AS INFERENCE
In this section, expand the discussion the motivation for using probabilistic inference to in- corporate epistemic uncertainty into the agent's learning objective. decision-making problems, an agent seeks to accumulate knowledge through interactions with the environment. Standard RI. achieves this by maximizing accumulated rewards; however, this approach often becomes overly ex- ploitative of known rewards and ignorant of unknown potential rewards. Consequently, the learning process is not truly active, as is driven primarily by observed rewards rather than by the uncertainty surrounding them.
By contrast, UCB-based bonuses introduce a proxy for "uncertainty," such as the inverse visit active exploration. However, these methods often fail distinguish whether a reward estimate reliable or not when the uncertainty is high. This limitation moti- vates to disentangle exploration from exploitation via epistemically guided rewards, which are anchored in probabilistic inference.
counts, promote
Specifically, probabilistic graphical models provide principled framework to condition on addi- tional hidden variables (e.g., U). As illustrated in Figure 4, this conditioning allows us to partition optimality (O) into two cases (or more, depending on modeling choices): one in which the agent is uncertain, corresponding to epistemic uncertainty, and one in which it is certain, corresponding to reward estimates. This mechanism thereby focuses more on exploration when epistemic uncertainty is high, while shifting to exploitation when the agent is confident in its existing knowledge.
B
MODEL SPECIFICATION
B.1 HIERARCHICAL REWARD MODEL.
In our setting, r(s, a) denotes the expected reward, which deterministic function. The source distribution can be modeled as either P(rls, or P(r(s, a, s'). Notably, the former is independent of the outcome following the action, making less expressive and potentially misrepresenting the underlying generative process. For example, in many scenarios, the reward is meaningful only when feedback is received, which depends on the next state s'. In such cases, the reward distribution P(r]s, a) effectively becomes mixture distribution:
P(rls, a) p [P(rls,a,
we were to use simple distributions e.g. Normal distribution to model P(r|s, a), then it will underrepresent the more complex true mixture distribution. On the other hand, if P(r[s, a) can be
15

---

Published as a conference paper at ICLR 2026
sufficiently represented by class of distributions, its feedback-dependeni counterpart P(r]s, s') must be representable with similar complexity. Moreover, learning P(ris, a, s') and the transition model P(s'|s, a) is disentangled, allowing computation to be appropriately allocated. In contrast, learning P(rls, a) implicitly learns P(s"ss, a), which makes learning more difficult and prevents reuse of existing knowledge. Therefore, adopt modeling P(r|s, 0, 8') in our implementation and aggregate epistemic uncertainty in reward as follows:
ER(,,a) = Bps(o(Taa) [E((s,a,'))--
B.2 EPISTEMIC UNCERTAINTY
seriance-based epistemic uncertainty involves evaluating the expectation of either the transition model or the reward model. However, unlike real-valued distributions, it is meaningless to take an expectation over a categorical distribution, since the numeric representation does not correspond to the actual categories. To address this, we encode the state using one-hot encoding when calcu- lating epistemic uncertainty for the Dirichlet distribution. The exact formulations provided in Section H.2.
The maximum epistemic uncertainty Emar, required by the epistemically guided reward. is fully determined by the priors and therefore does not introduce any additional degrees of freedom. Al- though epistemic uncertainty is generally non-increasing, for certain priors it may not be strictly so-for example, the Normal-Gamma prior for the reward, which incorporates the sample variance. Therefore, it is safer track the maximum epistemic uncertainty throughout learning, ensuring that Py remains well-defined.
For mutual information-basee epistemic uncertainty, it worth noting that a closed-form solution exists for the Dirichlet distribution. By leveraging the known moments of the Dirichlet, we obtain:
MIs a) [DK (P(s'Is, w) Po a))l
Σ ai vba; + 1 ssa + 1) - log 06i
(x)
where v is the digamma function.
B.3 DISCUSSION ON FUNCTION APPROXIMATION
Although our work is not intended for immediate deployment with deep function approximators, we believe that the conceptual idea of epistemically guided reward could inspire future research. The main barriers we foresee are the efficiency and quality of both epistemic uncertainty estimation and Bayesian planning. Furthermore, we discuss how our theoretical results could be extended beyond the current setting.
Epistemic Uncertainty Estimation Existing approximate Bayesian methods can be leveraged for this purpose, e.g., deep ensembles (Lakshminarayanaa et al., 2017), Bayes by Backprop (Blundell et al., 2015), MC dropout (Gal & Ghahramani, 2016), Bayesian hypernets (Krueger et al., 2017; Dwaracherla et al., 2020), Langevin Monte Carlo (Welling & Teh, 2011; Ishfaq et al., 2024). However, these methods typically require multiple models or samples, which can significantly hin- der computational efficiency, particularly when integrated with Bayesian planning. Meanwhile, some efforts (Fan & Ming, 2021; Sasso et al., 2023) have been made to scale PSRL to continuous state and action spaces using Bayesian linear regression, offering a lighter-weight alternative. When epistemic uncertainty is quantified via mutual information. active learning (Gal et al., 2017) and Bayesian experimental design (Rainforth al., 2024) provide tractable estimators. In particular, Sukhija et al. (2023) model the dynamics with Gaussian processes (Williams & Rasmussen, 2006), deriving tractable upper bound on mutual information, which demonstrates strong zero-shot capa- bility on novel tasks. Nevertheless, a key open question remains: can we construct well-calibrated epistemic uncertainty estimator that does not rely heavily on sampling?
Bayesian Planning One can leverage sparse and smart sampling strategies, such as employing lazy sampling (Guez et al., 2012) or reusing a set of pre-sampled models (Wang et al., 2012; Lu & Van Roy, 2017). Additionally, trajectories can be simulated in latent space using Monte Carlo
16

---

Published as a conference paper at ICLR 2026
estimates, similar to Dreamer (Hafner et al., 2020), while policy optimization be performed via reparameterized policy gradients (Heess et al., 2015). Despite these advances, computational efficiency remains suboptimal, and the accuracy of the solution is unclear.
Approximation Error When approximation is involved, a natural question arises: do the theo- retical results in the paper still hold? We argue that theoretical results remain meaningful in the approximate setting. For example, when an exact MDP solver is not available, we may need resort an approximate one, whose solution we denote by क.. The per-step regret can then be re-expressed as follows:
V*(s) - (8)= (*) + (T ( V
Approsimation Erroe
As shown, the per-step regret can be decomposed into two components: the first part corresponds the results established in the paper, while the second part captures the quality of the approximate can derive similar regret and sample complexity bounds, albeit with an additional term reflecting the approximation error.
solver. If reasonably good approximation is available,
This property is appealing because, given the same solver, our method will always outperform alter- native approaches. also implies that EUBRL can be integrated with existing solvers, such as tree search-based rollout-based methods, as discussed previously.
Overall, scalable epistemic uncertainty estimation and efficient Bayesian planning with function approximation remain open and promising directions for future research, providing fundamen- tal basis for enabling active exploration in increasingly complex environments. Moreover, a more comprehensive theoretical analysis of the approximate setting is another direction worth pursuing.
C EXPERIMENTAL SETUP
C.I ENVIRONMENTS
Our benehmarks include standard tasks from the Bayesian literature, Chain and Loop, originally introduced by (Strens, 2000) as testbeds for smart exploration. These tasks are challenging due to the presence of multiple suboptimal policies and the fact that the optimal policy produces rewards that distant. The two tasks differ in their characteristics: in Chain, transitions are highly stochastic and actions may not always have the intended effect, whereas Loop, although deterministic, has a state-space structure that makes exploration difficult.
In addition to these, we evaluate more complex and larger-scale tasks. In particular, DeepSea (Os- band et al., 2019b), as implemented in Bsuite (Osband et al., 2020), requires deep exploration core capability for RI. agents. It has been shown that dithering strategies such as e-greedy or Boltz- mann exploration fail achieve deep exploration and may require exponentially many episodes to learn anything meaningful. In contrast, optimistic or randomized strategies can solve the task in the optimal number of episodes (Osband et al., 2019b). DeepSea has two variants: one deterministic, where both transitions and rewards are predictable, and one stochastic, which introduces noise to transitions and rewards and includes competing reward sources, making more challenging. No- tably, no algorithm has been shown to consistently succeed across different problem sizes in the stochastic setting.
Furthermore, we introduce new environment called LazyChain, where effective credit assignment bottlenecked by exploration, and efficient exploration hindered by myopia. In this environ- ment, seemingly promising immediate rewards may not provide meaningful feedback for learning the value function. LazyChain also has deterministic and stochastic variants. Details of all these environments provided below.
Chain (Strens, 2000) a five-state problem with two abstract actions, fleft, right). Each action has probability of "slipping", which causes to produce the opposite effect. The optimal behavior to always choose the action right; however, if the other action is chosen, the agent will be reset to the leftmost state.
17

---

Published as a conference paper at ICLR 2026
11L
1=0
1=1
1+2
Figure 5: Visualization of DeepSea.
Loop (Strens, 2000) was originally proposed as a two-loop problem jointly connected at a single start state. is deterministic environment consisting of nine states and two actions, {a, b). Repeat- edly taking action a causes traversal of the right loop, yielding a reward of when the agent returns the start state, while repeatedly taking action b traverses the left loop. yielding reward of If single step is missed in the left loop, the agent is immediately sent back to the start state, while all other actions taken within the right loop continue the traversal. This problem makes exploration difficult due to the structure of state-space and sparse rewards.
We generalize this environment to more than two loops, with only one loop yielding the optimal reward. The size of the action space expands to match the number of loops, with each action corre- sponding to entering a specific loop. Similarly, any incorrect action taken within the optimal loop causes reset to the start state, while the other loops continue their traversal.
Deep Sea (Osband et al., 2019b;a) consists of 5 which move the agent diagonally and terminate exactly after N steps per episode (see Figure 5). In the deterministic variant, there is only one positive reward at the bottom-right cell, representing treasure. However, there is per-step cost of in that direction, while no cost is incurred when moving the other way. In the stochastic variant, "bad" transition is generated with probability 1 when moving toward the treasure, introducing a high degree of uncertainty from which the agent may not recover. Moreover, additive noise N 1) applied to the rewards at both the treasure cell and the bottom-left cell.
x states and two actions, fleft, right),
0.01 N to discourage the agent from moving
Lazy Chain is balanced chain, with the initial state in the middle and the two halves of equal length (see Figure 6). The only positive rewards are at the two ends; however, the left end is sub- optimal. The per-step cost for moving along the chain is -1. To test the exploration capability of an algorithm, we introduce another action, do nothing, which leaves the agent in the current state with no cost incurred. Notably, although the left end gives positive reward, accounting for the cost to reach it, the cumulative reward will be zero. This makes credit assignment even harder, as fails to distinguish between "worth nothing because nothing happened" and "worth nothing because a lot of bad things and one good thing happened." Without proper exploration, an agent may either the suboptimal path or be unable receive any positive rewards, eventually in the same state. There are two variants of this environ-
converge confidently leading to a myopic solution-remainiin ment: the deterministic version, in which transitions are fully predictable, and the stochastic version, in which actions may be flipped at each time step with probability p = 0.2. In addition, the agent is reset to the middle of the chain whenever either end is reached.
Remark I. Notably, unlike DeepSea, where the probability error decays and is limited to the "right" action with adverse effeect, LazyChain maintains constant error probability, affects all movement actions, and produces opposite effects, making larger problem sizes increasingly chal- lenging, potentially exponentially so. Additionally, DeepSea is episodic, terminating exactly in N steps, whereas LazyChain may take an arbitrarily long time to explore the chain, even indefinitely, if one keeps choosing do nothing, Moreover, LazyChain has more suboptimal solutions, since
18

---

Published as a conference paper at ICLR 2026
Do Nothing
=
r=N-1
80
8N-1
SN
SN+1
82N
r= 2 -1
r= -1
r=
Turn Left
Turn Right
Optimal Direction
Figure 6: Visualization of LazyChain.
DeepSea is isomorphic to the right half of the chain of LazyChain, where any action that does not head toward the treasure is considered a failure.
C.2 METRICS
The metrics we choose reflect the key aspects interest: sample efficiency, scalability, and consis- tency. These are measured by the number of steps episodes required to solve task, scalability with respect to problem size, and consistency in terms success rate. Additionally, we report the average return whenever applicable.
Average Return The cumulative return up to given time, averaged across all random seeds.
Average Steps Episodes to Solve Task The number of steps or episodes required to solve the task, averaged across all random seeds.
Success Rate The proportion of successful runs among runs.
An algorithm is considered successful only if it matches the optimal policy exactly for consecutive episodes, which makes this stricter condition for task completion. Meanwhile, an algorithm halted if it succeeds in solving the task, fails to solve the task completely, exceeds the maximum allowable steps max For instance, Chain and Loop are stopped exactly at the specified number of environment steps. In contrast, for DeepSea, length, and for LazyChain, we use Taax 1000 N, where N is balanced length. This choice both facilitates computational efficiency and allows evaluation of exploration under constraints. In other words, this threshold can be viewed as a penalty for any algorithm that fails the task, inflating the metric for the average steps episodes required solve the task.
limit of T 50 N where N is the side
In sparse reward environments, we expect an efficient algorithm to achieve faster convergence, as indicated by the average number of steps or episodes required to solve the task, and higher con- sistency, as reflected by the success rate. However, in practice, algorithms may exhibit trade-off' between convergence and consistency.
C.3 HYPERPARAMETERS
To ensure fairness, all hyperparameters are tuned via line search for best performance for each method. Moreover, we ensure identical priors and modeling choices across Bayesian methods. Scaling factors are adjusted per algorithm, as they algorithm-dependent.
We model rewards using Normal-Gamma model N Ao, ao. 30). We set μi = and ag = 2. Furthermore, we impose À Bo. resulting in a single tunable parameter. This configuration leads to an initial epistemic uncertainty Ex(s, a, s') = 1, V(s, a, s') E A x.x.. addition, we model transitions using Dirichlet-Ne Mullte-mllti model. The Dirichlet prior is parameterized by single parameter a, yielding to a uniform prior Dir(1 a). A higher value of a indicates a stronger prior belief, whereas lower value makes the prior less informative. On top of that, have tunable
19

---

Published as a conference paper at ICLR 2026
scaling factor 7). For LazyChain, since the maximum reward scales with the state space size, the scaling factor has to be adaptive.
For Bayesian algorithms like EUBRL, VBRB, PSRL, and BEB, perform sweep
Dirichlet
10 10- 10 , x 10 5 10 x 10 10 1 10-4) for rewards. All algorithms use the same prior. The scaling factor is tuned individually for each algorithm, in proportion the maximum rewards the state space size. We find that VBRB and BEB perform better when the scaling factor is smaller, whereas EUBRL benefits from slightly larger value. worth noting that PSRL does require scaling factor; promotes exploration by repeatedly sampling from the belief. However, this sampling mechanism can lead to numerical instability when the Dirichlet parameter is too small (e.g. below the threshold clip the Dirichlet parameter at this threshold, which only affects state-action pairs for which no observations have been made. Moreover, since BEB does not utilize the posterior to compute the reward bonus, it is unnecessary to adopt the reward modeling discussed in the previous section; follow the same practice as the original paper.
parameter a E {1.0, 1 x 1001 1x 10 2, 1 10
10 *} for
transitions, and 3D E (1.0, 5 10 1 x 10
10-3) For faimess, we therefore
For the frequentist algorithm RMAX, the maximum reward is assumed to be known to the algorithm, and we tune the knowness parameter m E {1,3, 5, 10, 20). We find that a small knowness parameter is generally beneficial in deterministic environment, but not well suited for stochastic environments, which require sustained exploration. moderate value of the knowness parameter performs best in stochastic environment; otherwise, the algorithm spends excessive time exploring, which scales as (m).)).
The discount factor is kept the same for all algorithms. However, its value may differ across tasks, depending on the task horizon. For smaller-scale tasks like Chain and Loop, we choose 7 which trades off accuracy and computational efficiency. For long-horizon tasks, we choose ? 0.99 for DeepSea, while = 0.999 for LazyChain, since LazyChain may require more time to explore due to the inaction and stronger stochasticity.
0.95.
C.4 CODE ACCESSIBILITY
The code supporting this work is available at htttps//ggithi comm/Maiieeeney/EEBaaa licensed under GPLv3 ensure the software and its derivatives remain free and open-source. Our code is based on https: //gttub com/ dust /duustisitttt innttiivtee ratttaaaaaaaeeetteeeaaae revised, extended, and optimized while aligning the baselines with the original implementation. We appreciate the efforts of the authors in releasing their code.
which we substantially
D NOTATIONS AND LOGARITHMIC TERMS
In this section, we summarize the notation and logarithmic terms used exclusively for the analysis of both finite- and infinite-horizon settings. To begin with, we denote PV(s, a) == P (V(')) for any distribution and function V.
D. FNNITE-ORIZON EPISODIC MDPs
Whenever we refer to i or h, they denote the episode and particular step of that episode, respec- tively. We define An (v)((s, == Vn (s) ( a). Furthermore, we define Nx(s,, a) as the number of visits to (s, a) before the k-th episode, and (s, a) as the number of visits up to and including the htth step of the k-th episode. is useful to define stopping time vk as follows:
min(h E [H] n (s) at) > 2N* (s af), h exists.
H 11
otherwise.
Intuitively, the stopping time is the first time step within an episode at which the number of visits has more than doubled compared to before the episode.
We define the error terms 8*, a) associated with (*,aa)))
(4 - (s)) + 30v
(* = () () (*(
A
20

---

Published as a conference paper at ICLR 2026
Table Summary of logarithmic terms and additional notations used in the analysis, with shorthand notation. Each term is specialized for finite- and infinite-horize MDPs, where symbol O takes either episodes or steps input.
Shorthand
Finite-horizon episodic MDPs
Infinite-horizon discounted MDPs
4
log (2
log 24SA4
2n
log (1 + SA
kH
log
+ 37
f3,0
log
12.5 (3 +-ogg kM)
log
125 A2 +1pg
(s,
log
125 N² (a.al)
log
125 N (a.a)) 6
4,
log 12H
log 8
ls,e
log (1 + (8)
log (1 + 140B(c))
log log Vie
Vee log log x(1->)
lo.
B(e)
Ris 2
Run HS(H +la.))
R 4
Rox 9(26 + (p..) c11-1)
(1 73
VC2
mp
R X V
R X
m
R X 7V 6 Ag
R A 7V
rD
7V
1f
Emax rk + Rmax ma
Ema T + Remax mi
Emax T + Rmax v m
Emax Y + Rmnx m
Based on this, we define a Bellman-like like function (s), which uses (* a) as rewards while fol- lowing the latest policy uy and the true transition P:
J (+) = (s) = miin {
+ P (x))), viJ} for ha E [M].
D.2 INFINITE- HORIZON DISCOUNTED MDPs
Whenever we refer to I, it denotes the time step, which is the same as the environment step. Analo- gously, we have (V) a) = V(s) - (V((s, a). In addition, we define ('(s,, a) as the number of visits to (s) prior to the 1-th step", and n²' n a) as the number of visits up to and including the 1-th step.
The stopping time i is defined as follows:
min(r [1, n (ST, a7) 2N' 0r)}, if exists.
1/ ==
T ++1,
otherwise.
The main difference from the determine a stopping time v,, rather than relying on single stopping time that applies to entire episode.
setting is that, every time step f, we look ahead to
Similar to the finite-horizon setting, we define the enror terms (i a) associated with N'
(4 (4- (
(ss == (( (s
+
X
Althooghh at first sight this definition differs from the standard visit count n'(s, a). they essentially cquivalent up one-step shift.
21

---

Published as a conference paper at ICLR 2026
And (s) uses ('(s, a) rewards while following the latest policy x¹ and the true transition P, with discounting:
[s) = min
(s)),
E HIGH PROBABILITY EVENTS
In this section, outline high probability events that are basis of the analysis henceforth. Let {A+] be a sequence of real numbers with A E (0, 1), vk E N for finite-horizon episodic MDPs. Analogously, we have {Ae]E=1 for infinite-horizon discounted MDPs. They arise from Freedman's inequality (Freedman, 1975), and has been enhanced recently by (Lee & Oh, 2025).
E.1 REGRET ANALYSIS
E.1.1
FINITE-HORIZON EPISODIC MDPs
A
3 Var Var(V (vs(
A =
(pt - PIV PPVVi- s
[H), \x.*(s.a) ( A A [
4V
6V &
A2 =
(P (M-P")(;;)))(s.)) - 2
Var Var(V (s,
V(s.a)
[1],EEN
(²(s,a)
2P(s' 8, (, a) 1*(8'1 1s,)) PP(s' ss,a) 2
283,((8,
A3
((s,a) ES
N²(s,a)
(N
Rmaah
A4
ph (*, r(s, S s
ESx \s, ESx A
K
1 -ー1
6 Var(Jk+ a +V log AK eN
As
(5h J&t (s) S
AV
H
km
Am1
K -
K b
1
6 Var(J att + 6V log 5.
As =
(P(Jitz))(hh aht
S
AK N
2
k=
A=1
E.1.2 INFINITE-HORRZOO DISCOUNTED MDPS
(PV S de (s, 3V
A7 =
AV.
6V
Aî- =
(P (P-P))(V))(s - (s,(())(s,,)++ + N'(s,a)' ((s,a)
2P(s' (3,0)la,(s,a)
23zn(s,0)
A3
('(6' (, P(s' ([ss|ss00) s,,a s /
((s,a) V (
(((
3N
Rmach V(s,a) ((5, ES
A7
(s, r(s, a)) S Arr(s,a)
\,Na(s,a))
Ag
Σ
T -1
+ (s)) -((444)))) <
(1 (1-7)
8V8 Σ Var (Y*( (st, +
6v1
log z.
6
VT ENJ
1
1=0
? -(X(ss))))))) < Var (x*(4)))) (5t, 0z) + 12V12
AO =
Σ (P(("(s++))) (s),
log g
VT E EN
(1 7)2
For the definition of yt (8(++)))) please refer to the proof of Lemma 20.
22

---

Published as a conference paper at ICLR 2026
E.2 SAMPLE COMPLEXITY
To analyze sample complexity, we consider modifying the last two events using an indicator function that only accounts for subset of episodes time steps deemed "bad". Since the resulting bound is almost identical, except that these "bad" indices replace the full summation, we denote such events as A7; As for finite-horizon episodic MDPs, and A7, Ag for horizon discounted MDPs.
E.3 PUTTING ALL TOGETHER
Each undesirable event is assigned probability most A 6. By the union bound, the probability of their intersection is at least 1- Therefore, we have the following events spanning different results:
A ni_i
B = AEAA
= (n==AA)) (A7
D = (NL (
F PROOFS FOR FINITE-HORIZON EPISODIC MDPs
Our proof starts with finite-horizon episodic MDPs, which are simple to illustrate and play a vital role in bridging the infinite-horizon horizon case.
F.1 PRELIMINARY CONSTRUCTIONS
Since our formulation decays more aggressively than 1 NE. we need to introduce an auxiliary value function T that behaves the same the original before a critical point m, however, after which error should be manageable. That is, it value function of the MDP (S, A, pk 5 H)) where only the reward is different compared to 1 of (S, A, pk r "'LBBRL: H). The modified reward defined as P/) + b², where the bonus term is defined as:
E P Rmax
N m.
T NT. otherwise.
Here n7th = Emax T Ryux / ma. for which more details can be found in Lemma 33.
The reward is increased to degree that decays least as fast as NE ensuring advantage over the complexity arising from the reciprocal of visits. Although this advantage holds for an arbitrary m, need to control the error between the two value functions thereafter. For this reason, we set v
= Re Xi
which yields sufficiently small error.
F.2 QUASI-OPTIMISM WITH EPISTEMIC RESISTANCE
Lemma 2. For finite-horizon episodic MDPs, under high-probability event A₁ O Ag. it holds that for all S, h. E [H + 1], ke N.
Vi((s) + 33 2 (0) N Vi((s)
Proof. Since we want bound the error between V V*(s) and (*((s for any S. The auxiliary
function is served as a bridge to achieve that. Let us decompose the error (*(s) (s)-)*(s) as follows:
V*(s) v* V*(()
V v
Quasi optimismm
Complexity
The complexity can be bounded by Lemma 3, and its proof will be given later. We now focus on the other part.
23

---

Published as a conference paper at ICLR 2026
The proof follows the procedure of Lemma 2 in (Lee & Oh, 2025), with modifications to fit our for- mulation. The epistemic uncertainty guidance allows us to establish refined induction hypothesis, thereby tightening the bound in proportion to the degree of uncertainty.
To simplify notations, more, let a* = x (s), = n² (s), and ä == (s) denote the actions under the optimal policies corresponding to V*, V* and V*, respectively.
write P (s) (s, π (+)) and (s) (s ( Further-
We prove by backward induction on h:
(s) - (s) S Ax ( (P-PP)(()) (s) (s)))
1
(V))
2V
For the base case h = H + 1, both sides are 0, therefore the inequality holds. Assume it holds for h + 1, we will show it holds for h. If V V then left-hand side will be no positive, therefore the inequality trivially holds. Suppose Vi < Vii by definition we have
V (+) = p (s, + Ph (s,
With this, we obtain:
Vi(()) - (s)
(s) (+(s,a")+
(s) +
(a) - (r(*,a*) + PV - (8) + P4 (1)
= rs(s,a") - 5* a²) + (VVi+i((,
/iViitassa"") - (s, +b =r(s,a") - -(1-) (s."")))) +
- -piihh
( (1- P (s)) (r(s, + -
(PViti pa p4 (..
where (a) is due to the optimality of ā and (b) by noting r(s,a")
(a1 - p(- Pt)((s) r(s,at).
Since r S Reaax we have:
phi* (s)r(s,a") (s(ss a²) S (s) -ammx-b66ss (ss
At this point, we note that the intermediate steps are identical to those in (L.ee & Oh, 2025); therefore, we omit them here and state the resulting expression. Denote P = TV
we obtain:
(s) (s) N - (b (s, a²) - ph: (m) + (7 (7-Ph (
\xN*(ssaa*)
dv (V)))(ss)
A2 p (s))(((s))) PVitz(s,a"))
2V
--(b"ss, p1x+ (m)x) (7 - (7-Pti* (s))
do (t--pti(ss) ((-
Vi((s)
2V (17)((s)
1
ANN*(s,
S -(("(s,a") - (s) + N*((sa))) + du
rk
((2- (i- (s)
1
(V))
2V
$
(a)
$ d ((- (i)
(v)))(s)
(1)
2v
where (a) is due the fact of Lemma 33. Moreover, note that for E S, we have s 2
po- (s) S 2, therefore the function f(z) (2 p--p-* (s)
1 x² x E [o, vijl is bounded by
2v
{ ph (s)) VØh Substituting this for Eq. completes the proof.
24

---

Published as a conference paper at ICLR 2026
F.3 BOUNDEDNESS OF COMPLEXITY
Lemma 3. For all & E E [H + 11, & E N, holds that
(5) (x) (+) S RmarAs == k.
We first introduce the the following elementary lemma:
Lemma 4, For any max } we have
m VR v
< C.
Proof. Since n m, vn vn <6 2, then the result is desired, which is because:
0. require c-aceuracy, needs
n + If have
/n
m v
<
+
n
7
Proof of Lemma 3. The following will bound the complexity term (*))) (s). Since the two terms differ only in rewards, first bound the difference in rewards 1 EEBBRL
Without loss of generality, we bound the reward for finite-horizon episodic MDPs. We set 6Y
Amade thereby my
R2
If N my the reward jk of Vk is the same as rh
"BUBRL. therefore A
otherwise, have
r
A
Rmax
EP
No
PS
Rmaxxxxx Rmax
r
Tx
Rmax Emax
m
1
NE
No
Raus
TFER
Ph Rmaxx
Emn
N
Rmax
Ems
VNJ Emax
N
Rmax
V mg N
Emax
Rmax
v N
mi
Emax
N
Rmax
VNk
m
Emax
N
Rmax Rmaxx Ax
S Emax V.7
Rmax AE
Emax H
Aj
< Remxx H
where the second to last is because of Lemma 4, and the last is because of the assumption that Emax 1.
25

---

Published as a conference paper at ICLR 2026
By Simulation Lemma (Kearns & Singh, 2002), we know that the value functions differ at most Ry
For dufinite-horizon discounted MDPs, the proof is similar, except that need replace the time index with and the maximum value function with VJ.
F.4 BOUNDEDNESS OF ACCURACY
Lemma 5. For finite-horizon episodic MDPs, under high-probubiliiyy event M==1 As holds that for all s E S,h E [H + +l, N,
(s) (s) VI (s) S (s) 2 ( Aall + (2) -
Φ²
Xo teltx
V
convenient to define the following quantities for the analysis. Definition 2. Let (s) be defined by
(+)))= = dE (3- 2V
(1))(s))
(Sk)² (V/ + 5h )
+ VV
where as)
Pb(()) Vil.2
(s, a) = (s a)n E +
Ns,4((s,
(s) = (s) (s)
3
Sp 2
p (s)) de VeVi + tk:
which
1
33i + -30 (ts
B ($,0)) (s)
Proof of Lemma 5. The key to bound the accuracy term (1) - Vi (s) is to decompose into differences:
(x) (s) = An (8. +P (V% v++1 (s,a).
By Lemma 35, we know that
S (D*) a) 2.3 (s)
Combining this with backward induction on h, we obtain
(+) (s) ()((s) (8)
The final step is to bound (s). Denote
I 2P) 1 (v)))(s))
2V
Ig = St - (V/((s) - ss)))
we have (s) = > J2
TV Tz.
We now bound l/ and 13 individually.
Bounding Iz
2 - 2P)(s)) V1
T <
(2)
26

---

Published as a conference paper at ICLR 2026
Bounding Is
13 - (s)2 2S, (s) S Sg. 17(()) E -- vill
(3)
3
S =
P (s)
A V + 4
(4)
2
S
3
p
(8)
1/ + $ + +3 2s)
(6) A 1/
(5)
2
Therefore,
1
(+) = 2 +
17
(6)
7V
5 -22P((s)
1 1/3
(3- (s)
2
+
AnVit
2
XEV +0
+0A
2 p(:)(s)
$
(8)
As V
0
+ xx
11
which completes the proof.
F.5 BOUNDEDNESS OF J
Lemma 6. For finite-horizon episodic MDPs, under high-probability event As O Ag, it holds that
12H
( 2
2 a Aom
+ S6 log
h=1
for all K E.N.
Lemma 7. For finite-horizon episodic MDPs, under high-probubility event As n As, denote )((K) 12V S, it holds that
Ag
K
KH
12H 8
1 (x+) < 42((KSAAM log 1+ SA
+6V
for all K N.
F.6 LOWER BOUND OF EPISTEMIC RESISTANCE
Lemma 8 (Lower Bound of Epistemic Resistance). Given uniform A = X, VK E N, it holds that
K
23 (2 (VHK- - VH) HHH) X
Emau
for any K N.
27

---

Published as a conference paper at ICLR 2026
Proof.
P0
a4)
-1+
E Emax
at)
kmm
K
2 21+ Cmax
(k 1)H
k=2
K-1 1
=1+
Emxx H
Vk
k=
k+1
2
dx
maa VH J
Vx:
=1 Emax V
(2V -2)
-2) 2)
Note, this also holds for P ( Therefore, multiplying with 7
23 AV completes the proof.
F.7 REGRET ANALYSIS
Combining the results of Lemmas 2-5, we obtain the per-step regret:
Theorem 6. Under high-probabiiltty event A, it holds that for all E S,
(H + 1], EN,
V ))
(s) (x) Xn V + +2)
o 1+ 2b
where we define the following as Epistemic Resistance
H (s) = (P) 9 (s).
Theorem 7. For finite-horizon episodic MDPs, for any fixed K E N, with probability at least 1 - 6, holds that
Regret( S Ō(HVSAK -HS A).
Proof. From Theorem 6, we have:
1V Regret(K)) (K) < A V
K
K
D
))
nthh
(st)4, + 2 k=1
> (+
1 +
V
k=1
k=1
2 Σ st (s)
Choose d min(11 (1, /
SAlik2,K
Vk: E [K] and denote ((K) =
kmm
we have
Σ 9e (x+)
9V K
K A Vi Σ
9V H 2
SAL1E2K
g (s
K minn 4
9K
K
k=1
SAL
181 (K))KK
18 ((()) (SRDO)SAKAAE SAKEE
28

---

Published as a conference paper at ICLR 2026
From Lemma 7, we know that
K
KH SA
12V 12H
(* S 8))K)
1
k=1
96V H
240V 52 Al2 + 12 12H
AK
{1, T SAL1l2
K
12H
96V 96V max
+ 240V 5 2 Al2,Kla, + 12
12H
96V 24V SAKE122 + 240V S² Al, Al2 + 12 SAlog
- /AKE + 336V 52 AC, (1 (1+ k2,
where we denote '' == log 21HSA[1+)og as an upper bound of both &,,x and fz,x, and merge into the non-leading term.
Combining these two together, we get:
K
D
Regret( K) & (42 (K)(K)) V SSAGEKK + 5 Ae + (2,x))
Σ
+
+
1=1
11
(42 (K)) Rmaa /SAKK(, + 336 2
Ae x (1 k2 )
+
o
Φ
VH
where only the last part left to resolve.
Given 4 = Raa Ag. we have one additional source of O(AK), which will be merged into the leading term. In addition, note that
R SA
K KVT
122 SA
vi
< 5 SA),
which only increases the non-leading term by some constants. So overall, we have:
Regret( = Ō (HVSAK+ + AHS?A)
F.8 SAMPLE COMPLEXITY
Theorem 8. For hoiit episodic MDPs, with probability at least 1-6, 8, the sample complexity bounded by
(( H 2
((ESA
HS²
log 1 !
For finite-horizon episodic MDPs, the sample complexity of an algorithm is defined the number of non-e-optimal episodes taken over the course of learning (Dann & Brunskill, 2015; Dann et al,, 2017). If this sample complexity be bounded by polynomial function f(S, A, 2 8: H), then the algorithm PAC-MDP.
The proof is analogous to that of the infinite-horizn case in Appendix G.8; therefore, only
provide a sketch.
From Theorem 6, know that the per-step regret can be bounded follows:
29

---

Published as a conference paper at ICLR 2026
(*(st) - (5f) -
( (
AeVA + (8+) + +x
+ (3- 2
DE d +
2
V
2 (*
V + +2
+
4 +
k
V
L22,
Li,k
We choose As E881 so that we have L1,5 S & and La, S 1. So the remaining step is to prove
that majority of episodes satisty (st) I 4. which implies L2, S &.
The following notations are to connect the number of non-optimal episodes with (sf))
Let the set of non-optimal episodes within K total episodes be defined Dxx = (k [K]
Jk (++) > } and its cardinality [[ We overload the definition of visits that occur only T--
as) = Σ
Σ
a() < (oor,
REI
(*, = E
Σ I((8, at) (s,
min E [M):
: af) > (5 at),,
h exists.
H+1,
otherwise.
Akin to Lemma 26, we can bound I using the fact that J (s/) > 4
Definition 3. Let ((K) be defined by
W(K)= = 3456R2 max
(P 480 S Al2,x 24 HSAA1,K
Lemma 9, For finite-horizon episodic MDPs, under high-probabilitty event C, holds that
Txl S ((Tx)))
for all K E N. Proposition 2. For finite-horizon episodic MDPs, let Ko be defined as
Kg 6920 R H2S Al Es.e, 480Rmar S2 A(28, + Es,
22
Then the sample complexity of EUBRL is at most Ko with probability at least - 5.
Before proving this result, we need bound the the other way around i.e. W(Ko) Ko- Lemma 10. It holds that
W (Ko) < Ko-
Proof of Proposition 2. From Lemmas and 10, we know that | < W([ x|) and W(K))
Ko- It implies that [[x]] * Ko for all K E N. Since [[' increases by at most starting from Tol = that is, [ K S [[x]
for all K E N, we conclude that [I [I'l < Ko for all K E N. Otherwise, there exists K" such that Tx | > Ky- Assume K' is the minimal such index. Then follows that [T 11 Ko, which leads a contradiction.
G PROOFS FOR INFINITE-HORIZON DISCOUNTED MDPs
The difficulty in proving quasi-optimism and bounding accuracy is that we longer use back- ward induction on the horizon, since the value function is imeeiindeenndet. To resolve this, we construct Bellman-like operators bridge this gap.
30

---

Published as a conference paper at ICLR 2026
G.1 QUASI-OPTIMISM WITH EPISTEMIC RESISTANCE
Lemma 11. For infinite-horizon discounted MDPs, under high-probability event Aî n A2, it holds that for all S,l E N,
(*(s)- - vi(s S ( (2- (*))
2V (1))(())
Corollary 2. For infinite- infinite-horizon discounted MDPs, under high probbbbrbbbiiitty event AJnAZ, it holds that for all 8 E S,t N.
(ss) Ae (2 p (8) VT.
To prove Lemma 11, we need define Bellman-like operator that contraction mapping and monotone.
Definition 4. Let operator Ti be defined by
(T) = (Pl* Rmax - b' (s + (1 - (s) - (s),
+7 + PP- (+(,T(()' + + ( (s, (b)))
Lemma 12. Ti is contraction mapping and monotone.
Proof. Denote
M(s) (s) Rmax (s, (1 (s)) (1(s -(),
? P Pt) (*
For any U.V [0, V7 have
ITU Vl sup (M( + (e((s)+?(U(ss.+())) (MI(s) 22'())
ysup (U (U-
~ - Vl
Therefore, Ti is contraction mapping under co-norm.
On the other hand, given U.V E [0, 1715 such that U(s) S V(s), Vs S, we have
(TU - (1))s) = Pt (U - V) (s)
$ 0.
Thus, Ti monotone as well.
Lemma 13. Denote [s) Ne ((2- phr (s) (8) 227 (V)) under high-probability
event A n AZ. it holds that
T S
Proof. This follows the same procedure as the proof of Lemma except that we apply Lemma 34, the boundedness of the discounted value function, and the inequalities stated in the events A and A3.
Now we prove Lemma 11.
Proof of Lemma 11. Denote AV -*--"t Vt
Since Ti is a contraction mapping, by the Banach fixed-point theorem, there exists a fixed point V such that V limg-+oo (Ti)* ) g from an arbitrary initial point g.
Note, AV < TAAV. By monotonicity and contraction of Tj from Lemma 12, we have AV < &
TAVV limg- (T)) Av V. By Lemma 13, have Tif < f. by monotonicity and con-
traction again, we have V = lim (T)) Tif < f. Combining two sides, we conclude that AV < f. which completes the proof.
31

---

Published as a conference paper at ICLR 2026
G.2 BOUNDEDNESS OF COMPLEXITY
Lemma 14. For all E S, E N, it holds that
V*(s) ((()) S Rmard: Dc-
Proof. See the proof Lemma 3.
G.3 BOUNDEDNESS OF ACCURACY
this section, we bound the accuracy term. Although it is tempting to use the same logic as in the previous section, it is worth noting that the nuance in the definition of J prevents this, no longer have an argument analogous to Tif S f. We state the main result in advance, followed by its proof.
Lemma 15. For infinite-hwrizon discounted MDPs, under high-probability event n A] it holds that for all s S,t N,
V'(s) V (s) s ()) (s).
V**(s)
Before we dive into details, we define the following relevant quantities. Definition 5. Let (s) be defined by
(s) = de (3- (3-2 (s) 1 (V))(()) + TV²
((8))- (o-e-(v(s) + SS))
2V.
where (s,
ViG P+())) (s,
('ssa)
(((s) = (s) (s)
S, = 3 P))
\.V. + Pt.
2
which
3V, &
+ 30V (lssss(((s.)))
({ a) = a)
d
Definition 6. Let operator To be defined by
(T2V) (s) == A, ms)) + 2,3 +(())) (())
+
Definition 7. T is affine if, for any vector V and E
T(V + E) = TV
Lemma 16. To a contraction mapping, monotone, and affine.
Proof. The argument for contraction and monotonicity is similar to that of proof of Lemma 12. For the affine part, we observe:
(V + E) = AD() + 28th + yP(V + E)) = =D,(D')) + 23 + +PV +*PE
= TVV + +PEE.
Lemma 17. Under high-probabiliity event nf A7, it holds that
A, (V' (V''-**)(s0) (s) (D))) Te(a)) 2, (s, Te(a)).
32

---

Published as a conference paper at ICLR 2026
Proof. The proof is similar to that of Lemma 35, except that uses +s) 0 from Corollary and Lemma 14, an application of Lemma 34, and the boundedness the discounted value for variance decomposition, together with an adjustment of some constants under the event Ag. M
Now we prove Lemma 15.
Proof of Lemma 15. Denote AV = -
Note, (s Ay (AV) (8, (5)) 7P (AV) (s, (s)), By Lemma 17, we have
AV $ T2AV.
Condition
For brevity, we denote g := 8" tPP' ; min V and D = Dr We observe
Tz(D + 2 D 2g.
Condition
Moreover, since 2 6 V and AV S y, we have
AV D + 2V
Condition
Now, we claim AV <D 2f f is true. We consider two cases:
Case 1: g(s) 2 V For any state s where g(s) 2 V7, the function f(s) is defined as f(s) = Vi- The inequality we want to prove becomes (V(s) S D(s) + 2V,, which is true by Condition 3.
Case 2: g(s) VsJ For states where g(s) V7L the function f(s) is now defined f(s) g(s).
We prove by contradiction. Assume there is at least one state where g(s) < Vi and the desired inequality is false.
We define an "error" function = AV (D++ By the assumption, the set of states E = {s S (s) > 0} is non-empty. Let F" Sl1P.es E(s), then E" 0.
We start with Condition 1, that is, AV < TAV, and substitute AV = E + 2f), we get
E + (D + 2f) S (2(E D
By the affinity in Lemma 16, can write D+ T2(D + + +.EE. By Condition
2, we have T2(D + 2f) = + 2g. Combining this with Equation G.3, we obtain:
E (D < (D + 2g) +PPE.
Rearranging it, get:
E 2 f) +PE.
Now, let consider state s* where the error maximal, i.e. E(s*) E must hold that: E". E(s*) < 2(g(s*) f(s*)) (PE))
"((g(s*) - f(s*)) +(()))))E(+))))))
Thus, get
(1 (1-7)E(s*)) < 2(g(s")~ - f(s"))
Since g(s) = f(s) whenever g(s) < V the above equals to zero, implying E(st) S 0. This leads contradiction. Therefore we conclude that AV D + 2
Bounding (s)(s) using steps similar to those in the proof of Lemma 5, we obtain:
Corollary 3. For infinite-horiin discounted MDPs, under high-probability event no A?, holds that for all S,t N,
2 pt. (s) -
42
- (s)))V((()) 3
(s) 3 -
XeV, + 23) +
Xe
1.7
33

---

Published as a conference paper at ICLR 2026
G.4 PER-STEP REGRET
Theorem 9 (Restatement of Theorem 1). For infinite-horizon discounted MDPs, under high- probability event B, it holds that for all E ESLLEN,
$
-R((s) A (s) +0 (*(s) - (s) 2
Φ
Proof. Combining Corollaries 2 and 3 with Lemma 14 gives the desired result.
G.5 BOUNDEDNESS OF J
Lemma 18 ((Lee & Oh, 2025)). Les C' > O be a constant and {Xele be a martingale difference sequence with respect to a filtration {Fi]e with X, S almost surely for all N. Then, for any À E (0, 1] and 5 E (0, 11, the following inequality holds for all n E N with probability at least 1- 6:
1
31
C 1
X
Σ F[X
log
4C
A 8
Lemma 19. For any time T, we have
Σ + SA log, 2T.
Proof. The general idea is similar the proof of Lemma 30 in (Lee & Oh, 2025), but unlike the episodic setting, where episodes exhibit monotonicity, the infinite-horizon setting requires special consideration to handle coupled trajectories. By focusing each individual state-action pair, get:
T
T
Σ 1 #
+T+1)=>
Σ
Σ
1 +T+ (8 attrr = (s,
1=1
t=1 (xx))E8xA
Σ
1(+4 Σ
T + 1,, = (8,
(s 1=1
If + v1 + 1, then + 02 is the first time step more than double the anchor L. Therefore, we have (((+))))s atte,) 2 2N atte, + Since any step that greater than + 24 is an inclusion of n (f(p))) we have (((++c+o) (St+2: Ot+u,) 2 2N* 2 actv:) + for any E N. Based on this condition, we denote MT(s, a) the number of steps & E 21,2.... T3 such that ((++u+t) (8,a) 2 (N a) + 1, then, we have:
Σ 1(t uu +L+uTT+IN (tt.) (s,a)) S Mr(s,a).
We aim to bound the right-hand side above by finding contradiction between a upper and lower bound of (o(ttcto)ss a). First, since there are most (T - t 1) time steps left from the anchor f, we have vottm)+)) (s, < (*(ss,) + (T t + 1) - N a) T. Combining this with ((+++++) (s,a) 2 2N + 1, we know that it occurs only if N' a) < T. Next, we prove by
induction that
P(t) (s a) 2 ( - 1.
To verify this, let c and define a sequence of "checkpoints" that starts with
to = fx+1 = t Vt, +
Because Vig O, we have + t 1. Also V/, < T + 1 and tz 2 2 give t++1 S T. Hence {tx } is a strictly increasing sequence bounded above by T, so after at most to steps (114,,) then, by the above
reach (x T. If the induction statement holds for any step
34

---

Published as a conference paper at ICLR 2026
progress and termination argument, it follows that all steps covered.
Let's first verity the base case P(L), for which have Mo 0 and NO) 0, there- fore the inequality holds. Then assume P(to) holds, there are two cases to consider. (s. 2 (s, + 1, it implies that (s,a) is the first time step that triggers the stopping of Vt, leading to (V(ttett)(ss a) 2 2 (M.-1(x.))+1
1. More- over, for each intermediate step 1 with 1 < 1 Vt, P(to + 1) holds; On the other hand, (8.a) is not the pair that triggers v4, this means that it has not been doubled yet, imply- ing M1+0, (s,a) ((t++++)) (s, a) 2 (s),,)) 2 2 ((8,a) -1 2. (e,a) - 1. Thus, conclude that the induction holds.
= (MMtte
M-1(88 a). However, there may still be
increments, and therefore
This gives us a lower bound, suggesting Ms, a) cannot grow faster than logarithmically in T. Formally, once (s, a) reaches [log, T' + for some t. it cannot increase further, since (* a) < T. Therefore, we conclude that Mr(s, a) S [log2 7 + 1 S log, 2T', which completes the proof.
Lemma 20. For infiittehhorizon discounted MDPs, under high-probability event AG n A it holds that
24
13V1
12T
(st)
1 (8t41, 0(41) + SA log
for all E N.
Proof.
Bounding (s) Given a T-path (s1, 0i, ST, aT,ar, Pr, ST+1) where actions are chosen from ((())) each time step, we decompose Jí (s:) as follows:
(s:) ('ss 0z) + t. ('t, + PPJ (st, at) - ( (J
21
+ + (144,, J' ('(444+1)) th (s(tm))
S
$2,1
Then, we take summation over T steps:
T
T
T v4
T
(x)
<
S +
S2, +
2
Jt (84t)))
t=1
t=
t=1 t=
1=1
35

---

Published as a conference paper at ICLR 2026
Bounding Is
By Lemma 19 and (((--1) S Vg, we get:
T y J (s(+2)
13
- J
1(t (1++v: 1/ * T + 1)7 (sttve) +
1(t 2+T+++1-- 1)7% J' (s(tm))
1(t+ 14 * T J +
Σ
= 117 1 T++1 ((T4)
V
1 + T + 1)
+
1-7
V
1(++ 1/ # T
1 1-7
Vt
I VT 2T +
1 1-7
Bounding 1/
T 14-1
12 =
S2
1 1t 1)82,1
111 - 12 (s44,,))) -
- (((4)-11)
1(T - 13 1 - -- (PJ' - J (8)-)))
b
- ( az) - J ())++)))
where (a) is due to the exchange of rows and columns and (b) to the reverse of the roles of indexes.
Note that in the final step, we make bag of martingale differences with the same time index;
therefore, it is not hard to verify that X, is a martingale difference sequence, with E[X, [i]
0. F(( = Var
Σ 1(t- S vr - 11) +1 (8L-1) (st, az) and bounded as [X,] S
vt yVT <
Denoting ('((++1) == Σ 1(1 - + & Suz - 1) Jr (81+1) and applying Lemma 18
1
T=1
36

---

Published as a conference paper at ICLR 2026
to (Xi) with À
8. we get the following:
T
1
Σ
X
1=1
(1 - 7)
T
6V, log 5
Var (Y'(s4+1)) (st, az) +
8V
Next, we will bound the sum of variances L. First, we look at each individual variance.
L = P (Y'(( (st, ax) + (PM(())))))))))))))))))))
= P (844))))) (se, ai) (PY ((+))))(s)))))
= =((((()++1) (st, at) -Y"'(++++))
+ +(*((5++1) + PY (XY Pr
2V (Y'(s(+1) - PY (())))))))))
S P (X (s), - (X' (5++)))
=2+
Akin to the previous argument, the second term is martingale difference sequence, therefore, obtain:
T
1
Var(Y"(( + 6V 6 log
(s++1) - (*+))))) <
8V 1=1
7 8"
Based on this, we can simplify the bounding on L:
L
2V T
Z +
Σ
(s411) - PY (r
1
1m
tm1
2V1
(1 (1-0
Var(Y a.) + 60 6
Z 1 1-7
1 y log
8V.
12V12
6
Σ 74
(Y
(8+
+ (1 7)
log
T
12V12
Σ 1=1
2, +
L+
+
log
4
(1 (1- 72
12V12
Zz +
L +
log 8'
(10)
4
(1 7)2
1m1
It is not difficult to check that ) is a martingale difference sequence, with E|Z = 0. [(( = Var (Y'(s<+1)))) (st, ar) and bounded as |2, S (I-7)= Moreover, by applying Lemma 9 in (Lee & Oh, 2025) to the second-order moment, we have:
4V12
Var ((*(()+11)²²) (st, ar) - (1 71- Var (x*())+1) (st, at).
37

---

Published as a conference paper at ICLR 2026
Combining this with Lemma 18 with À
12. we get the following.
1
Σ
T
2
T
Var (Y" (8++1)) (sts ar) + (1 7)2
12V
log
6 8
1
12V
6
L
+
log
(1 7)2
Substituting this into Eq. 10, we obtain:
T
1
12V
6
L
Ze
+
+
log
4
(1 - 7)²
8
1=1
12V12
log 6
1 L +
12V
6
L
+
log
(1 7)2
(1 7)2
2 1 24V122
log 8'
(1 7)²
which has a recursive structure, leading to:
48V;2
6
L 1 (1 7)2
log
8
Substituting this into 9, we have:
7)
6V1
12 x
L + 1
log
8V.
(1 7)
48V12 2
6 +
6V
log
log 3
8V
21
8
12V 1
log 8
Finally, we conclude that
Σ (()) $ + 12 I3
12V1
6
V
< h
log
VY 27
1-7
13V1
1 +
log
V SA log, 2T
1-
13V1
6
VJ
< +
log
SA SAlogg 2T
Y
7
13V1
6
2V1
1h+
SA
+
SA log 2T
1-
8
1-
13V1
6
13V1
< + SA log
SA log 27
5
13V1
12T
I + 1 7
SA
8
which completes the proof.
Lemma 21. For infmite-horrion discounted MDPs, under high-probabilityy event AG n A. it holds that
T
(2((")
T
12T +
13V1
Σ
(x)))
SAlog
1
SA log 8
-1-7
SA
1
for all T N.
38

---

Published as a conference paper at ICLR 2026
Proof. Based Lemma 20, only need to bound 4, which is series of discounted sum of 3 By the definition of the stopping time V4, we know that for any t that satisfies t-r S 1/2 - 1, we have ns,, az) & 2NT a.) looking back at a previous anchor r. Moreover, 2 must hold, otherwise it cannot satisfy the condition. We denote the set Z(s, a) S (1, 2, 7) as the time steps at which the pair (s, a) is encountered.
infer that n' (s 0z) 2
T
1
A (8441:
10 1044-11p7 (1)))))
1(7 117-1S 1s - -1)7- (8,, ar)
T S -1)7 Br (st. mz)
1(t T M v 1)n²T ym
ΣΣ T=
NT ac)
S
1(t 7 S 17 1)t (s,,
T
1(1 7 7 S U, - -1m² /J
at)
T
(4) y(
- 1) 2 2)7 - S 11-T5
2
a)))
r=1
< <2
Σ (n az) 2 2)
Σ 1(t S vr 1)7
ni' n' at)
2)(T)
Σ
Σ
((n 2)
1-7
ns
(s.a)ES X (EE
N
2)(7)
Σ
Σ n=2
1-7
n
(sa)ESSA
2)(7)
Σ
log (1 + NT+ (s)
1-7
(s,a)ESXA
()(T)
T
< 1-7
SA log
1+
SA
where (a) holds because we can distinguish two cases:
If - V,- 1. then the indicator 1(t r S v, - 1) is zero, the product vanishes regardless of the other indicator;
If T S er 1, then, as shown earlier, we have n (1((1,,)) az) 2 2.
39

---

Published as a conference paper at ICLR 2026
G.6
LOWER BOUND OF EPISTEMIC RESISTANCE
Proof.
Σ at)
=1+
Emax
N a1)
T
21
vt-1
max
=1
Emax
Vi
p++ 1
2 1 +
dx
Emax t=1
Vr
+
dr
Emax
.1
Vz
1
(2VT -
&max
Note, this also holds for (st, (s))). Therefore, multiplying with AVV completes the proof.
G.7 REGRET ANALYSIS
G.7.1 PROOF OF THEOREM 2
Prior to deriving the regret, state the following lemma.
Lemma 22. holds that
4T S + E2.T.
for all T N.
Proof. Expand l,, and relate it to 42,7, we get:
12T
4. log
8
12(S A + T)
< log
12S
+
T
log
3A
128A
T
log
+ log
1 SA
< f1 + L2,T.
Proof. From Theorem we have:
Regret(T) 7 Σ A
1V T
V Σ
T
(s)A,
+ 2 1e + Σo Φ
T
T
(1+
|
4 V.
2
t=1
[=1
1=1
t=1
40

---

Published as a conference paper at ICLR 2026
Σ
(s)
Choose d = min(1,3
1A E (7) and denote (T) =
we have
T(1-?)
92
T
Σ (s)
9V6
T
T
1V
VØ
H (s)
1=1
Tmin (1.3 (1.3
2
2
9T
T(1 ((1-7)
1=1
1=1
Rmax
SAl122T
$ 14 1-7 (1 (
T(1 77)
Rmax
= 14 (1 - (T)) 1 SATE,
From Lemma 21, we know that
4)
T SA
26V1
12T
(+1) - 1- SAlog
1+
+
7 SA log
1-7
48V 48V15AA11 S2,,
120V
26V
12T
52 Al2, +
SA log
(1 (1-7)>T
1-7
1 1-?
8
48V, S.V.
T(1 (1
120V
26V
12T
(1 (1-7)
max
131
5AL1
1-9
S² Al2,Tla,T
+
1-9
SA log
48RmaxS SALI,TE2.T
16.mmx
120Rmax S² Al2,7L3,T +
26l2max
12T
SATE +
SA log
(1-7)2
(1 11.5
(1 7)
7)2
8
(8)
m6
120 5² A62,733,
48R max SAP1,
26 SA(E1,T + l2,T)
VSATE122 + (1 11.
(1 71-
(1 (1-
(1-
16
1 5² Al2.T
48R S SAC A.
26
SATMee +
S SA . + l2,T)
1..
<1-
(1 7)2
16
120R
A8 A + (22TT)
26
SATH
52 Al2,1 +
(1 (1-7)2 SAl2,3
(1 1-..
(1 (1-
(1-
16Rmax
120
48 48 SAC, + +b2,r)
SATE,12,
52 A62,T(1 + +G,)) (1 7)
(1 7.
(1 (1
16
168 S² A(1 ( (1111440 12,T),
SATAR22,
(1 1)
7)
where (a) uses the Lemma 22, and (b) l is denoted as log 21SA(1+HogT)
therein f 2 E1 and
8
LT 2 la.--
Combining these two together, get:
VSATE,E2T
S2A (1->)² (1 + (1 +2,)) +
T
)
Regret(T") < (30 (T)
(1 (1-7) 71.5
+ 168
Σ
1+
v.J
where only the last part left to resolve.
Given .; = Rmax we have one additional source of ((T)), which will be merged into the leading term. In addition, note that
T
T
R12
SA
max
TV.
(=1
R2
SA
5
V
O R.nx.uSS.. SA),
41

---

Published as a conference paper at ICLR 2026
which only increases the non-leading term by some constants. So overall, we have:
VSAT (1--7)13 +
S²A (1 71-
RTg =0
G.7.2 STATE-ACTION DEPENDENT (s
Definition 8. Let G be defined by
46 (vi-ag) Pu(s,a))
9= Σ
(KR))ESA
where
Pī(s,a) (in a) ( (s)
Pu(s,a) == min
min ()) 25ngNT=1(ao) (n)
Notably, we have the property & that 17SA < G S SA. The maximum is attained only (s. 0, ((s E S x A.
03
If the epistemic uncertainty is non- non-increasing, then (u a) is corresponding exactly the epis- temic uncertainty at the end of learning, that is, PT a), reflecting the systematic uncertainty of a particular state-action.
Lemma 23. Denote (8) == / (e.
it holds that
Σ 44
3v2l1, glog (1+7)
N' (1841,444))
(1 - 7)
42

---

Published as a conference paper at ICLR 2026
T 1- Σ Σ T (144), we have
Proof. Denote ==
1=1 1=0
l1,
9
1(t v, 11--10 - -1)
NT(s;, at)
VV
99 (st, as)
T
261
9
1(t T S v, - -1)
Ri (s,, at)
n² n at)
VV
(0)
T
3 20
ΣΣ
1(1 - S 14 1)7*
V2 9i (s), at)
1=
(b)
2 3V
1(t T M 11)
1
(V1-
46
63 (s at)
nz n ac)
1=1
t
46
=3 ΣΣ
1(t S 14 1)1(n' az) 2 2)
pr ( as)
n (1( az)
63
1=1==1
S <3V2l1.7
1( (5), at) 23
1(t - - 1)m2 t- Σ
46
pū (,,, aI)
n'(s,, as) 7=1
63
46
<3v2l,,
2 2)
(v1-
min P7 (((s)))) 4z) ISTSt
1(t - - S ur - 177-
n¹' (1)
63
3V221.T
46
1nr ax) 2 2)
(
min (s))
(1 (1-7)
n¹ n(
63
Isrst
S (1 (1-
3/221,
Σ
Σ
(s, 2 2)
03
minsrre (s)
(8(
(5,a)E8x (EZ((.)
3V
46 63
min minls (8(
Σ
Σ
(1-7)
n
(s,0)E8xA
n=
32221I Σ
46
(1 (1-7)
V
63
min 25
(s.o) (STSt(a))
min
P)(
(s.n)ESXA
n2
3/201x Σ
46
V
Po((,a)
log
(1-7)
63
(s,a)ESXA
3//01, glog 5 (1-
(V1
46 Pu(s,a)
03
(1 (1+1)) CL+N++I (s,a))
Σ
g
(a.))EXA
(V1
46 Pro(o,a) (N)+)(s,
3//21.7 glog (1-
Σ
03
1+
g
(s.a)ESXA
31 glog
NT+2(s,))
Σ
1+
(1 71
(s,a)ESxA
(0) 3/221,T glog 1+
T
(1 7)
where we have used the following facts:
43

---

Published as a conference paper at ICLR 2026
(a) Monotonicity of 1,r
(b) Rº (5), 0z) 2 2 Pf oz)
(c) Jensen's 's inequality
Lemma 24. For any T N and x E [a, 1,", < a < b, define function G(x)
Σ
and
n=
f(x) = G(x) log (1+ ) we have that
f(1a) S f(x)= S f(1b).
Proof. Using the elementary fact that g(u) ulog (1 + 4), u > is nondecreasing on (0, oo)
completes the proof.
Proof. From Theorem 1, we have:
-
1 p
))
Regret(T)
V
A (5)), +2 2 +2Σ (s)
- Σo 0
2
V
t=1
1=1
1=1
T
))
9
V
(s)
\
Σ [x(s) Σ 0
1+
7
2
V
Choosing A = min
1,
C
SAt I(1-7)
1A E [T], we have
(+)
9
T
C
SAL1,162,
(s)
d1 = V
R)(ss
min
1.
1=1
2
[=1
9
2
(+)
T(1 ()
Rmax
T
SALLTE
< 0
v/2 -s)
1 7 t=1
T(1-7)
0 Rmax
T
9 T
Σ (s))
SAl,,T22
1 1-
T(1
C Ponax
(
9
2
T Σ (s)
SALITTET
(1 1.5
1.5
Ji Σ ot((s)
Given
12
y =
+ -33,,
d
// - (s)
(s)s
T(1 - 7)
12V b1, max
1,
+ 30V SL
C
SA
12
9
7(1-7)
12V 112 +
vte
(s))
Sla..
C
2
SAl1,
y
y
3/
44

---

Published as a conference paper at ICLR 2026
From Lemmas 20 and 23, get
T
T Me11
26V1
127
2
(5)
Σ
(s141, +
SAlog
1 1-7
1=1 1=
yr
26V
127
2 rl
+ 1 7-7
SA log
N (st, (t))
6
26V
12T
2 Σ
Σ
1(1
14 1)7
1)7 7 (T(8,, a+)
(VI + +33) +
SA log
8
r=
48V SS0
(1-7)Ar
72
T(1 7) SALI,T12.T
(G22T)
C(L-7)
120V
1-7
26V1
12T
SA 8
7
72 72
168 168 5² Al1, (1 + f2,7) (1-
V
C(1 1-)55
7)2
Combining everything together, we get:
Σ (s) + +2()) + 168 Rmux
T
$
)
Regret(T") J1
52 AlA,,T(1 (2T)) +
0
d 1+
(1 7)2
Vil
T
So, depending on the contribution of
Σ R and G, we can get different bounds. In what will
follow, choose C ===33 3 -
Disregarding 9 Even ignoring the first part, we can obtain tighter bound where the leading term offset by the sum of epistemic resistance
R (s) as follows:
T
Σ (x)
Rmax
168 Rmux 1ma (1 - 7)2
Regret(T) <
16 + 14
-
9T
1). (1-
(1
SATH
+
52 A61, + b2
T
p
)
+
o
Φ
1+
V
t=1
Considering Both
Let N = SA, a =
17
1, by Lemma 24, we know that
631
17 V
T
T SA
SA log
1
G6 S SA log 1
63
17 SA
63
45

---

Published as a conference paper at ICLR 2026
with this, at best, we can achieve:
17
2.7
2
Rmax
168
Regret" (T) S
16
+
14V
(1- 1- v SATE,, +
52 Al1,,r(1 + E2T))
63
22T
(1 7)-
4
+
p
+
V.
t=1
the ratio T is large, then 2, = 2. Therefore, the overall reduction is by a factor of 3A
63
0.519. In this case,
improve the constant in the leading term by roughly one-half.
Lastly, the treatment of the part of d is similar to that the uniform case. Therefore, we ultimately have
VSAT
S (1 - 7)2
(T) = =6
71-
+
G.8 SAMPLE COMPLEXITY
For infinite-horizon discounted MDPs, the sample complexity of an algorithm is defined as the number of non-c-optimal steps such that (*)(s) S (*(s;: - taken over the course of learning (Kakade, 2003; Strehl & Lituman, 2008). If this sample complexity can be bounded by polynomial 1 function S(S, A, E: 82 1-y), then the algorithm is PAC-MDP. We are interested in proving PAC- MDP for the full range E (0, V.7.
From Theorem I, we know that the per-step regret can be bounded as follows:
99
T V
(*(8)) V (x)) S
AeV 2J2(()) + +
1+ 2P (8)) A
9 Ay (s))
D
<
Ao1 + 2.x( $
4
V
12.1
I.s.e
For L1,t, choose A
1851 that have L,, $ 1. In addition, note that o Rmax
and X; 18955= I is substituting it into L3,1, we have:
2
<(1 7)
4. Rmax>1 = Rmux
<
18V,
18
18
R2 X2
1
R2
<(1 - 7)
182
V
182
182
Therefore, obtain La,a
[13
If prove that L2,1 5. equivalently, Jz < 5. then the time step t can be said to be optimal. To achieve this, we introduce a set new notations that explicitly connect the number of non-optimal steps with J (s.).
We define the set of non-optimal steps within T total steps as I7 E {T] J((s.) }. and its cardinality [ Then want prove that [r]| is polynomially bounded for all T E N.
46

---

12[L'T] Published as a conference paper at ICLR 2026
For analyzing non-c-optimal steps, it is useful to overload the definition of visits so that it only includes those occurring in Pr.
a²) Σ a() (s,
ACT
a))
Σ 1((s); = (s)
tET1-1
min(T [t, : n (s,, > (sr, if exists.
Vt
T+1,
otherwise.
Next, we bound the sum of Jr but only for the steps in lT.
Lemma 25. For anfinite-hoiizon discounted MDPs, under high- probbbbtbbbiiitty event A n Ag, it holds that
2)(1FrD)) Σ (+)) S 1 - SAlog
(1+ [rl
13V
+
SA log
SA
1-y
8
RT
for all T T N.
Proof. The proof follows the same procedure as in Lemmas 19-21, except adding the indicator function ( Tr) each time step.
Based on the above result and Lemma 22, we can bound Ty using the fact that (s,) > Definition 9. Let WTT) be defined by
W(T) 1780 S S
52 Al2,T 52
(11-7)8
<(1 7)2
<(1 77
Lemma 26. For infinite-horizon discounted MDPs, under high-probability event D, it holds that
Trl < W(Fr))
for all T N.
Proof. From Lemmas 25 and 22, we get
8y(2)SAl2 52V55A((11 + E2.T)
Trl 6 (1-7)
c(1 (1-7)
Substituting the definition of (()) into the above, we have
T 1728 max SAA,, 12
240R Al,,,,, (3,117)
52R 52nmmssSA(A SA((1,Ir
+ +2,11171
<² 73
71
<(1 7)2
(a) 1780 SAL,,IT 1z
SAL,,
240R S2Al2, 22
52R SAf,,IrA e 7)
e1 - 7)3
<(1 71
where (a) uses the facts that V 2 and (,, 2 1. therefore concludes the proof.
Proposition 3. For
discounted MDPs, let Ty be defined as
3670 2(1-7))
480 S2 A22((2) + (i.e)
<(1 <(1-))
Then the sample complexity of EUBRL is at most Tp with probability least - 8.
Before proving this result, we need to bound the the other way around i.c. W(T) < To. Lemma 27. holds that
(T.) To.
47

---

Published as a conference paper at ICLR 2026
Proof. Denote B
R- &1 2-11-9)"
+
Ron S(26, +
therefore we have To S 3670 ACs, where
<l1 <(1-))"
f..c log (1 + 140B) I 5B. Then we have:
To
22.T log
1 +
SA
s 2.5,e.
Moreover, we have:
4SA
1 S 8
V1
8, - c(1 - -7)"
Therefore, we get:
8SA
V
281 + lo.e S
8
c(1 (7)
9VTSA
5c -7)"
We use this to bound B as follows:
R
R S(281 lo,c)
B
(2 7)3
<(1 - (1-
4R2 SA
9 S²
+
8ca 7)3
dc² - 7)
13 S
(1 7)
With this, now bound log To. which is part of E3,To log To S log 18350B
169R4 max A² SA
S log 18350
82
7)8
18350 x 169
R4 S4
log
SA
e4
8 (1 - 7)8
568005 A3
V
log
log c²(1 - 77)
82
== =1
We now bound L1.
568005 A
L =
log
8²
5680055 5
log
85
9 $5 AA5
log
85
9SA
5 5
8
SA
< 11
Therefore
SA
Vfe
log To $ 11
+ 4log
5
e(1 7)
15SA A
Vie
log
8
c(1 - 7)
48

---

Published as a conference paper at ICLR 2026
Then, substitute this into Es,To we get:
125 + log To)
l,,, log
12SA
log
+ +log (1 log To)
8
15SA
Vie
11 log
1
log
(1 7)
(n)
16SA
Vie.
S 81 log
log c(1 - 7)
8
(165AA
Vie
$ 61 + log
+ log log
5
c(1 -7)
$ 261 + 6o,e.
vfe where for (a) we have used the facts that SA and log c(1->)
>
Now, we prove (Th)) < To- Since 2 1, therefore Es.c 2 log 141 > 1. This leads to To 2
36705' A, henceforce 6,,, 2 1. Along with VI 2 1, we have:
W(T)) 1780R2 SAC1, T. 22,70
240/ S2 A2
+ c(1 -7)2
<² 7)
(1 7)7
1780R S SAA, 1,TT f2
240R 52 A22,T, C3.TO
52 SA E,
+
e²(1 - 7)3
(11-7)²
211-7)²
1832 mux S.A1 E,,
520lmaxx52A2222 La.TO
(=(1-7)
<(1 71)
= (Tb)
Substituting the bounds on logarithmic terms, we obtain:
(TT)) s (To)
3664/12 SAl
480 S2 A2Als,e l6.c)
e²(1 - 7)3
c(1 7)2
3666 max SAl.
480 52 A2,,,, + ((a,)) -
e11 - 77)3
7(1-7)2 480/ S2 AlA,,, + lloc))
3670 min SALE
-
<2 73
<(1-7))
3670R2 max SAlies,
480 52 A22, + E6,c)
+1-2
2(1 7733
e(1
3670R2 max SALEes.
480R 52 A2,,,, + la.e)
e1 7)3
<(1 7))
To
To.
Now, we formally prove Proposition
Proof. From Lemmas 26 and 27, we know that [[>] < W([T]) and W(T)) < To. It implies that [Ty] + To for all T E N. Since [r increases by at most I starting from [Tl = 0, that is, Tr+1l S [r]+111 for all T E N, conclude that [r < To for all T E N. Otherwise, there exists T" such that [ > To. Assume T' is the minimal such index. Then it follows that [r 1| = To which leads to contradiction.
49

---

Published as a conference paper at ICLR 2026
H POSTERIOR PREDICTIVE AND EPISTEMIC UNCERTAINTY
In this section, we will give backgrounds necessary to relate the Bayes estimator to the MLE esti- mator.
H.1 POSTERIOR PREDICTIVE
H.1.1 TRANSITION
Lemma 28. Let by = Dir(a) be a Dirichlet prior over transition for a fixed (s, a) E S x A, and define og = a the sum of prior parameters. Let n. denote the total number of visits (s,a).
Then, the following decomposition holds:
n
(P-
00 (Pho P).
Po - P
+ 00
0x0
for any posterior and n E N.
Proof. Note Po
we get:
og
Pb
P
n1 + Og
n&
Po
0g n+ +
P
n n a0
11 +
n
(P-P)
+ + 00
ag
(Pop - P).
n1 + ag
H.1.2 REWARD
Lemma 29, Let by == N N(o Ta) be Normal prior over mean of reward for fixed (8, E S x A. and T the precision of the data distribution, which is assumed to be known. Let n denote the total number of visits to (s, a). Then, the following decomposition holds:
rols, a) - r(s,a)
+ nT (No - -r(s,a)) + nt
To
NT nt (f(s, a) - r(s,
for any posterior b and n N.
Proof. By definition, we have the posterior predictive mean of the reward:
ToHlo + T Σ r
(s a)
1=1
To
The difference to the ground truth reward is:
n
Toflo r Σ r
ro(3, - (u(s,))-(ss.)
-(s,a)) = To
r(s
(To/10 + nTf(s, a)) (To (7))(
To + nr
To(Ho - -r(s,a)) + nT(f(s, r(s,a))
To nr
To
(uo - r(s,)))) + nt
(f(s, a) - r(s,
+ 12T
NT nt
50

---

Published as a conference paper at ICLR 2026
Corollary 4. Let bu (gu Au ous Bu) be Normal- Camaa prior reward for fixed (s. E x A. Let n denote the total number of visits to (s, a). Then, the following decomposition holds:
Ao
ro(s,a) r(s,a)= Xo
(vo r(s,
(f(s,a) r(s,a)).
do + n
for any posterior b and n. N.
H.2 EPISTEMIC UNCERTAINTY
The definition of variance-based epistemic uncertainty for both transition and reward is:
ET(8, a) = Varw-b (B[s' (s, w)) Eg(s, a) = Varw [B[r]s, a, w])
And we consider generalized form of epistemic uncertainty to combine the two sources together: (11,,, a) = [(T((s,a),
In this paper, we consider f(x, 7l V Vy).
H.2.1 BOUNDS FOR TRANSITION
Since is meaningless to take expectation over categories for a categorical distribution, we instead choose some feature vector for each component. One of the sensible choices is the basis function e, (0, O...., ,,,.,, 0), which leads to the following formulation.
Definition 10. The variance- based epistemic uncertainty of Dirichlet-Multnonne model is defined as follows:
5 (ax + na) + n an -RR)
=
k=1 (on 2) + n +
Lemma 30. For Dirichlel prior, the epistemic uncertainty in transition follows that
(r) ( (+)
and (s( = 52 nr
for any (s) SSx A and N.
Proof. Let T = ao + n, then we have:
T - Σ (ax + nx)²
Er(s, a)
T²(T +1)
We will derive its upper and lower bound. start with the upper bound.
S Note Σ (ax + n2 2 therefore we have:
T2
Er(s,a) 5
T2 +1)
(T + 1)
1
ni + oo +
<
So (s, a) O( with constant C2 =
51

---

Published as a conference paper at ICLR 2026
Now, we focus the lower bound. Consider the worse case, where have only one state being visited, denote its index as j. we have
9 T Σ k=1
as + mx) = + (ao (mn))=(n++0) aa) + Σ
aj
= (n² + 2agn + oz) - (n² + 2aym +
Σ
a3)
j=1
s
(200 - -2a,) )n + (a}
02)
j=1
2 =2000 - -2a,) n.
Therefore
(s,
(200 20,)n
T I²(T + 1) (200- 2aj)
22
T (²(11
(20g 20xz)
(1 + 20 )²( + antl
(200- -2az)
(1 + (2 + on)
So a)) = with constant C
(200 (200-2a;) This corresponds to the case where the (12ta))))
transition deterministic or near-deterministic.
H.2.2 BOUNDS FOR REWARD
Definition 11 (Normal-Normal), The variance-based epistemic uncertainty of Normal-Normal model defined as follows:
En(s, To + rm Definition 12 (aamma)-Gamma), The variance-based epistemic uncertainty of Normal-Gamma model defined as follows:
En(s,a) = A(a A(a-1) 1)¹
where
À Ag
a 0p
2
no² + Agn(E - pa0
don(E=noo)
B = 3 + 2
No + n
Lemma 31. For Normal prior, the epistemic uncertainty in reward follows that
ER(8,0)= = (+
for any (s, S x A and E N.
Proof. Note by choosing Ci To+7 for lower bound and C2 ! for upper bound concludes. n
52

---

Published as a conference paper at ICLR 2026
Lemma 32. For
prior, the epistemic uncertainty in reward follows that
0)( 0 and (T(8,a) =
n?
for any (s. x A and N.
Proof. The upper bound is trivial. For the lower bound, consider the deterministic case, leading to sample variance being zero. Therefore the numerator ((1) whereas the denominator O(n²). [
I FROM FREQUENTIST TO BAYESIAN
I.1 PROPERTIES OF PRIORS
Definition 13 (Decomposable). A prior bu parameterized by 0 is said be decomposable if there exist functions f(n, 0), (n, n 0) for transitions and (n,, 0). s(n, 0) for rewards such that
Po P = f(n, O)(p g () P), ть r h(n, () r) + s(n, (T - r),
with the constraints
s(n, 0) )
f(n, 0) 1, h(n, 0) 1 VnEN; g(n 0) 0
for some positive multiplicative constant () and (
Note, when indexed by particular (s, a), all the quantities above can depend it.
Definition 14 (Weakly Informative). A prior by parameterized by 0 is said to be weakly informative
Ir - Fl ( and ||Po P1
Definition 15 (Uniform). A prior by parameterized by 0 is said to be uniform if there exist positive constants Cg and C₁ such that
C,(0)ss,a) Cg and C.(0)(s, SC
for any (s, E A.
Definition 16 (Bounded). A prior bn parameterized by is said be bounded if there exists R such that Ira, (s, a)1 < R for any as S x A.
Definition 17 (Restatement of Definition 1). Let C be defined by the class of decomposable or weakly informative priors whose of epistemic uncertainty is θ V
Theorem 10 (Restatement of Theorem 4). Ler (S,A, be any MDP. For any prior bo C, there exists an instance of EUBRL such that, when executed on M, it achieves, with probability least 1- 8. prior-dependen bound on regret, or alternatively, on sample complexity, depending on the choice of n.. If. furthermore,, b is assumed to be uniform and bounded, these bounds are nearly minimax-optimal.
Proof. Note, by either weak informativeness decomposability, the additional complexity is most O (g) for transitions and O (+) for reward. This applies to the events, e.g. AT which involve bounding the distance between the posterior predictive and the ground truth. Without loss of generality, we assume b is weakly informative. We bound
( (pt-P)C PVV a) as follows:
IPPo - P)V* (s.a)]= (sN (s. - (s)* (s, 0) (Pon - -s,V')s,
S
p+ (s' (c,, - Pll, V!) (²(s,))
Frequentist Bound
Prior Bins
53

---

Published as a conference paper at ICLR 2026
where the first term is simply the original bound derived in the analysis of MLE estimators, while the second term captures the complexity arising from prior misspecification. the prior is correctly specified, there is no additional overhead; otherwise, this term must be accounted for in the final bound.
Similarly, have the decomposition for the reward
(s, r(s,a)) S (s) - a)] + (C,(0) (s) -s(,s))))))) N*(s, a)
By merging all the quantities of the same order of NT. overload the definition of T y and 3r respectively. For brevity, we drop the dependency on (s, a) for each term.
S
+ (C,(0) Irbo -rl) 1
quasi-optimiss
+ + (C,(0)) Pll, V2)
N
N
Accuracy
8 + 2 (C,( P.. - PIl VT)
N
8 - P + + (1 - (s)) V
+ +(1 - (1-P((s)) (C.(0) (ho - -rl) N
N
1 30V Sta, + 3 (C,, Pr. - Pll S) + (C. Inho r()
Bounding (8)) y
X
In addition, since the rate of the epistemic uncertainty is O VNT scaling factor can be chosen
appropriately such that Pt (s, a)n''E(ss, a) (s a) Rmaxx 2 (*aaa akin to that of the proof of Lemma 33, with which we are guaranteed the quasi-optimism to hold.
T'
Since
|| Pho (-18, P(. a) 22
(s, a) r(s, a)l s (s, a)l + Rmax
we denote
AT(0): max
(s),
(a.a)SxAA
An(0): max (s.a)E5xA
(0) (Iro, (s, Rmax)}
Following the same procedure for analyzing regret and sample complexity, we obtain prior- dependent bounds as follows:
S (1 (1-7)15 + (1 (T))
VSAT
(1- + An((0) SA 1-7
Regret
SA
S
1 log J
Sample Complexity
( 7) + (1 (r) + (R()))
<(1 71-
If the prior by is furthermore assumed to be uniform and bounded, both (T and (n will reduce to constants that do not depend on the state-action pairs, thus leading bound similar to that in the frequentist case.
L
Remark Since the epistemic uncertainty is additive across both reward and transition sources, The other source may decay faster.
suffices for either source to satisfy an order of (
In the following sections, we will instantiate specific priors.
I.2 DIRICHLET AND NORMAL PRIORS
Corollary 5 (Restatement of Corollary 1). Let by denote the joint distribution consisting of Dirich- let prior Dir(alsxi) on the transition probability vector and Normal prior N N + on the mean reward with known precision T for all (s, a) E S x A. Then by E e and is uniform and bounded, and hence achieves nearly minimax-optimality when used with EURRI.
54

---

Published as a conference paper at ICLR 2026
Proof. By Lemma 31, we know that (/,(s, a) = (#t) By Lemma 30, we know that (, a) and (s, a) = Ω2 (+) By Remark 2, this makes the final epistemic uncertainty E (s, a) In addition, Lemmas 28 and 29 imply that the prior is decomposable. All together, we have E C.
In addition, we can find Cg and C. required by the uniformality in Definition 15. And note that [rb as] Ioll V(s.)) a) E S A, therefore the boundedness in Definition 16 is satisfied as well.
1.3 DIRICHLET AND NORMAL- GAMMA PRIORS
Proposition 4 (Restatement of Proposition 1). For Normal-Gamme prior NG Ao, Oug Bu). there exists a parameterization and an MDP such that 3t E N for which guasi-optimism does not hold.
This follows from the fact that the epistemic uncertainty under a Normal-Gamme prior depends on the sample variance, which multiplies the number of visits n in the numerator (Definition 12). In deterministic nearly deterministic MDPs, the sample variance can be zero, yiclding a lower bound on the epistemic uncertainty:
En( =
n2
which is insufficient to guarantee quasi-optimism, especially when a prior bias presents. Even the frequentist bound may vanish.
J HELPER LEMMAS
Lemma 33. It holds that
T
b² (8, - (s, Rmarr
Rmmr
(s)
for any (s E S x A and E N.
Proof. For (*. a) 2 m, the inequality trivially holds. For (s, < m, note by choosing n²t = Emax T + Rmax /m,, we have:
Te
rk
(b a) (s, Rmax)
(² = (p) (3)
(s (ss a) Rmax)
N* a)
Ryna
1
rh
Emax (*,
Emax v Nk (x,
(*, a)
Rmax
1
Rmax
1
rt
rx
VITLE
Emix
(*
Emax
(N*(s,a))
(8,
Rmax
/m=
1
Emar
(*
(N
Rmux
(N
Emax
(s,
0,
which is desired.
The following Lemma is helpful in proving both the quasi-optimism and accuracy for discounted settings.
55

---

Published as a conference paper at ICLR 2026
Lemma 34. Let C 2 0 be a constant and (0, 1). Let V be function such that V : S - [0,C].
For any (5, E A. the variance of under P(.)s, (,)) a) is bounded as follows:
>Var(V) a) s (v))))) + (1 + x)C (ax))))mamm,())
Equivalently, the following inequality holds:
~Var(V) a) - (
(1 (1+))
Proof. Adding and subtracting (V(s))² to (s), we get
VVr(VVsss)=>PPVV(sss -
(s.V) (V(s)) (VV))))))((()))++(VV()))) (V(s)) (PV(
-x (V(+)) -
->,(V)(s..)- -VV)))
bb)
+ - = (L()))))_)000+)))(((((()-))))(-) - -V- +1 (1+ m)x((,,
I (s)))(ss,))- - (V(+)) -VV())
where (a) is due to the fact that 7 >2 and (b) by the boundedness of value functions.
Lemma 35. Let V denote the value function of the approximate MDP under its derived policy Th. Let v denote the value function of the true MDP under the same policy. Then the difference between V and v is bounded as follows:
Au (V* - - (8, (An(D))(s,)) + 2.9 (s.
Proof. The proof completed by applying the procedure of Lemma 13 in (Lee Oh, 2025), except using (s) + Ss 2 0 from Lemmas 2-3 for variance decomposition, together with an adjustment of some constants.
K PRIOR MISSPECIFICATION
Problem Setting
Given a two-armed bandit:
a1 : P(rla1) = Bern(ui)
(11)
a2 P(r(az) Bern(u2)
(12)
with μ4 > μ12
(13)
We use Beta distribution model the belief over the parameter of the underlying Bernoulli dis- tribution. We have independent prior b(w(a,) = Beta(a,, Bb) over each arm with parameters 0; 0, 0, (1,2). Since Beta distribution is the conjugate prior of the Bernuulli dis-
tribution, after observing the number of success S, and failures F,, we can get the posterior a closed-from, i.c.
b(wla;, F.) (at +S, B, + F.)
(14)
(ota(a,,8)) i E {1,2}.
(15)
Then the EUBRL reward will be:
p _BBBLL = (1- Po) P. + Pt E,, where
(16)
A: En(w]ot,Ss.F.) P(rla,,) [r] a; + S
(17)
(18)
(as + S.) (3, F.)
df
(19)
a + B
56

---

Published as a conference paper at ICLR 2026
The epistemic uncertainty can also be expressed in closed form:
E(a:)
Varo(w or S....
[p(rla,.)) [r]]
(20)
Varo(w a..5.. [w]
(21)
0484 ( 3 +)
(22)
If we assume that the parameters of the prior are equal, we can show that epistemic uncertainty is non-increasing. This result is formalized in the following lemma:
Lemma 36. Given Beta prior distribution Beta(a, 3) with a Bernoulli distribution, the variance of the posterior distribution decreases monotonically with the number of observations.
for the parameter of
Proof. Let denote the by as the Beta prior before observing any outcome from the Bernoulli dis- tribution. It has variance Var(bo) = 4(20+Ty- After observing one sample from the Bernoulli distribution, whether it is success failure, will have updated posterior dı with the variance:
Var(bi) 2(2a 1)²
(33)
By examining the difference between the two, we have Var(bo) Var(bi) = 4(2++1) > There- fore, the variance of the posterior is decreasing after observing one outcome. However, since this result will hold for the next posterior compared the current posterior well, conclude that the variance of the posterior is monotonically decreasing.
We will prove the following theorem:
Theorem 11 (Prior Misspecification). Le 1. There exists an MDP M, a prior by, an accuracy level > and a confidence level óu E (0, 1] such that, with probability greater than 80.
(s.) (s:)
(24)
will hold for an unbounded number of time steps.
Proof. Before any new observation, both EUBBRL &max. therefore breaking the tie leads to half probability choose either arm. Consider choosing the second arm, it will lead some reduction of the epistemic uncertainty because of the new observation.
We aim to force the agent repeatedly select this arm, thereby preventing from ever reaching the optimal one. To achieve this, we need to ensure that (to simplify notation, we will henceforth drop the dependency of the epistemic uncertainty on the action; E will refer to the epistemic uncertainty of the second arm whenever it is considered):
EUBRL
EUBRL
((1 Pv)e + Ptε) - -Emxx
(25)
((1 Pv)f + Pvε) - ((1 Pv) Pmaxmxx + Puxmmxx
(26)
= (1 Po) (m-Em + Po (E -maxx)
(27)
2
(28)
Note, the second term in the penultimate line is a quadratic function; therefore, we can obtain its minimum as follows:
min E
Emax (E²
Emarx Emaxx))
(29)
Emax
(30)
Therefore, as long we ensure that Eq. 27 with substitution of this lower bound is non-negative we can guarantee Eq. 28 to hold. That being said, we require the following condition to be satisfied:
Emax
(1 - Pu) Emax)
2 0,
(31)
4
57

---

Published as a conference paper at ICLR 2026
which is equivalent to:
Emax
+ &max-
(32)
4(1 Pv)
By Lemma 36, know that Py is decreasing. Therefore, it suffices ensure that:
Emax
+ Emax:
(33)
4(1 Po.1)
where Pt,1 denotes the probability of uncertainty after observing the first outcome from the second
Moreover, the right-hand side can be expressed as:
Emax
x(a) 4(1 PUç1)
&max
(34)
16 + 4(2x + 1)
(35)
Since (0, analysis.
bound s(a) within the interval (1: ). which will be useful in our later
We now aim to show that, under certain priors, the probability of the agent sticking the second arm is high. In other words, suffices to show that the probability of not pulling the second arm is small. To that end, let focus the event f < s(a).
To proceed, we consider the following decomposition of the reward estimate:
+ S.
(36)
2a + n n1
(37)
2a + 2a +
where n is the total number of occurrences of the outcome from the second arm, and S, is the total number successes among these occurrences.
Notably, we can factor out the empirical mean F, resulting in a new inequality:
s(a)
20
(38)
2a+n a(2s(a) +
(39)
n = g(a n)
(40)
Next, apply Hoeffding's inequality to the expression above:
P(F < g(a, n)) = P(12 F #2 g(a,
(41)
exp (- -(())))(()))))
(42)
This provides an upper bound on the probability of not pulling the second arm over n samples. By applying the union bound at each step, can bound the probability that the second arm is pulled at least once, and refer to this event as "Omission":
P(Omission) = ( (F g((a
(43)
P(f < g(a,n))
(44)
la P(f < g)a,
P(F < g(a, n)),
(45)
n=1
(=a+++1)
S²
where we split the into two parts based on the floor of a, which will analyze individually.
58

---

Published as a conference paper at ICLR 2026
Bounding S2 We denote k |el. Since > |a|, we know that is (0,1). Therefore, we can rewrite g(a, n) as:
g(a. k(2s 1) s, k E (0.
(46)
For every fixed n, we want to find both the lower and upper bound of g(a.n) Since we know E (To) 16) and g(a, n) linear in s, can solve for the range of g(a, n2) as An (T k 5
16 k).
In addition, since E [0, 1), we can solve for superset
5 that contains every set 16 16
An, Vn > laj. We then analyze the squared term (M2 - g(a, n)))². This is a quadratic function with axis of symmetry of j22- There are two possible cases for the relationship between /42 and A: either (42 S 16 or #22 > 16 For the first case, the minimum of the quadratic function will be zero, which cancels out the effect of n and results in the largest probability- an outcome want avoid. Therefore, we consider the second case, 122 > 5
5.
Tg. where the minimum of the quadratic function
occurs at y - -S We denote this minimum as C = (12 3² Then we can bound the second term in the probability of omission as follows:
82
Σ (=(+++1)
P(f < g(a,n))
(47)
exp(-2Cn)
(48)
n=([a++1)
(xpp(-2C(a) Σ exp(-2Cm)
(49)
==1
= [aaaaaaeeeppppp____
exp( -2C)
(50)
1- exp(-epppp -2C)
exp( (xp(-20((a] (0((([+()))))))
(51)
1 exx
1
(52)
2'
where r7 E (0, 1) is arbitrary confidence level.
We solve for the above and obtain [a] 2 zz log
711 exp z07) 01 Next, we will bound the
other term.
Bounding S The goal is to isolate the parameter and make it dominant. We expand the exponent as:
(2s 1)2
- on(p2-g(a,m)) m))² =2 n(ju2 1012-s) s)2 + 2(12 s)(1 25)) a
a²
(53)
n
5 and (1) ) therefore I2 > O. And the remaining two terms are also positive. Since 22 > 16
Based on this observation, we provide a lower bound for the exponent as follows:
9
2n(u2 - n)a, > 213
32
a
(54)
n
Next, we use this result to bound S₁:
9
S
<
exp
37
aa
2
(55)
71
[a]
9
exp
(56)
32
1=1
9
|a|
exp
a
(57)
32
(58)
2'
59

---

Published as a conference paper at ICLR 2026
which unfortunately has closed-fome solution. However, leverage the Lambart W function to obtain an analytical solution. Denote u We instead bound it as follows:
32 Lal. then Eq. 57 can be rewritten as 32
u exp (u).
g
32 - 2
9 uexp(u)
(59)
+ uexp(u) 2
64 4
(60)
which matches to the I Lambart W function. Since there are two branches Wo(r) and W W-1(2) of the
Lambart W function when x E 2 0), and (x) < Wo(x) We can get u I W-1(- 1)
therefore [a] 2 32 w-1(- 64 = 02.
Combining the two bounds together. long choose omission will be bounded as follows:
[a] max(a1, a2), the probability of
+ 7
P(Omission) S1 + S2 -
(61)
2
2
Therefore, if we denote the event of sticking to the second arm as St its probability will be:
P(sticky) P <F
(62)
P(u (F < P(omission)
(63)
(64)
(65)
Therefore, can conclude that with probability greater than ōn (1 .7). the second arm will be always pulled, leading to suboptimality. More formally, for any co < μ1 P2. we have:
(*t V*(s)) co.
(66)
where (st) U2 and (st) M4, which completes proof.
60


Reviews:
[{"review_id": "MXnp7itz9C", "reviewer": "Reviewer_12wQ", "summary": "The paper proposes a novel Bayesian reinforcement learning algorithm, EUBRL, to solve the explore-exploit dilemma, especially in environments with sparse rewards. The paper argues that common \"optimism-based\" exploration (adding an uncertainty bonus) is flawed because it can magnify errors when the agent's reward estimates are unreliable. EUBRL uses an \"epistemically guided reward.\" This is a weighted average that exploits (uses the estimated reward) when the agent is confident, but explores (uses uncertainty itself as an intrinsic reward) when the agent is uncertain. Theoretically, they show that EUBRL achieves nearly minimax-optimal regret and more importantly sample efficiency which hasn't been done in prior work. Empirically, they show that their method leads to imporved sampled efficiency on different tasks.", "questions": "My questions are based on the practicality of the algorithm for more realistic applications:\n\nExploration bonuses have been shown to work with Deep Reinforcement learning algorithms. Do the authors think that their method can be deployed with a neural-network based policy in a model-based setting. \n\n1. The paper claims \"superior scalability\" but only demonstrates it in tabular, low-state-space environments (DeepSea). Isn't this claim misleading, as the algorithm's tabular, model-based nature makes it computationally intractable for the large-scale, high-dimensional problems where scalability is actually needed?\n\n3. Since maintaining a full Bayesian posterior is impossible, which practical proxy for uncertainty would work with this method? For example, would you use the variance from a deep ensemble or a novelty score from a pseudo-count method?\n\n4. Could this \"guided reward\" concept be adapted to improve sample efficiency in a model-free deep RL algorithm (like DQN or SAC), or is it fundamentally tied to a model-based approach?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper tackles the fundamental exploration–exploitation dilemma in reinforcement learning by introducing a novel approach termed “epistemic guidance.” The method is well-motivated, and its effectiveness is supported through both rigorous theoretical analysis and comprehensive empirical evaluation.\n\n2. The paper argues that adding an exploration bonus to the reward estimate is a flawed way to do exploration in BAMDPs because the reward estimate can be highly uncertain and can result in a poorly specified reward. Instead they propose to weigh the two rewards (reward estimate and the exploration bonus) by the uncertainty associated with the state-action pair. If the agent is uncertain it uses the exploration bonus if the agent is certain it uses the reward estimate. The paper also proves that this method achieves nearly minimax-optimal regret in both regret and sample complexity.", "weaknesses": "1. The paper's analysis is confined to discrete state-action spaces, and it does not address the challenges of integrating its method with deep function approximation. The reliance on maintaining an explicit Bayesian posterior is computationally intractable for the high-dimensional environments where deep RL is typically applied. Therefore, it is unclear how the 'epistemically guided reward' could be effectively approximated to improve sample efficiency in practical deep RL algorithms. \n\n2. The paper suffers from a separation of theory from implementation. While the main text provides a compelling theoretical justification for the \"epistemically guided reward,\" it lacks a clear, procedural description of the full algorithmic loop. To understand precisely how the belief posterior is updated after each transition and how the new policy is extracted, the reader is required to hunt for the algorithm in the appendix.\n\n3. The adaptive weighting scheme is particularly vulnerable to the degeneracy of the uncertainty estimates. If uncertainty degenerates to zero, the agent will become fully exploitative.\n\n4. Similar to the last point, a mis-specified prior will also impact this algorithm a lot more than standard exploration bonus algorithms.", "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": "jdnM5FoiUs", "reviewer": "Reviewer_cKEm", "summary": "The authors propose the Epistemic Uncertainty directed Bayesian Reinforcement Learning (EUBRL) algorithm which achieves nearly minimax-optimal regret and sample complexity in infinite-horizon Markov Decision Processes (MDPs). EUBRL directs RL exploration by utilising probabilistic inference to model epistemic uncertainty as part of the agent’s objective (i.e., adaptively weighting the mean reward and uncertainty term based on the probability of uncertainty). Nearly minimax-optimal regret bounds and sample-complexity guarantees are established for the class of priors that are decomposable, or weakly-informative, and whose rate of epistemic uncertainty is $\\mathcal{O}(1\\sqrt{n})$. Empirically, EUBRL is shown to outperform frequentist (RMAX, MBIE-EB), sampling-based (PSRL, BOSS), optimism-based Bayesian (BEB, VBRB), and classical Bayesian (BEETLE, Mean-MDP) baselines across tasks with sparse rewards, long horizons and stochasticity (Chain, Loop, DeepSea, and the newly introduced LazyChain).", "questions": "Would it be possible to compare EUBRL to a variant that uses the exact same uncertainty estimates but applied as an additive bonus? I think such a result would help further empirically support the benefits of disentangling exploration and exploitation versus improved UQ.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is eloquently written and introduces a novel theoretical proof which, for the first time (to the best of my knowledge also), achieves nearly minimax-optimal sample complexity in infinite-horizon discounted MDPs without assuming a generative model. This result improves on He at al. 2021 which shows nearly minimax-optimal regret but doesn’t extend to sample complexity. The theoretical results are backed up by convincing empirical results (using multiple seeds, reporting standard errors etc) covering a wide range of appropriate baselines (including frequentist and Bayesian), three environments from the literature, and newly introduced fourth task which targets algorithm “myopia”. In all tasks EUBRL is shown to improve upon prior works.\n\nOverall I think the claims in the paper are both significant and well-supported both theoretically and empirically.", "weaknesses": "Towards the goal of disentangling exploration and exploitation, the evidence could be strengthened by e,g., considering an ablation (see questions).\n\nThe accessibility of the paper to a wider audience could also benefit from adding short intuitive summaries after key lemmas in the appendices.", "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": "6gjwR5sUkU", "reviewer": "Reviewer_Sc6X", "summary": "This paper proposes EUBRL, a Bayesian RL algorithm that steers exploration using epistemic uncertainty. At a high level, the per-step reward is interpolated using a learned \"probability of uncertainty,\" $P(U=1 \\mid s, a)$, which balances exploitation (the current mean reward estimate) against exploration (an intrinsic term derived from epistemic uncertainty). The authors prove nearly minimax-optimal regret and sample-complexity bounds for infinite-horizon discounted MDPs under a class of priors. Experiments on Chain, Loop ,DeepSea, and a new LazyChain benchmark compare EUBRL to several baselines and suggest strong exploratory behavior.", "questions": "1.Details in Algorithm 1: How do you compute $\\mathcal{E}(s, a)$ exactly in the tabular/prior choices you study? How is $P(U=1| s, a)=\\mathcal{E}\\_{b}/ \\mathcal{E}\\_{\\max}$ estimated on-policy, and how is $\\mathcal{E}_{\\text {max }}$ selected (global constant, rolling maximum, or theoretical bound)? Do you require assumptions on $f$ and $g$ ? How is Valuelteration(b) implemented under the updated belief?\n\n2.Theorem 3 suggests $\\eta$ is important. How do you choose $\\eta$ across tasks, and how sensitive are results to it? \n\n3.$\\widetilde{V}^t(s)$ is introduced to ensure quasi-optimism. Could you give its precise definition and a short intuition for how it drives the regret decomposition?\n\nSuggestions:\n1. If some definitions or derivations are omitted due to space, please add precise references to the appendix, so readers can quickly locate the formal statements and implementation details.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.To the best of my knowledge, this is the first work to convert epistemic uncertainty into an explicit guidance weight $P(U=1 \\mid s, a)$. This idea is novel, naturally decouples exploration from uncertain reward estimates, and provides an adaptive interpolation weight of the reward signal.\n\n2.Theoretical guarantees are strong.  The paper gives (i) a regret bound $\\tilde{O}(\\sqrt{S A T} /(1- \\gamma)^{1.5}+S^2 A /(1-\\gamma)^2$ ) that matches known lower bounds when $T$ is large enough, and (ii) a sample-complexity bound that matches lower bounds for small $\\varepsilon$.\n\n3.The paper formalizes a class \n$\\mathcal{C}$ of decomposable/weakly-informative priors and shows nearly-minimax bounds for uniform bounded priors.\n\n4.The experimental section covers both deterministic and stochastic settings with many random seeds, which helps demonstrate robustness.", "weaknesses": "1.The algorithmic description is quite high-level. More concrete details and examples would help reproducibility-for instance: how $\\mathcal{E}(s, a)$ is computed in practice; how the on-policy estimate $P(U=1| s, a)= \\mathcal{E}\\_{b}/ \\mathcal{E}\\_{\\max}$ is formed; and how $\\mathcal{E}_{\\max }$ is chosen.\n\n2.Some notation and concepts in the main text need clearer definitions. For example: what is the role of $w$ in Section 3.1? How is a \"prior\" specified precisely (i.e., prior over what objects/parameters)? It would also help to include concrete examples illustrating Definition 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": "3HipbEz1tj", "reviewer": "Reviewer_kthm", "summary": "The paper proposes a method for incorporating epistemic uncertainty into a standard Bayes-Adaptive-MDP-solving framework (interact, update belief-posterior, find the optimal policy with respect to the posterior, repeat). The paper includes a comprehensive theoretical analysis of the new method from the perspective of optimality.", "questions": "**Presentation:**\n1. Algorithm 1 is very simple and very compact, which is excellent. However:\n    1. I think it is important it is at least described in the main paper.\n    2. ValueIteration(b) is never defined, described, or cited, I believe.\n    3. BeliefUpdate(s,r) should also be described in more detail (at least, how the update is done from a practical perspective).\n    4. It seems to me that algorithm 1 is not one of the contributions of the paper, but rather a rather-standard approach for posterior-belief/over-models based methods. Is that correct? If yes, I would rephrase the contributions. Rather than introducing a new algorith, the authors introduce a new method to incorporate uncertainty into the belief / posterior. I do not view this as weakening the contribution of the paper - merely making it easier for the reader to understand the novelty of the paper.\n2. I don't think $\\Epsilon_b$ is ever defined?\n2. The \"related work section\" would work much better after preliminaries (Section 2) than where it currently is, in the end of the paper. It will also make introducing the baselines and understanding the approach much easier in my opinion.\n3. I would cite at least one uncertainty survey for the Uncertainty Quantification paragraph, such as [1].\n4. Section 3.1 should build on citations from the uncertaity quantification paragraphs in the related work (/preliminaries). Unless 3.1 is entirely novel (in which case - this should be emphasized stronger), the prior work it builds on should be cited.\n5. I think lazy chain is incompletely explained. What is the complete action space? Are transitions det. or stoch.? Is there a difference between the left end and the right end? What does solving the problem constitute (ie what is the optimal policy), if the comulative return is zero?\n6. I would also suggest adding more detailed descriptions of chain and deep sea.\n7. Some \\citep should be \\cite (line 464).\n\n**Experiments and baselines:**\n1. I believe PSRL can be tuned to work much better if the \"right\" choice of prior over transition models (/rewards) is made (ie - transitions from any states are to at most two different states, rewards are det / from a normal). Since experiments are already run with EUBRL+ and there's a prior selection discussion, I think these results belong there. What do the authors think?\n\nI'm open to increasing the score, especially since most changes I would like to see are textual. The most major comments from my perspective are the clarity that relates to Algorithm 1 and the missing theoretical motivation.\n\n[1] Hüllermeier, Eyke, and Willem Waegeman. \"Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods.\" Machine learning 110.3 (2021): 457-506.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "Strong theoretical foundation.\n\nStrong theoretical results.\n\nGood sanity-check experiments.\n\nClear description of theoretical limitations.", "weaknesses": "Missing theoretical motivation:\n  1. Why is CAI chosen to formulate the epistemic uncertainty?\n  2. Why is epistemic uncertainty chosen to be formulated in CAI in this way?\n\nMissing additional limitations - the method is most likely limited to tabular settings. Is that correct?\n\nPresentation: multiple comments, described in more detail below.", "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)