Multi-Reward Best Policy Identification
Authors: Alessio Russo
Filippo Vannella
Venue: NeurIPS 2024 poster (2024)
Keywords: multiple rewards
best policy identification
pure exploration
active exploration
reinforcement learning
sequential decision making
Primary area: reinforcement_learning

Abstract: Rewards are a critical aspect of formulating  Reinforcement Learning (RL) problems; often, one may be interested in testing multiple reward functions, or the problem may naturally involve multiple rewards. 
In this study, we investigate the _Multi-Reward Best Policy Identification_ (MR-BPI) problem, where the goal is to determine the best policy for all rewards in a given set $\mathcal{R}$ with minimal sample complexity and a prescribed confidence level. We derive a fundamental instance-specific lower bound on the sample complexity required by any Probably Correct (PC) algorithm in this setting. This bound guides the design of an optimal exploration policy attaining minimal sample complexity. However, this lower bound involves solving a hard non-convex optimization problem. We address this challenge by devising a convex approximation, enabling the design of sample-efficient algorithms.  We propose MR-NaS, a PC algorithm with competitive performance on hard-exploration tabular environments. Extending this approach to Deep RL (DRL), we also introduce DBMR-BPI, an efficient algorithm for model-free exploration in multi-reward settings.

Multi-Reward Best Policy Identification
Alessio Russo Ericsson AB Stockholm, Sweden
Filippo Vannella Eriesson Research Stockholm, Sweden
Abstract
Rewards are critical aspect of formulating Reinforcement Learning (RL) prob- lems; often, one may be interested in testing multiple reward functions, or the problem may naturally involve multiple rewards. In this study, investigate the Rewlad Best Policy Identification (MR-BPI) problem, where the goal is to determine the best policy for all rewards in given R. with minimal sample complexity and a prescribed confidence level. We derive a fundamental instance- specific lower bound the sample complexity required by any Probably Correct (PC) algorithm in this setting. This bound guides the design of an optimal explor- ation policy attaining minimal sample complexity. However, this lower bound involves solving a hard non-convex optimization problem. We address this chal- lenge by devising a convex approximation, enabling the design of sample-efficient algorithms. We propose MR-NaS, PC algorithm with competitive performance on hurd-explorationn tabular environments. Extending this approach to Deep RL (DRL), we also introduce DBMR-BPH an efficient algorithm for model- poode--free exploration in multi-reward settings.
Introduction
Reinforcement Learning (RL) provides powerful framework for sequential decision-making which has achieved number of breakthroughs in wide range of applications, including mastering video games [1, 21, accelerating algorithm design [3], optimizing fusion control systems [4, 5], and
enhancing autonomous robotic control [6, 7, 8].
Rewards are critical aspect of formulating an RL problem. Yet, designing reward function can require numerous iterations of reward engineering [9]. Furthermore, in many practical scenarios, the reward signal is not necessarily scalar, and the agent may seek optimize performance across set of reward functions [10, 11] (c.g., goal reaching applications in robotics [12], recommender systems [13], intent-based radio network optimization tasks [14, 15], etc.).
In this work, we investigate how to efficiently identify optimal policies across multiple rewards in a given set R, setting refer to Multi-Reward Best Policy Identification a variant of traditional Best Policy Identification (BPI) with fixed confidence [16, 17, 18, 19, 20], where the goal is to identify optimal policies using the least number of samples and with prescribed confidence level. Exploration algorithms for BPI typically aim to find the optimal policy for a single reward function, which is known and fixed in advance. However, previously mentioned, the agent may face uncertainty about which reward function is the most appropriate for a given task, or may seek to optimize performance across a set of rewards.
This setting
This problem remains relatively unexplored in the current RL literature. Closely related settings reward-free RL [21, 22, 23], unsupervised RL [24, 25, 26, 27, 28, 29], and multi-objective RL [30, 31]. In reward-free RL, the goal of the agent is to estimate the optimal policy for any possible
Code repository: https: //github/btttttt http://///seeeess///ttttt...t Reward- Best- cost-Policy-oo -ow.ooo-oddooiiiiccceeeeeeoee Identificatiinn
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

reward, using methods such as maximum entropy exploration [32, 33]. This reward-free phase is then followed by a downstream task adaptation in unsupervised RL. Lastly, in oojett-o RL, the agent optimizes over multiple (potentially conflicting) rewards, with the goal of identifying a Pareto frontier of optimal policies. While reward-free RI. is the closest to our setting, exploration for any possible reward is unlikely to occur in practical problems. On the other hand, unsupervised RI. and multi-objective RL do not directly address the multi-reward pure exploration problem - a setting we deem to be of practical use in wide range of applications. For instance, in intent-based radio network optimization, rewards are designed to reflect network operator intents, such as maximizing throughput or coverage in given network area. MR-BPI enables the agent to identify policies that perform well across different reward functions, enhancing robustness and adaptability to varying conditions and goals.
Our contributions are as follows. For MR-BPI with a finite set of user-specified rewards, we establish an asymptotic instance-specife sample complexity lower bound for Markov Decision Processes (MDPs) with a unique optimal policy, which generalizes the lower bound in the single-reward BPI setting [17]. This bound provides insights into the fundamental difficulty of the problem and guides the design of an optimal exploration policy, As in previous works [16, 17, 19, 34], determining such an exploration policy requires to solve non-convex optimization problem. To address this issue, we propose a convex formulation of the lower bound based on a finite set of rewards. We also propose extensions for two cases: (1) for random exogenous reward signals provided by the environment (app. B.4), and (2) for a set of continuous rewards, which can be addressed by considering a carefully chosen finite set of rewards (app. B.3).
We then devise MR-NaS (Multi-Rewaad Reward Navigate and Stop), a PC algorithm with asymptotic sample complexity guarantees, adaptable to the aforementioned extensions. We evaluate the performance of MR-NaS on different hard-exploration tabular environments, comparing to RF-UCRL [22] (a reward- free exploration method), ID3AL [33] (a maximum entropy exploration approach) and MR-PSRL, multi-reward adaptation of PSRL [35]. Results demonstrate the efficiency of MR-NaS in identifying optimal policies across various rewards and in generalizing to unseen rewards when the reward set is sufficiently diverse. Lastly, we further extend our multi-reward exploration approach to Deep RL (DRL) by devising DBMR-BPI (Deep Bootstrapped Multi- newli- BPI), model-frree exploration algorithm for continuous-state MDPs. We assess its performance, along with RND [26] (Random Network Distillation), Di Disagreement [27], and APT [29], on hard-exploration problems from the DeepMind BSuite [36] and on link adaptation (a radio network control problem [37]).
2 Problem setting
In this section, we introduce the notation used in the manuscript and briefly introduce the Best Policy Identification (BPI) framework. Lastly, we describe the MR-BPI setting.
2.1 Markoy Decision Processes and the Set of Rewards
Markoy Decision Processes (MDPs). We consider discounted MDPs of the type M = AS where S is the finite state space (of size S = [S)), A is the finite action space (of size A = AA). P:S x A > A(S) is the transition function, which maps state-action pairs to a distribution over states and 7 E (0, 1) is the discount factor. We indicate by by M, = AS, P.r, 7, the MDP when considering a reward r : S x A - [0, 1]. For a given reward r, we define the discounted value of a Markov policy
s), where 8141 ((-|s,, a:) and a, (-1ss). We also let (s) = max, (s) be the optimal value in and, for MDPs with unique optimal policy, we indicate it by (s) arg max, (T)(s). Similarly, we also define the action-value function Q7 (s, a) = r(s, a) + 11,.a [V, (s').. For an MDP Mr. we indicate by II* = {i e IId : V|V - V = 0} the set of optimal policies in M, and Ie is the set of deterministic policies.
S + ((A) to be ViT(s) = E" ''E2 ?r((s,,;))ss)
Set of rewards. We denote the set of rewards by R. and assume that it is known to the agent beforehand. In subsequent sections, for the sake of simplicity, we consider this set to be discrete and finite, while we present results for continuous sets of rewards in app. B.4. For finite MDPs, rewards are represented as vectors within [0, SA with each coordinate corresponding to the reward for the i-th state-action pair (thus the reward in each state-action pair is bounded in [0, 1).. We also denote

---

the canonical basis of rewards as Reanonical fei...., eSA) in R&A (with e, being the i-th vector
of the canonical basis).
2.2 Single-Reward Best Policy Identification with Fixed Confidence
Best Policy Identification consists of finding an optimal policy in an MDP using the least number of samples with given confidence level for specific reward function [16, 17], and the proof techniques are inspired by the Best Arm Identification literature in the bandit setting [20].
Optimal exploration strategy. The main idea is to derive an instance-specific lower bound on the expected number of samples needed identify an optimal policy, Interestingly, the lower bound is often formulated as an optimization problem, whose solution wn allows us to derive an optimal exploration algorithm. In other words, the solution w* provides the best proportion of static draws. That is, policy following wn matches the lower bound and is therefore optimal [20, 17].
Change of measure. The recipe to derive instance- instance-specific sample complexity lower bounds is based on a change of measure argument. In general, the reasoning adopted is to think in an adversarial way: Does there exist an MDP similar to the one considered for which the optimal policy is different?
The analysis of such a problem delves into the required minimum amount of evidence needed to discern between different hypotheses. The evidence is quantified by the log- log-likelhhood ratio of the observations under the true model and a confusing model. This confusing model is usually the one that is statistically closest to the true model while admitting a different optimal policy.
This argument allows us to derive an instance-dependent quantity T** also known as the characteristic time, that lower bounds the sample complexity of an algorithm. Change of measure arguments have a long history [38, 39, 40, 41], and have been applied to derive lower bounds for regret minimization [42, 43, 44]. best-arm identification [20, 45, 46, 47] and change detection problems [48, 49, 50].
2.3 Multi-Reward Best Policy Identification with Fixed Confidence
The MR-BPI setting follows closely the single-reward BPI framework [17]. In MR-BPI, the goal is to learn the best policy for all possible rewards E R as quickly as possible. This objective can be formalized in the 6-Probably-Cone MDP until she can output an optimal policy with confidence 1- 8. Contrarily to the classical BPI framework, that solely considers single reward, here we are interested in algorithms that identify best policy for all rewards in R.
(6-PC) framework [51, 22], where the learner interacts with the
Algorithm. Formally, an algorithm consists of (i) an exploration strategy (a.k.a. sampling rulc), (ii) a stopping rule T and (iii) an estimated optimal policy 6y.r, for any reward R. At each time step t, the algorithm observes a state st, it selects an action a, and then observes the next state 8141 P(-|s,, a.). We denote by IP (resp. E) the probability law (resp. expectation) of the process (Zi),. where Z, = (st, at). We indicate by F, = of (f Ze }) the o-algebra generated by the random observations made under the algorithm up to time in the exploration phase. For such algorithm, we define r to be a stopping rule w.r.t. the filtration (Ft).21 This stopping rule simply states when to stop the exploration phase. At the stopping time r the algorithm outputs an estimate न.,, of the best policy for any given reward r E R using the collected data. We focus on 8-PC algorithms, according to the following definition, and we impose a few mild assumptions.
Definition 2.1 (6-PC Algorithm). We say that an algorithm is 8-PC if, for any MDP M, it outputs (in finite time) an optimal policy for any reward r E R with probability at-least 6, i.c., PPr oo, (Vr E R, म,, E III (M,))] 2 1 8.
Assumption 2.1. (l) M E M. where M is the set of communicating MDPs [52] with a unique R; (II) M is aperiodic under a policy that assigns positive probability to all actions in every state; (III) for all r E R there exists a model P such that (( a) < P'(( a) = 0, where M' AS, Pl, 7) and for any two measures
optimal policy for every
for all (s, a), and IT* IT* (M,) (n, X), & À denotes absolute continuity of j w.r.t. X.
Assumptions (I)-(I)) are standard in the BPI literature [51, 53). Assumption (III) is made to avoid degenerate cases in which there are no confusing model for rewards r E R. For example, this occurs when the reward is identical in all state-action pairs (therefore all actions are optimal).
3

---

3 Best Policy Identification with a Set of Rewards
In this section, we investigate the MR-BPI problem, i.e., how to optimally explore MDP derive the best policy for any reward in R. In the first subsection, we derive a sample complexity lower bound for any 5-PC algorithm. Later, in the second subsection, present MR-NaS, 6-PC algorithm inspired by NaS [17] with asymptotic optimality guarantees.
3.1 Sample Complexity Lower Bound
In the next thcorem, state an instance-specific lower bound the sample complexity of any 8-PC algorithm. This bound provides a fundamental limit on the performance of any 5-PC algorithm and guides the design of optimal exploration methods for MR-BPI.
To state the bound, we indicate by w E RSA the allocation (or exploration policy), and by w(s a) the corresponding frequency of visit of a state-action pair (s; we introduce the set of confusing models (M) for M, as the set of MDPs that are statistically similar to the original model M,,
but admit different set of optimal policies under r. Specifically, we let Alt, (M) = (M' M &
M', (M,) (M,)) = 0}. where M < M' if for all (s, a) we have P(-|s, a) < P a))
E Theorem 3.1. Let E (0,1/2). For any 8-PC algorithm we have lim inf log( (1/8) 2 T (M), where
(M) = sup inf inf WER(M) FER (M)
Σ 8,0
[u(saa)LLMMr(s.d)
(1)
with KL (s (I((P())s,)) a))) and (MM) {w E A A): w(s,)) Ex at P(s|s', a' w') (o)ss','),, Vs S).
The proof of the theorem is presented in app. B.I. The result, obtained by classical change-of-measure arguments [20], extends the corresponding lower bound in the case of a single reward| [17].
Discussion.
The quantity (M) is referred to the characteristic rate and is non-convex optimization problem. It can be interpreted as a zero-sum game between an agent choosing a distribution (or allocation) w, and opponent choosing confusing model M' [45] (in the multi-reward setting, the opponent needs also to consider the set of reward when choosing the confusing model, which makes the problem harder to solve). The distribution is stationary distribution over states and actions that takes into account the transition dynamics, and, interestingly, the optimal solution Wopt the optimization problem in eq. (1) also defines the optimal exploration strategy (as Texp (als) Wope (8, a) Σb Wopt b)).
In principle, with access to optimization oracle that solves (1), could apply classical Track-and- Stop (TaS) [20] algorithms and achieve asymptotically optimal sample complexity by tracking the optimal allocation. Unfortunately, even in classical BPI, computing the characteristic rate (M) is in general a non-convex problem [16]. Instead, as in previous works [16, 17, 533. we focus on deriving convex upper bound U* (M) of T* (M), which call relaxed characteristic rafe, that guarantees that we are still identifying the optimal policy at the cost of an increased sample complexity. We focus on the case of finite set of user-specified rewards. The extension externally provided reward signals and the consideration of continuous set of rewards are detailed in the appendix (app. B.3 and app. B.4, respectively).
3.2 Relaxed Characteristic Rate
To define the relaxed characteristic rate, we state a few definitions of problem-dependent quantities for MDPs. We let A (s,a) a) == V,7
(s(s, a) be the sub-optimality gap in (s, a). Var, a) = EerePt-ls aa (sV, - Bg-P()) [+ (8)] be the variance of the optimal value function in the next state, and MD, as) = V Etr-P())aaa) [V, (V'))s (s')]llo be the maximum deviation starting from (s, Additionally, for a given reward r E we also let A, == min Ar a). Var, == max aeal.M).. Var, (s, a) and MD, = max,,assAs:MM, (s,(s, a) be the minimum gap, maximum variance and deviation across sub-optimal state-action pairs, respectively.

---

We define the relaxed rate in terms of an upper bound on [ww; that holds for all possible allocations w A(S A), where
T(w; My inf rER M'EAR(M,)
inf
Ew(s, (I
(2)
Theorem 3.2. For any allocation w E ASS x A) we have that (ww; M) S (w; where
27 (s, a)²
H + max Azw(s', (T))))) A
U(w; M) == max max ER (.)
(3)
(, a) (s,
where H, min 11--7
We define the optimal value (M) Uww"; ;M), where w" arg (w; M) ) the optimal allocation w.r.. U (*M... WER(M)
139(1+7)²
(1-713 max
Ver. e7 /7 M }. (1 (1-7)4/5
(1-7)²
Discussion. In the above theorem (the proof can be in found in app. B.2), the various instance- specific quantities Var, a), (r(s, a), H, and A, are computed with respect to M. The result extends the corresponding upper bound in [3].
We make some observations to clarify the key aspects of this result, First, (ws; M) is convex in w for finite set of rewards. Hence U (ww M) can be computed efficiently by using convex optimization methods (we report the runtime of our simulation in app. E.I).
For continuous set of rewards there are some challenges to guarantee convexity, due to the fact that the minimum gap can be non-convex and discontinuous. However, we find that, in practice, is sufficient to optimize over set of rewards whose convex hull includes the original set of rewards (e.g., by using the canonical basis of rewards; refer also to app. B.4 for more details).
Second, using the allocation w guarantees that we identify the optimal policy, at the cost of an increased over-exploration [53], since U (M) 2 (M). The cost of this over-exploration is limited,
min,eR A7 note that since by plugging w(s, a) 1/(SA) one can see that (*M O [I-
$4
the dependency in (1 -1 can be improved whenever the maximum deviation is smaller than (1-7)-1, Lastly, observe that the dependency Afw(s', (s')) the second term in eq. (3) can be improved to (s, ww(s', (s')) in [53].
3.3 MR-NaS Algorithm
In this section devise MR-NaS, an adaptation of MDP-NaS [17] MR-BPI for finite of rewards. The algorithm consists of (1) exploration policy (a.k.a. sampling rule) and (2) stopping rule. We detail these components in the remainder of this section (and in app. C) and present the pseudo-code of MR-NaS in Alg. 1.
Sampling rule. The main idea, in [16, 17, 53, 20], that the exploratory policy should follow the allocation w* = arg infwen((M) U(w; M), as this will yield sample-efficient exploration policy, However, the model . unknown, we cannot directly compute w*. Alternatively, we employ the certainty-equiivlence principle, and use the current estimate of the model M, in place of the true model M to compute the allocation w/ = arg inf inf (w; M,), where
2 MD.
He.
(w; Md) max max
+
(4)
rER s,aEOF,, (x) A., (8, (5 (),
A min a' (s). w(s'aa))
In the above expression, for any 1, the estimate Mr is completely defined by the empirical transition function Pú:
a) as) Nf > 0, and Pa(s'|s, a) - otherwise, Nz(s,a)
(5)
where (s, a) the number of visits for each state-action pair up to time t (sim. Ni a, s'))) Let- ting V denote the optimal value in Mr, = (M,rr) (sim. Qī,,) then (s,((s) {a Q (s, V (8)) is the set of optimal actions for reward r in state (and (s) is the complement), MD, MD,,(s,aa) IIV (s) Eer (V,, (s')]ll is the maximum deviation starting from (s, a)
5

---

Algorithm/ 1 MR-NaS (Multiple Rewards Navigate and Stop)
Require:
Confidence 8; exploration terms (a, B); reward vectors R.
I: Initialize counter t 1, (s, a) & 0 for all (s, a) E
2: Set exploration term <, = 1/N)(s:) ) and observe 81.
3: while (N;/; M,) < ((N,, do
Compute w/ we((M)) U [w:; M.) and let wi = (1/6) E En=1 Wh.
5: Set Te (alst) = (1 ex) (a]s;) + (als)) where ni (a|s) @t (s, /n/ (7(,,'))
6: Play at te(()1e) and observe 8.41 ~ P(-(st,ac):
7: Update (81, at), Mr and set
8:
end while
Output: an optimal policy f for given reward
for Mr,, Var,, (s, a) P. (VV()) (s') (a (8)) is the corresponding next- state variance of the optimal value for Mer- and (s, (s) Qi, (s, a). These quantities can also be used similarly to compute Har (i.e., H, computed w.r.t. Mr,)).
At the same time, the sampling strategy must ensure that the estimated model M, converges M. To that aim, we mix the computed allocation with a forcing policy xy. ensuring that each state-action pair is sampled infinitely often. We use the forcing policy xf,,(-(s) = sof (- Ne ex /E,
EEet e² for vector This choice encourages select under-sampled actions for 3 > O, while for B = 0 we obtain a uniform forcing policy (als( = 1/A. [16], the authors use an exploration factor &t = 11(m+))) where m is an problem- specific constant measuring to the "connectedness" of the MDP. As estimating this constant is typically hard for most MDPs, we instead use e, = 1/ max(1, (x)))) with (s) = >. (s a) and a E (0, 1]. which only depends on the number of states visits. This change requires modification of the proofs in [17], since now 6, depends also the number of visits of s, Finally, to ensure convergence of wt + w*, we simply require that a + 3 S 1.
with 3e(s) max, (s.)) ming [x,b) 3 [0. 1] and (softmax(z)
9 (a))
Stopping rule. The stopping rule (line 3) is defined through the relaxed generalized likelihood ratio term tU (N, M,) and a threshold function ((N,, The term Nt/t simply refers to the rates of visit of each state-actin itte-action pair, while M, is the current estimate of the MDP (based on (5)). The threshold function is selected to guarantee that the algorithm is 5-PC (the proof is in app. C.4).
Proposition 3.1. Define the threshold ((N, 5) = log(1/0) + (S - 1) E) log (c[1+ M1) 2 ((N,, 5)} is 8-PC, iee. P(7 < 0o, (Jr R म., & II" (M.)) 86.
8-1 "sle))
Then, the stopping rule t == in 2 1: E0 (U (N./t;
(6)
Putting everything together. Following our discussion, MR-NaS uses the estimate M, to compute the allocation w/ arg infiwe(e(M))) U (w; Me) (line 4). To stabilize the exploration, use an averaged allocation to obtain कテ = (1/t) Σ w (similarly to the C-navigation rule in [20, 17]). Lastly, we mix oद with forcing policy Ty (line 5). The samples observed from the MDP are then used to update the number state action visits and the estimate of M,. Finally, the stopping rule (line 3) determines when the algorithms has reached the desired confidence level.
Sample complexity guarantees. Lastly, we establish asymptotic optimality guarantees on the sample complexity of MR-NaS (see proofs in app. C.2.3 and app. C.3.5, respectively).
Theorem 3.3. MR- with the stopping rule in prop. 3.1 satisfies: (i) it stops almost surely and E(r]
[im sup log(1/8 S UM) = 1: (ii) E[r] < 3o and lim sup tog(1/8) S U (M).
3.4 Numerical Results on Tabular MDPs
In this section we show results on different hard-exploration tabular environments: Riverswim
[54], Forked Riverswim [53], DoubleChain [22] and NArms [54] (an adaptation of SixArms to
N arms). We compare MR-NaS against RF-UCRL [22] (a reward-free exploration method), ID3AL
[33] (a maximum entropy exploration approach) and MR-PSRL, a multi-reward adaptation of PSRL
[35] (posterior sampling for RL) that is outlined in app. D.1.2. A full description of the environments

---

MR- No8
RF-UCRI
IDIAL
MR-PSRI.
Riverswim
FoveedRivrrswin
DoubleChsin
NArms
100%
Estimationn erior Eje:]
80%
60%
40%
20%
0
20000
40000
20000
40000
0
20000
40000
0
20000
40000
Stepe
Steps
Steps
Steps
Figure 1: Average estimation error over 1 1,..., T steps (note that is random variable). Shaded area indicates 95% confidence intervals over 100 seeds.
can be found in app. D.I. As the baselines are not specific to our setting, we consider different sets of experiments. In this section, show results for MR-NaS the more challenging setting with continuous sets of rewards, while in app. D.I, we also investigate the problem of identifying best policies with finite set of rewards.
More precisely, we consider the problem of correctly estimating the optimal policies convex set of rewards [0. 1 1|SA as well as the optimal policies of the canonical basis, with discount factor = 0.9. We consider R Reanonical Rynd where Rnd = { {R...... R30 consists of 30 reward vectors uniformly sampled from [0, 1] IIS., different for each seed. For MR-NaS, we use the insight from the analysis of a continuous set of rewards (see app. B.4.2) which shows that exploring according to the canonical basis Reanonical is sufficient to identify the optimal policies in a continuous set.
We run each algorithm for T 50 10 steps, and we report the fraction of misidentified policies et.r at time step and for reward r. Fig. shows the results for this setting over 50 seeds. We see how depending on the environment, certain algorithms may be more efficient. Nonetheless, MR-NaS is able to reach low estimation error relatively quickly on all of the environments. We refer the reader to app. D.I for further details.
Exploration in Deep Reinforcement Learning with a Set of Rewards
Extending MR-NaS to Deep-RL. is not straightforward. Firstly MR-NaS is model-based method, secondly there is no closed-form solution arg inf U (w;; M). To circumvent these issues, we adapt the OBMF-BPI algorithm from [53], where the authors propose DBMF-BP -PI, a deep-RL. RL exploration approach for single-reward BPI.
The DBMF-BI -BI algorithm. DEMF- BPI [53] is an algorithm for model- model-free exploration. In [53] they suggest that a model-free solution can achieved by (i) using the generative solution arg inf A(S U (w; M), which can be computed in closed form (see app. B.2.4), and (ii) by estimating the parametric uncertainty of the MDP-specific quantities (sub-optimality gaps, etc.). In other words, the generative solution may be close enough to the model-based one. Nonetheless, this solution may be biased because the true sub-optimality gaps are unknown, and therefore we need account for the parametric uncertainty in the estimates.
DBMF BIMF-BPT BPI estimates the parametric uncertainty using an ensemble of Q-networks. This ensemble of size B, when trained different data, can be used mimic the bootstrap procedure [55]: the samples (r))be(B) from this ensemble are used to build an empirical CDF P(X < x) around some quantity of interest X (in our case the quantity of interest is the Q-function). A randomized prior value mechanism [56] addresses the restricted support of 1S by adjusting the sampling of (#+)s. This empirical CDF then used to sample the Q-values at each time step, which then used compute the generative solution w..
D 1(x

---

Algorithm 2 DBMR-BPI(Dec) Bootstrapped Multiple-Rewards BPI) Exploration phase
1: Initialize replay buffer D, ensemble network parameter 0.
2: for t= 0, 2, .......... do
3: Choose reward with probability x 27,-
and compute allocation wi using DBMF-BPI with reward
4: Sample 04 (8t, -) and observe 8++1 P(-|st, 0t).
5: Add transition (St, Ge, "1.t,.... ".tt,,.,,"....> FR,1,, Sc+1) the buffer D, with rs = (8t, at), 1 1,.... [R].
6: Train the ensemble 9 according to DBMF-BPI and update estimates Ar,- for each reward r E R.
7:
end for
Multi-reward adaptation. We propose DBMR-BPI, an extension of DBMF-BPI to the multi-reward setting with finite set of rewards. DBMR-BPI at each time step observes a vector of rewards, and drives its exploration according to these observed values. More precisely, the extension mainly consists of the following modifications:
1. The Q-values are learned for all rewards. In the finite action setting, this implies that there are A|R] values to estimate in every state. Alternatively, one can choose to feed the networks with one-hot encoding of the chosen reward (or embeddings), but we experienced this change to be less effective.
2. We explore according to the difficulty of the reward function. Specifically, we explore reward r with probability x 1/4 as this term is typically the leading factor in the sample complexity. For the sake of stability, at the beginning of each episode (or every ~ 1/(1 ->) steps) we sample reward R to explore, and apply DBMF-BPP on this reward.
The main steps of the algorithm are outlined in Alg. 2, and all the details can be found in app. E.I.
4.1 Numerical Results
We evaluate the performance of DBMR-BP and compare it with state-of-the-an method in unsuper- vised RL [24] (note that this is the first algorithm for multi-reward exploration in Deep-RL). More
precisely, we compare our algorithm to RND [26] (Random Network Distillation), Disagreements [27] and APT [29]. The exploration procedure of these methods guided by an intrinsic reward function that is learnt during exploration (e.g., by quantifying the parametric uncertainty of the model, or some prediction uncertainty; these methods are detailed in app. E.2). As in [57, 533, we evaluate on different challenging environments from the DeepMind behavior suite [36]: the Cartpole swing-up problem and a stochastic version DeepSea [36, 53] with varying level of difficulties. We also evaluate the methods on the link adaptation problem, a radio network control task where the agent needs to choose a coding and modulation scheme in wireless networks [37], and report the results in app. D. Lastly, also evaluate the exploration quality of DBMR-BP both on known set of pre-defined rewards and on unseen rewards.
The Cartpole swing-up [36]. In the classical version of this environment, the goal is to balance pole initially pointing downward, and the agent incurs a cost -c whenever the cart moves. In the multi-reward variant of Cartpole, the goal is to stabilize the pole vertically around specific position Zo. The agent earns a positive reward only if the pole's angle, its angular velocity, and the cart's position, respectively, satisfy the conditions (1) cos(0) > k/20, (2) ( < fg. and (3) [z - < 1 - k/20, where &n is fixed constant and & is an integer representing the difficulty. To assess DBMR-EPP BPI's unseen rewards, we uniformly sample 5 additional values of in the same
We considered 5 values of zo linearly spaced in [11,5, 1.5), so that [R] capacity to generalize interval that are not used during training, and we denote them by Rind-
In tab. 1 we present results for two levels of difficulty & E {3.5} and different training steps T. The table presents statistics for the random variable X; = reward in the set. This metric measures the average amount of information collected by the agent useful to learn how to stabilize the pole upright. Avg (fX,)) (sim. the others metrics) indicates the arithmetic mean of {X,}, 1 over the rewards. We average results across 30 seeds.
+ = "TT Ir.(s,,a,))0 where is the i-th
In general, we see that DBMR-BP outperforms all of the unsupervised learning baselines. Interestingly, even though DBMR-BP1 IPI uses the base set of rewards to explore, we see better performance when collecting rewards from Rnnd (which not used by DBMR-BII BPI during exploration). The reason
8

---

rewards R2
Random rewards Ron
(
Essiee
Eluing ((X))
Av ((X)))
ElsidR... ((X)).
Ejiin,,. ((X)))
DBMR-BPI
21,3:20.6
6.1(8.5.66
12.8/120.8
23.1(22 24.2)
.1366.46)
17.1(16.0.
T 150000
RXD
1. 1.6)
0.3
0.900.711 1.2)
1411111777
04001002
1.1,99 1.4)
APT
0.310.3. 0.45
0.1 0:2)
0.200.1.021
0.360.3.00 0.4)
0.100.10.1)
0.2/0.2 0.2)
Disngr eenentt
0.9)0.7, 1.2)
0.3(0.2,0.6) (.6)
0.6.0.4,0 0.6)
1.0(0.7, 1.6
0.3(0.1,0.55
0.6,0.5, 0.7)
8-
DRM
20.2:19.6 20.6)
6.4[6.0,6
11.4(1077, 12.0)
22.3/21.5, 28.1)
4.5.4.0.4.))
15.5/14.4, 16.7)
200000
R3D
1.2/0.9. 1.5)
0.2(0.2.0.3
1.1)
11100. 1.4)
0.200.10.2)
0.900.7. 1.11
0.340.3.0.4)
0.100.1..3)
0.2
0.3,0.3,0
0.100.1.0.1
0.2
Dixagreecenn
0.7(0.5, 1.0)
(.4)
0.4/0.300.6)
0.8(0.5, .0)
0.203.10.3)
0.5/0.4,0.7 0.7)
Table 1: Cartpole swing-up. Statistics for the random variable X; = 7 Σ E R r; E Rma).. Values are multiplied by 100 and rounded to the first digit. In bold statistically significant results (in parentheses we indicate the 95% confidence interval over 30 seeds).
(with
may be that some rewards in R, (e.g., those with |z0| = 1.5), are harder learn, while is unlikely for the random rewards to have such values of Ti. This result seems to suggest that data collected by DBMR-BPI could also be used to optimize similar, but unseen, rewards. We refer the reader to app. 1 for more results and details on the environment.
The DeepSea [36]. In the DeepSea environment the agent moves in a riverswim-like environment, and the actions are randomized for each different seed. The agent starts the top-left corner of a grid of size N x N, and can only move diagonally, towards the bottom of the grid. In the classical setup, the agent observes a Ni=-dimensional one-hot encoding of its position, and the goal is to reach the bottom-right corner. We adapt it to a multi-reward setting by considering N different rewards R = (ri,..... TN) }, so that rú assigns a positive reward whenever the agent reaches column the last row of the grid. As in [53], we include small probability of the agent taking the wrong action.
To assess the capacity of DBMR-BPI BPI to collect unseen rewards, for each seed; we sampled 20 reward functions Rrad (r())20 1. each of dimension ((N + 1)/2 (where the i-th value corresponds to a possible position in the grid), from a Dirichlet distribution with parameter a (a:):, with a; = 1/(0N)) for all i = 1.... .(N + 1)/2, and computed the reward for these additional reward functions. The reader can find more details regarding the environment in app. D.2.2.
Base rewards
Random rewards Rnnd
(TGMM(((.))
((x))
BIS 1x,=o]
B'Aves ((X.))
Bjstda.... ((x.))
N 20 DBMR-BPI
4.6(4.6,4.6)
L8(L7, 1.8)
0.0 0.0)
5.92)
3.6(3.2, 4.0)
T 50000
RND
1.6/42.11.)
1.7(1.6,18)
0.0(0.0.0.3 0.1)
9.7
3.5(3.1, 40)
APT
1.4(0.8.
5.3(4.8, 5.8)
0.9[0.6, 1.3)
8.7 9.2)
6.6(5.9.7.4)
Disagrecment
0.0(0.0.0.0)
6.2(5.9.6.5)
4.0(3.4.4.5)
8.9 9.5)
6.4(5.8,
30
BPI
3.1(2.9.3.)
0.7(0.7.0.7)
0.0(0.0.0.))
6.0(5.8, 6.3)
3.0(2.5.366)
T 100000
RED
1.8 2.2)
1.9(1.9220)
0.3(0.2.0.5)
6.1
3.0(2.4,3.5 3.5)
APT
0.0(0.0, 0.0)
3.9(3.6. 4.2)
3.3.28.388)
5.9(5.6.6.2
4.3/3.8, 4.7)
Deeagreenent
0.0(0.0.0.0
7.0(6.6,7.3)
11.5 12.2)
6.2
6.1(6.6.6.6)
Table 2: DeepSea. Statistics for the random variable X, x (s at) (with ri or E Rrad). Values are multiplied by 100 (except the third metric for the base rewards) and rounded the first digit. In bold statistically significant results (in parentheses we indicate the 95% confidence interval over 30 seeds).
In tab. 2 we show some statistics for the random variable X, + (st, at), that quantifies the average reward collected for the i-th reward in specific instance. In the table GMR ({x+) indicates the geometric mean over the rewards (the arithmetic mean would be a constant for these base rewards in this setting, and the GM is more appropriate [58]), and ΣV 1x,=0 indicates the number of cells in the last row of the grid that have not yet been visited at time step T'.
When considering the set of rewards R used by DBMR-BPI, we see that APT and Disagremeent do not match the performance of DBMR-BP1 BPI and RND, focusing most of the time on few rewards. On the other hand, while DBMR-BPI and RND show similar performance for N = 20, the difference increases for N = 30 on the base set of rewards. When considering the total reward collected from the set Rynd, we see that DBMR-BP -PII achieves performance similar to RND, which confirms the capability of DBMR- BPI to collect reward from unseen reward functions (refer app. D.2.2 for further details).

---

5 Discussion and Conclusions
Exploration in RL and Best Policy Identification. There exists a variety of exploration methods in RL [59] and DRL (see [60, 53] and references therein). Our setting is generalization of classical single-reward BPI with fixed confidence [16, 17, 61, 62. 18, 19]. This line of work typically leverages instance-specific lower bounds on the sample complexity (or approximations of it) to devise efficient exploration strategies, but do not directly address the MR-BPI problem. While we primarily draw inspiration from [17, 53], we enhance their work by introducing multi-reward generalization applicable to both the tabular case and DRL, along with some technical improvements (see app. C and app. E.I). Lastly, while not directly related, in [63, 64, 65] the authors study the identification of the Pareto optimal frontier in multi-objective bandit model, a framework yet to be explored in MDPs.
Rewtii There are several works considering a setting where the agent deals with multiple diverse reward signals [10, 66, 11, 31]. Shelton [10] investigates the case where an agent observes vector of rewards from multiple sources at each time step. The author proposes an algorithm attaining Nash equilibrium on the average return of each source. In [66] they investigate a multi-reward setting with continuous states and devise an algorithm yielding optimal policies for any convex combination of reward functions. Arguably, the closest work to ours is Dann et al. [LI], where they investigate
tabular MDPs, aiming at optimizing a regret measure that combines the various rewards components through an operator and provide regret bounds for action elimination algorithms. Despite the similarities, these works focus on the classical regret minimization problem and do not address the pure exploration case.
A related framework is multi-objective RL [30, 67, 31], a technique with various applications in areas such molecular design [68] and pricing strategy optimization [69]. In this framework, the agent seeks to optimize multiple rewards simultancously. To the best of our knowledge there are no work investigating the exploration problem in Multi-Objective RL, setting that could potentially benefit from more efficient exploration strategies, such as the ones that we propose.
Reward-Free Exploration. A relevant body of literature considers Reward-Free Exploration (RFE) [21, 22, 70, 71, 23, 72], where the agent learns behaviours without a specific reward. For example, Jin et al. [21] study reward-free RI. in the tabular episodic case identify e-optimal policies for any possible reward. They provide a lower bound on the length of exploration phase scaling as S(H25² A/=²) and devise an algorithm nearly matching it of order 0(H1 A/²²). This bound was improved in [22] and [70], where the authors propose the RF-UCRL and RF-Express algorithms for episodic reward-free RL. On similar line, the authors of [23] focus on an RFE setting where the minimal sub-optimality gap is known quantity, and provide an algorithm with reduced sample complexity. Another relevant RFE framework is maximum entropy exploration [32, 33, 24, 73], which studies the problem of state entropy maximization. This type of exploration is particularly useful for offline RI. [74] since it is well know that the coverage of the state space characterizes the sample complexity of the problem [75, 76]. Lastly, the reward- freee exploration phase can be followed by a downstream task adaptation, as in unsupervised RL [24, 25, 26, 27, 28, 29]. While these settings are highly relevant and provide valuable insights for other RL domains (such as facilitating representation learning in self-supervised manner [77, 78, 791), some RFE techniques can be impractical realistic scenarios (e.g., exploring for any reward) or do not address the MR-BPI problem directly. Furthermore, unlike our setup, most of the works in RFE focus on the minimax setting only.
Conclusions. In this work, we investigated the MR-BPI problem, focusing on efficiently de- termining the best policies for diverse set of rewards R with a specified confidence level. We established a fundamental sample complexity result for MR-BPI and proposed two efficient methods for multi-reward exploration: MR-NaS for tabular MDPs and DBMR-BPI for DRL. Numerical results on challenging exploration environments suggests that both algorithms exhibit strong exploration capabilities and generalization properties. We believe that our study benefits various areas of RL by enabling more principled exploration in newri scenarios. This includes applications in multi-objective RL, which naturally lends itself to optimization over multiple objectives, and offline RL, where it is crucial to collect dataset that performs well across different rewards.
10

---

Acknowledgments
This research was conducted while the authors were employed at Ericsson in Stockholm, Sweden. We would like to express gratitude Burak Demirel, Pablo Soldati, Yu Wang and Peter Björkén for their support during the preparation of this work. We would also like to thank Maxime Bouton and Martin Isaksson for their critical feedback that enhanced the quality of this paper.
a personal note, Alessio Russo wishes to personally thank Letizia Orsini for her assistance in reviewing the manuscript. also dedicate this work to the memory of my beloved cat, Caterina, whose companionship and gentle spirit brought immeasurable joy to my life and was a comforting presence throughout my academic journey. Her memory will forever be source of comfort and inspiration.
References
[1] David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. Nature, 2017.
[2] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre,, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 2020.
[3] Daniel Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean- -aan-Bapistee Lespiau, Alex Ahern, et al. Faster sorting algorithms discovered using deep reinforcement learning. Nature, 2023.
[4] Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 2022.
[5] Jaemin Seo, SangKyeun Kim, Azarakhsh Jalalvand, Rory Conlin, Andrew Rothstein, Joseph Abbate, Keith Erickson. Josiah Wai, Ricardo Shousha, and Egemen Kolemen. Avoiding fusion plasma tearing instability with deep reinforcement learning. Nature, 2024.
[6] Ilge Akkaya, Marcin Andrychowicz. Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's cube with robot hand. arXiv preprint 1rX1v:1910.07113. 2019.
[7] Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza. Champion-level drone racing using deep reinforcement learning. Nature, 2023.
[8] Sarmad Ahmad Abbasi, Awais Ahmed, Seungmin Noh, Nader Latifi Gharamaleki, Seonhyoung Kim, AM Masum Bulbul Chowdhury, Jin-young Kim, Salvador Pané, Bradley J Nelson, and Hongsoo Choi. Autonomous 3d positional control of a magnetic microrobot using reinforcement learning. Nature Machine Intelligence, 2024.
[9] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[10] Christian Shelton. Balancing multiple sources of reward in reinforcement learning, Advances in Neural Information Processing Systems, 13, 2000.
[11] Christoph Dann, Yishay Mansour, and Mehryar Mohri. Reinforcement learning can be more efficient with multiple rewards. In International Conference on Machine Learning, 2023.
[12] Sha Luo. Hamidreza Kasaei, and Lambert Schomaker. Accelerating reinforcement learning for reaching using continuous curriculum learning. In 2020 International Joint Conference on Neural Networks (IJCNN). IEEE, 2020.
[13] Anisio Lacerda. Multi-objective ranked bandits for recommender systems. Neurocomputing, 246:12-24, 2017.

---

[14] Cleverson V Nahum, Victor Hugo Lopes, Ryan M Dreifuerst, Pedro Batista, Ilan Correa, Kleber V Cardoso, Aldebaro Klautau, and Robert W Heath. Intent-aware radio resource scheduling in ran slicing scenario using reinforcement learning. IEEE Transactions on Wireless Communications, 2023.
[15] Chamitha De Alwis, Pardeep Kumar, Quoc-Vies Pham, Kapal Dev, Anshuman Kalla, Madhusanka Liyanage, and Won-Joo Hwang. Towards 6g: Key technological directions. ICT Express, 94):525 2023.
[16] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In International Conference Machine Learning, pages 7459- 7468. PMLR, 2021.
[17] Aymen AI Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Advances in Neural Information Processing Systems, 34:25852-25864, 2021.
[18] Jérôme Taupin, Yassir Jedra, and Alexandre Proutiere. Best policy identification in discounted linear mdps. In Sixteenth European Workshop on Reinforcement Learning, 2023.
[19] Alessio Russo and Alexandre Proutiere. On the sample complexity of representation learning in multi-task bandits with global and local structure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9658-9667, 2023.
[20] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016
[21] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning. PMLR, 2020.
[22] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, 2021.
[23] Jingfeng Wu, Vladimir Braverman, and Lin Yang. Gap-dependent unsupervised exploration for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 4109-4131. PMLR, 2022.
[24] Michael Laskin, Denis Yarats, Hao Liu, Kimin Lee, Albert Zhan, Kevin Lu, Catherine Cang, Lerrel Pinto, and Pieter Abbeel. Urlb: Unsupervised reinforcement learning benchmark. In Deep RL Workshop NeurlPS 2021, 2021.
[25] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven explora- tion by sele-super prediction. In International conference on machine learning, pages 2778-2787. PMLR, 2017.
[26] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference Learning Representations, 2018.
[27] Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via dis- agreement. In International conference on machine learning, pages 5062-5071. PMLR, 2019.
[28] Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. In International Confer- ence on Machine Learning, pages 9443-9454. PMLR, 2021.
[29] Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 11188459-887777 2021.
[30] Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi-objectivve sequential decision-making. Journal of Artificial Intelligence Research, 48:67-113, 2013.
12

---

[31] Conor F Hayes, Roxana Rädulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfar- lane, Mathieu Reymond, Timothy Verstraeten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, et al. A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 2022.
[32] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681-26616 1-911. PMLR, 2019.
[33] Mirco Mutti and Marcello Restelli. An autrinscaall-mmoiiaatd motivated approach for learning highly exploring and fast mixing policies. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
[34] Jérôme Taupin, Yassir Jedra, and Alexandre Proutiere. Best policy identification in discounted linear mdps. In Sixteenth European Workshop on Reinforcement Learning, 2023.
[35] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems (NeurIPS), 26, 2013.
[36] 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 Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020.
[37] Erik Dahlman, Stefan Parkvall, and Johan Skold. 5G NR: The next generation wireless access technology. Academic Press, 2020.
[38] Abraham Wald. Sequential analysis. John Wiley, 1947.
[39] Gary Lorden. Procedures for reacting to change in distribution. The annals of mathematical statistics, pages 1897-1908, 1971.
[40] Tze Leung Lai. Asymptotic optimality of invariant sequential probability ratio tests. The Annals of Statistics, pages 318-333, 1981.
[41] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[42] Richard Combes and Alexandre Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. In International Conference on Machine Learning, pages 521-529. PMLR, 2014.
[43] Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Muthematics of Operations Research, 44(2):377-399, 2019.
[44] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured rein- forcement learning. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
[45] Rémy Degemne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits, 2020.
[46] Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019.
[47] Alessio Russo and Filippo Vannella. Fair best arm identification with fixed confidence. arXiv preprint 1703, 2024.
[48] Tze Leung Lai. Information bounds and quick detection of parameter changes in stochastic systems. IEEE Transactions on Information theory, 44(7):2917-2929, 1998.
[49] Alexander Tartakovsky, Igor Nikiforov, and Michele Basseville, Sequential analysis: Hypo- thesis testing and changepoint detection. CRC press, 2014.
13

---

[50] Alessio Russo and Alexandre Proutiere. Balancing detectability and performance of attacks on the control channel of markov decision processes. In 2022 American Control Conference (ACC), pages 2843-2850. IEFE, 2022.
[51] Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating the best policy in markov decision processes. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[52] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[53] Alessio Russo and Alexandre Proutiere. Model-free active exploration reinforcement learning. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[54] Alexander L Strehl and Michael L Littman. An empirical evaluation of interval estimation for markov decision processes. In 16th IEEE International Conference on Tools with Artificial Intelligence, pages 128-135. IEEE, 2004.
[55] Bradley Efron. Bootstrap methods: another look at the jackknife. In Breakthroughs in statistics: Methodology and distribution, pages 569-593. Springer, 1992.
[56] lan Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning, Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
[57] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in Neural Information Processing Systems (NeurIPS), 29, 2016.
[58] Kenric P Nelson. Assessing probabilistic inference by comparing the generalized mean of the model and source probabilities. Entropy, 19(6):286, 2017.
[59] Susan Amin, Maziar Gomrokchi, Harsh Satija, Herke van Hoof, and Doina Precup. A survey of exploration methods in reinforcement learning. arXiv e-prints, pages arXiv-2109, 2021.
[60] Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Pierre Perrault, Michal Valko, and Pierre Ménard. Model-free posterior sampling via learning rate randomization. Advances in Neural Information Processing Systems, 36, 2023.
[61] Andrea Tirinzoni, Aymen Al Marjami, and Emilic Kaufmann. Near instance-optimal pac reinforcement learning for deterministic mdps. Advances in Neural Information Processing Systems (NeurIPS), 35:8785-8798, 2022.
[62] Andrew J Wagenmaker, Max Simehowitz, and Kevin Jamieson. Beyond regret: Instance- dependent pac reinforcement learning. In Conference on Learning Theory, pages 358-418. PMLR, 2022.
[63] Peter Auer, Chao-Kai Chiang, Ronald Ortner, and Madalina Drugan. Pareto front identification from stochastic bandit feedback. In Artificial intelligence and statistics, pages 939-947. PMLR, 2016.
[64] Cyrille Kone, Emilie Kaufmann, and Laura Richert. Adaptive algorithms for relaxed pareto set identification. Advances Neural Information Processing Systems, 36:35190-3522 2023.
[65] Zixin Zhong, Wang Chi Cheung, and Vincent Tan. Achieving the pareto frontier regret minimization and best arm identification in multi-armed bandits. Transactions on Machine Learning Research, 2023.
[66] Daniel J Lizotte, Michael H Bowling, and Susan A Murphy. Efficient reinforcement learning with multiple reward functions for randomized controlled trial analysis. In ICML., 2010.
[67] Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi- objective reinforcement learning and policy adaptation. Advances in neural information processing systems, 32, 2019.
14

---

[68] Julien Horwood and Emmanuel Noutahi. Molecular design in synthetically accessible chemical space via deep reinforcement learning. ACS omega, 5(51):32984-3299) 2020.
[69] Elena Krasheninnikova, Javier García, Roberto Maestre, and Fernando Fernández. Rein- forcement learning for pricing strategy optimization in the insurance industry. Engineering applications of artificial intelligence. 80:8-19, 2019.
[70] Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning. PMLR, 2021.
[71] Ruosong Wang, Simon S. Du, Lin F. Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear funetion approximation. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, AarianFlorina Balcan, and Hswan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[72] Andrew Wagenmaker and Kevin Jamieson. Instance-dependent policy learning for linear MDPs via online experiment design. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[73] Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Pierre Perrault, Yunhao Tang, Michal Valko, and Pierre Menard. Fast rates for maximum entropy exploration. In International Conference on Machine Learning, 2023.
[74] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01663, 2020.
[75] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning. 7 11:99-129, 2008
[76] Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
[77] Diana Borsa, Andre Barreto, John Quan, Daniel J Mankowitz, Hado van Hasselt, Remi Munos, David Silver, and Tom Schaul. Universal successor features approximators. In International Conference on Learning Representations, 2018.
[78] Ahmed Touati and Yann Ollivier. Learning one representation to optimize all rewards. Ad- vances in Neural Information Processing Systems, 34:13-23, 2021.
[79] Ahmed Touati, Jérémy Rapin, and Yann Ollivier. Does zero-shot reinforcement learning exist? In The Eleventh International Conference on Learning Representations, 2022.
[80] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 33:10007-10017, 2020.
[81] Aurélien Garivier and Emilie Kaufmann. Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models. Sequential Analysis, 40(1):61-96, 2021.
[82] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi multi-armed bandit models. Journal of Machine Learning Research, 17(1):1- 42, 2016.
[83] Satinder Singh, Tommi Jaakkola, Michael L. Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforcemennt-eerriing algorithms. Machine learning, 2000.
[84] Gersende Fort, Eric Moulines, and Pierre Priouret. Convergence of adaptive and interacting markov chain monte carlo algorithms. 2011.
[85] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
15

---

[86] Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning markov decision processes with sap-dependent sample complexity. Advances in Neural Information Processing Systems, 10:1253-12633 2020.
[87] 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.
[88] Guido Van Rossum and Fred L Drake Jr. Python reference manual. Centrum voor Wiskunde en Informatica Amsterdam, 1995.
[89] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre -errard-aarchat,, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, 2020.
[90]
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Couraapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman. Nikolay Mayorov, Andrew J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng. Eric W. Moore. Jake VanderPlas, Denis Laxalde, Josef Perktold. Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SeiPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature Methods, 17:261 2722, 2020.
[91] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedier modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[92] Michael Waskom, Olga Botvinnik, Drew O'Kane, Paul Hobson. Saulius Lukauskas, David C Gemperline. Tom Augspurger, Yaroslav Halchenko, John B. Cole, Jordi Warmenhoven, Julian de Ruiter, Cameron Pye. Stephan Hoyer, Jake Vanderplas. Santi Villalba. Gero Kunter, Eric Quintero, Pete Bachant, Marcel Martin, Kyle Meyer, Alistair Miles, Yoav Ram, Tal Yarkoni, Mike Lee Williams, Constantine Evans, Clark Fitzgerald, Brian, Chris Fonnesbeck, Antony Lee, and Adel Qalieh. mwaskom/seabom: v0.8.1, September 2017.
[93] Wes McKinney et al. Data structures for statistical computing in python. In Proceedings of the 9th Python in Science Conference, volume 445, pages 51-56. Austin, TX, 2010.
[94] John D Hunter. Matplotlib: A 2d graphics environment. Computing in science & engineering, 2007.
[95] CLARABEL. CLARABEL Optimizer, 2024.
[96] Alexander Domahidi, Eric Chu, and Stephen Boyd. Ecos: An socp solver for embedded systems. In 2013 European control conference (ECC), pages 3071-3076. IEEE, 2013.
[97] Stefan Behnel, Robert Bradshaw, Craig Citro, Lisandro Dalcin, Dag Sverre Seljebotn, and Kurt Smith. Cython: The best of both worlds. Computing in Science & Engineering, 2011.
[98] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-peeffrmance deep learning library. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[99] Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(5)833-846 1983.
[100] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-leve level control through deep reinforcement learning. Nature, 51897540):599-53, 2015.
16

---

[101] Burak Demiral, Euhanna Ghadimi, Yu Wang, and Pablo Soldati. Pareto-optima solutions in rans: How multi-objective reinforcement learning can implement high-level intents? 2024. Manuscript in preparation.
[102] Ian Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20: 12, 2019.
17

---

Appendix
Contents
Introduction
2
Problem setting
2.1
Markov Decision Processes and the Set of Rewards
2.2
Single-Reward Best Policy Identification with Fixed Confidence
2.3
Multi-Reward Best Policy Identification with Fixed Confidence
3
Best Policy Identification with a Set of Rewards
3.1
Sample Complexity Lower Bound
3.2
Relaxed Characteristic Rate
3.3
MR-NaS Algorithm
3.4
Numerical Results on Tabular MDPs
Exploration in Deep Reinforcement Learning with a Set of Rewards
4.1
Numerical Results
Discussion and Conclusions
10
Limitations and Broader Impact
20
Sample Complexity Bounds
B.1
Lower Bound Proof
21
B.2
Relaxed Characteristic Rate Proof
22
B.2.1
Step 1: simplifying the set of confusing models
23
B.2.2 Step 2: relating the KI. divergence to the sub-optimality gaps
23
B.2.3
Technical lemmas
25
B.2.4
A Closed Form Solution for the Generative Case
26
B.3
Extension to Random Rewards
28
B.3.1 Lower bound with random rewards
29
B.3.2
Relaxed characteristic rate with random rewards
30
B.4
Extension to Continuous Set of Rewards
31
B.4.1
Non-convexity of the minimum sub-optimality gap ................................
32
B.4.2 A finite set of rewards can be sufficient
33
B.4.3 Technical lemmas
34
MR-NaS NaS Algorithm
37
C.1 Forcing policy
38
C.2 Almost Sure Sample Complexity Upper Bound of MR-NaS
38
18

---

C.2.1
Forced exploration property
39
C.2.2
Convergence of the state-action visitation frequency
39
C.2.3
Sample complexity upper bound
39
C,3
Expected Sample Complexity Upper Bound of MR-NaS
40
C.3.1
Geometric ergodicity of the sampling rule
41
C.3.2
Forced exploration with high probability
C.3.3
Concentration the empirical MDP
42
C.3.4
Concentration of the state-action visitation frequency
43
C.3.5
Expected sample complexity of MR-NaS
46
C.3.6
Alternative forced exploration with high probability
47
C,4
Stopping Rule
49
C.5
Technical Lemmas
49
Numerical Results
D.I Numerical Results for the tabular case
51
D.1.1
Environments Details
................................
51
D.1.2
Numerical Results
53
D.2
Numerical Results: Cartpole swing-up and DeepSea problems
55
D.2.1 Cartpole swing-up
56
D.2.2
DeepSea
62
D.3 Radio network control problems
66
D.3.1
Downlink link adaptation problem
66
Deep-RL Algorithms Details
71
E.1
DBMR-BPI algorithm
71
E.2 Other algorithms
72
NeurIPS Paper Checklist
74
19

---

A Limitations and Broader Impact
We discuss some limitations of the current work and highlight major directions of improvement.
Limitations.
Tabular MDP. The current theoretical analysis only applies to tabular MDPs, and may not necessarily extend to continuous domains in similar way.
Tracking of the allocation. In MR-NaS we employ a probabilistic policy, which may lead to worse tracking performance compared deterministic approaches (see e.g., the classical tracking procedures for best arm identification in multi-armed bandits [20]). These approaches are. however, harder to use in an MDP setting, since it becomes harder to guarantee correct tracking and convergence of the allocation wi to w".
Lazy updates. MR-NaS computes an allocation wi = arg infwen(as,) U(w;; Mc) at each time step, which could be computationally prohibitive for large-dimensional problems. A possible way to address this issue is to use "lazyness" [80], i.e., to compute wi only at time steps t T. where T C N prescribes the allocation update schedule (see [80]).
Scaling of the rewards for DBMR-BPI. The method that we introduce for exploration in deep-RL, DBMR-BPI, explores according to set of rewards. These rewards, if not correctly scaled, may impact the learning performance since the method relies on estimating the sub-optimality gaps.
Number of rewards for DBMR- BPI. The usage of DBMR-BPI could be limited by the number of rewards if it is too high, as the output size of the Q-network DBMF-BPI
A [R]. However, our experiments with ensemble size of 20 and A [R] Rs 90 did not encounter any issues. Furthermore, the training can be efficiently done as shown in the code, without looping over the rewards. Nevertheless, exploring the scalability to a larger number of rewards remains an interesting area for future research.
Finite action space for FBMR-BPI. In this paper, we analyze DBMR-BPI within a finite action space. Although continuous action spaces are equally important, extending the algorithm such spaces requires additional work. It is currently unclear how adapt the approach presented in [53] to continuous action spaces.
Assumption on the uniqueness of the optimal policy. In the paper we assume that there is unique optimal policy. This assumption is common in the BPI literature [18, 16, 17, 53, 20]. Addressing MDPs with multiple optimal policies or identifying s-optimal policies necessitates the use of more complex overlapping hypothesis tests [81]. This approach is already complex when applied to multi-armed bandits (i.e., MDPs with a single state), and extending it to full MDPs presents
greater challenge. In that sense, can provide some insights on the main problems and potential solutions:
In presence of multiple optimal policies, one may be interested in ensuring that the stopping time we have II' (Mr,-) C II (M,,) for all rewards E R. This guarantees that we identify subset of policies that are optimal. Unfortunately, ensuring this condition causes an asymmetry between the definition of the set of confusing models, and the event M E Alt(M. in proof of the stopping rule, that cannot be easily reconciled.
A positive result is that if the set of confusing models can be decomposed as union, or intersection, over the optimal policies M, then the decomposition proofs presented in apps. B.2 and B.4.3, can be easily extended to the case of multiple optimal policies by considering the sub-optimal actions a & O (s) in the decomposition, where (s(s) {a 1M. ()) Vi. (s)}.
Broader impact. This paper primarily focuses on foundational research in reinforcement learning. particularly the exploration problem. Although we do not directly address societal impacts, we recognize their importance. The methods proposed here improve the sample efficiency of RL algorithms and could be applied in various contexts with societal implications. For instance, RL is used decision-making systems healthcare, finance, and autonomous vehicles, where biases or enrors could have significant consequences. Therefore, while the immediate societal impact of our work may not be evident, we urge future researchers and practitioners to carefully consider the ethical implications and potential negative impacts in their specific applications.
20

---

B Sample Complexity Bounds
In this appendix we first prove thm. 3.1. the subsequent subsection we study how to obtain the relaxed characteristic rate presented in thm. 3.2. After that, we present extensions of these results to the case of random rewards (app. B.3) and continuous rewards (app. B.4). Finally, the last subsection, present some useful lemmas.
B.1 Lower Bound Proof
The proof leverage the classical change of measure argument [41, 20] and proceeds similarly to [16]. For simplicity, we consider the generative setting (i.e., we consider allocations w E A(S x A)), while the extension the forward model follows similarly to [17].
Proof of thm. 3.1. The proof begins by analysing the likelihood ratio of the observations, and compare against the worst confusing model. Then, by considering the 8-PC event and a data processing inequality yields the lower-bound.
Log-like liliikieihoodd ratio. Consider the MDP M = PP7) and alternative model M' (S, :) such that P < P'. The log- logliiellhood ratio between M and M' of sequence of observations (Zo; 21,...). where 2, = (8,,4;), is defined as
P(sn|an-1) log p' (sn|lzn-1)
L Σ
To simplify the analysis, let
N.(a.)) Σ log P(unls,a) P'((nlss,a)
P(su]o,a) P' (((smls,a)
I,500 Σ ((2))))()) log
where Yn denotes the next state after the pair (s, a) has been visited for the n-th time (s, a) and (s, a) is the number of times the state-action pair (s, a) has been visited by the algorithm up to time t. Then we can write L = En, a Li 5. Taking the expectation over the measure induced by M, we have
log P(snIzn-1) (" 12n11)
EM = EM
where Ea(l) the expectation under the probability measure induced by a model M (sim. M (-)) Then, at the stopping time have
EM [L]]
Σ EM [L
(+(s,))
P(unls,a) P'(ynls,a)
Σ E
log
s,a
20
[NN((.)))1) log ((uals
Σ E
Since X;aa = =log
P(ynlaaa)
is independent of Fn-1, and since (N, s n 11c =
P ( [s,a]
(N) 2 Fn we have that
2
EM = Σ Σ
PM (N((N(). 2 (s,
5,a
t=0
= -'
EM (N a) (LM (s,
8.a
where KT. KTMMar = KT.(P(s, P*(
21

---

5-PC argument. Consider 5-PC algorithm, and define the event & = (Ar E R, E [M,) and observe that Ex = ((3r E R. *r, IT (M,)).
Let Alt(M)) {M' M IT (M.) n (M,) 0). which can be rewritten Alt(M)
U,tRAlt,,M), where ( (M' E MILI n n (M,) 0}.
Before proceeding by applying the transportation lemma in [82], we first note that for any 8-PC algorithm we have Pa [89] < 6. Denote by II the set all Markovian policies. Then, under M' we have
PM = Pr tn. $ II (M.),,
2 max Mr 1 $ 11 (Mrr),
2 PM 1 & II (M,)),
= PAIITT E II II (M)),
2 Pa lt E III (M,,,,
2 min PMr ( E [M,),,
2 P PM [V., H7, E1I (M,),,
= 1 - P क.. & 11 (T7 2 1 1
Hence, in view of the data processing inequality in [82], for any M' Alt(M) we can lower bound the expected log-likelihood at the stopping time
EM [r,] = Σ BM [N, J as 2
2 kl 1 d)
d).
8,0
In view of the transportation lemma in [82], for any M' E Alt(M) we can lower bound the expected log-likelihood at the stopping time
MM [4]] = Σ EMI[N, a KLLMM (s) 2 kl(F M [E) ( 2 kl(1 - 6,,)-
8.a
As the inequality above holds for all M E Al)(M), and by optimizing over the set of confusing model, we have
inf Σ (a) = min inf (M) 8,0
Σ
FER M' (M)
2 kl(1 8,8).
Sample complexity. By letting w(s,a) EM (s, a)) //ar [7], and optimizing over all possible allocations w S2 we have
EM[T] max (EA(SXA) PER M'EAlt,
min
inf
Σ ws (ssss)))LMM)) (sL kl(1 8,8).
9,a
Finally, taking the limit as - yields the result.
The extension from the generative model to the forward model can be done as in [17, Proposition 2].
B.2 Relaxed Characteristic Rate Proof
Since the characteristic time (*M)) is non-convex optimization problem [16], we focus on deriving convex upper bound of (M) that is convex for finite of rewards (we discuss the continuous case in the next section). This property guarantees that we are still identifying the optimal policy at the cost of an increased over-exploration. In particular, we find convex upper bound of T(w; M) that holds for all possible allocations E A(S x A). Recall the definition of T(w; M)
((w:M)-1- = inf
inf FER M.E
w(ss, 4)LK aKL (r 8,0
To find the upper bound, we proceed in 2 steps: (1) we simplify the set of confusing models; (2) we relate the Kl.-divergences in T(w; .)) to the sub-optimality gaps of the MDP, and formulate the problem of computing the relaxed characteristic rate as convex problem.
22

---

B.2.1 Step 1: simplifying the set of confusing models
We use the following lemma from [16, Lemma 2] to decompose the set of confusing models.
Lemma B.1 (Decomposition lemma.). We have that the set of confusing models for R. satisfies
(M) Us (s) Alt (M,).
(7)
where Alt (M) = {M' E (M) : Qit, (s,0) > (s) is the set of confusing models for (s, T)
B.2.2 Step 2: relating the KL divergence to the sub-optimality gaps
Using lem. B. we can convexify the characteristic rate and related the KL-divergence terms with the sub-optimality gaps (s, a). The goal is obtain an optimization problem where only the sub-optimality gaps depend on the reward function. We have the following result.
Proof of thm. 3.2. The proof follows similar steps to [16].We We begin by decomposing the set of confusing models. After that, relate the sub-optimality gaps the inner product between the transitions and the value functions. Using this relation, we can lower bound the KI. terms in T(w; M). Finally, through an optimization step, we establish the upper bound. In the proof, we indicate by VM, the value of a policy π in MDP My, and similarly QM,
Decomposition. Fi (s). in [16], we combine the condition Qhi VM with the fact that Qú,, (s.a) (s, Vi,, (s) to obtain that
as VM, (s) Qu, (s. + QN: (s, VW:
This is similar to Eq. (5) in [16]. Next, let AP(s, (s, (s, a), where Par (sim. Par(s, a)) is a vector of dimension S representing the distribution of the next state given as. Further define the vector difference between the value M, and Mr: AV VM (s1) VM. (s1)
(ss) Vis. (ss) Then, letting 1(s) cs be the unit vector
with in position 8, we find
(s) < <PM,, a) T - (a) VV,, 1(s) AVV; = =>)P(s, Vir. = +(7Par(s, - 1(s)) A
(8)
Hence, the condition Qúi, (s, > V is equivalent to the inequality in (8). This inequal- ity only involves the pairs ((s, a), (s', =+()))), and therefore the infimum over Alt (M,) of E., w(s, a)KLmMM a) is model M' satisfying KLM (s, 0 over all the other state- action pairs.
Hence, using lem. B.1, and the reasoning above, we can write
M)-1 min min inf rER (,0) (.
[wss, (LLI
+ Σ w(s +s) (s',
Sub-optimality gaps. We now relate the KL-terms to the sub-optimality gaps, similarly as in [53, 16]. For any state and action a * (s), we write each of the terms (8) as a fraction of (s, using {o.))=, which are real values satisfying E 0,2, 1:
= >/PPss, a) TV W
(s,a) (7 (8, a) 1(s)) AV
23

---

For the first term, we obtain
(a = = a) (V.. - - E (
AA a (M s 2 (s, (s,
where we applied Pinsker inequality. Therefore, we can write
(8, 2 oî A a)² MD, (s.
(B,,
For the second term in (8) have (s,a)ss, - 1()]]1 (s 11 + >(1
Par (s a)) & 1 + y and (s, S 1 x.. Following the same steps as in lem. B.3, we derive that
K,(s,,, S Kr,
(9)
where K, == max, (8 (8, max( K ( 02), K, 02)) and
(a)))(s, 7)2 16, 77)
|a a) a)) -1-41313
a,, = min
(10)
Gy4/3MD, 1/3 (1+ 7
(a,A, (8,4)) 139(1 +)
10,2, (s, a) (1
(1,2A, (1),())))(11)))
Kr,((s,,,a) = min
17 +7)
14(1 + 7)4/3MD
(11)
Optimization.
Putting all the inequalities together, we find
M(w 2 min min PER a (s) ar >. ass1 afw(s, Br, a) + minw(s', ( (s, (s, a2).
inf
As in [16], the above inequalities are satisfied also when a belongs to the simplex, and in particular 4/3 also have of s a,
< |as], for E 21, Therefore we can write
M(= 2 min min inf afw(s, a) (s,,,s reR a.ag)=;()) aEE,
+ min minaas ( max a), Bra(s,a))
s'
with
Ar(s,a)((1-1) (1- (1 16, (1 7)) 6y (/3 41+331/3
() = min
(12)
(1) 73) A,(s,a)(1-7)3 139(1 + 7)2 17 14MD 4/3
(1-)) (s, (13())433311133)11 7)/33
Bra(s, a) == min
(13)
1/000/31111 (1++)4//
Optimizing for a, we get
T(w; M) 2 min min PRR (.)
w(s,, Br,
max, w(s', (0)mm/7(s))))))))))))))))))))( max B, (r,3)
Then, using that A, s ()) we have
Hs,s,a) min(H,,,, H,
T(w: M) & max max PER (,)
w(s a) ming w(s', (s()))
'erre we have different constants compared to [16]. In that work, we believe the authors may have miscomputed the constants by using the logarithm base 10 instead of the natural logarithm.

---

where
H,(8,)) = 2D2 (s,
(s(5,))
16y
6///3MD 7
HG,1 = max
(1 71-7)4/3
119 + +2 17
14MD 4/3 (1 + 7//4//
Hr. max
4 7)3 (, - 7////
1/3 (1-
Finally, as A, 1 (see [16]) and MD max (1),,,, we have that H we can derive the following simplified expression for the upper bound
139(1+7)² 2:
Henceforth,
(s, (s,
H, miming wis' m, (s'))
M) S max max FER (.)
(139(1+2)² (1-7)8 max
(1,7) by MMD (1-7)2
with H, = min
(1-3)0/3
Remark B.1. Note that one can improve the dependency in A in the second term of (wr; M) by considering A, instead, as done in [53] (we did not for the sake of readability).
B.2.3 Technical lemmas
In this subsection, we present and prove some lemmas useful for the proofs of previous results.
Lemma B.2 (Lemma [16]). Consider two transition functions P. p' and let AP(s, P()s, P()ss,a). Then, Vr E R, we have for the optimal value function V E R we have
IAP(s, a) TV < 8Va (400:/00...P0(0000))222440000000
P'(1,,, a))3/2
Therefore
min (AP a 16Var, (8, (s, S ('))))))
Proof. The first inequality follows from Lemma 4 in [16], and by noting that the variance/span terms are both convex functions in the reward for fixed state-action pair. The second inequality comes
from simple application of the inequality + S 2 max(a, b) to the first inequality.
Lemma B.3. Consider two MDPs M, M' with transitions P, P and a reward vector E R. Let AV. VM: VM, where π E 11* (M²) and Vū, is the optimal value in (M, r). Then
max(Ki, K2) S Kr, where K, maxx,000,((e) KL.M (s, with (s(s) {a: Qis, (8, VM, (6)) and | (1 7)
(14)
| 11:3 4/3 (1 4//4
K1 = min
(15)
16
G///3MD
| I (1 7)3
| oo0 (1 -//022
| 4/3 (1 4/3
K₂ = min
(16)
139
177
14MD 4/3
Proof. First, note that Vy. = VS and hence, AV- = Vis
VM.--
Since the reward the same,
we have that
AV. = + VA.
where AP" - PT. Hence, ||V/ o0 ILPAP Il.0 Following the same logic as in lem. B.2, and upper-bounding over all states and optimal actions obtain
4-2
|| A V 113 <
(1 - 7)2 (2Var, + V2MD,K3/2)
25

---

where
K, = max (.)
Var, (s)
max
(s,,(s,
MD, max MD(s,
..EEO,(5)
Therefore
K1 min | (1 7)
AAV. D0 (1 4/3
< Kr,
(6y2Var,
27/3,4/3M11"
and note that 27/3 6. Secondly, we can also write AV, = 111
Using Lem. 5 in [16]. we derive
32 log (2)
8log(2) (1- 70/2
25/4 Kr 3-34 MD,
AV 00 -
(1 (1-
(1-7)
Using the fact that + + max b, c), we find the following lower bound on K,,
| r 12
7)3 |AV l (1 7//22
|AV," 4/3 (1 7/4
K₂ = min
S Kr,
288 log(2)
14g
34/3, 25/3MD
and note that 288 1og( < 139 (natural logarithm), 24 < 17 (natural logarithm) and
34/3, 2D/3 4/3 14. Combining the two inequalities K1 S K, and K₂ S Kr, conclude that
max(K1, S Kr.
B.2.4 A Closed Form Solution for the Generative Case
As a corollary, we find upper bound on Uww; M) that admits closed form solution in the generative case (w E Q(S x A)). Although this solution is not optimal (i.e., does not attain the optima of (w; M) under the constraint 9(M)), we can consider it computational--fficii approximation the optimal solution.
Corollary B.1. Consider
A(S A R). We have that an approximate solution to arg inf ())() Uww; M) is given by
(s,
a ()),,
E(s,a,r) x
(17)
H E.ES ((( otherwise,
with ((, Erer a(,,,,T), =+ 2,M H max.er /1
Proof. We first derive an upper bound of (ww; M) and then show the it can be solved in closed form.
Upper bound on U(w; M). Introduce the variable E(s, a, r) such that w(s, a) ErER ((s,arr). for all as,a) S x A. By rewriting Uw;; M) as function of &, we have
M,
H,
U(: M)
max max PER (s))) A, a)² Σ,- ((s,a,r") A.E, ming (;(),
2- (s, a) (, ((s,,))
H. A.ming ( (s'),,))
max
max
rER (s)
2- Ms,
11 min (( ())))
< max rR s.
max
(s,s)){(ss.0))
a, ((s,a,))
H*
max
max r (.)
ming E(s', (s'),,)))
26

---

where we used that (2 + y) S 1/2 for x. > O in the first inequality and we bounded the second term using H" eax,eR H, H in the second inequality. Finally, to lighten the notation, let 2, /),)),))))*
Closed-form solution. We now show that the problem the last line of the previous equation be solved in closed form. For the sake of notation, in the proof we denote by O, {a : QM, (s,a) VM, [ the set of optimal actions in state for the MDP M,.
To distinguish & when the action is optimal, or not, we write Esra if E (s)s and E(s, a, r) otherwise. After introducing the auxiliary variables t, 2 0 the optimization problem can be equivalently rewritten as
min t+p Ed..
Hr(s,a) O,
s.t.
t t
a(
H*
p 2 Eora
O,()),
(18)
Σ E(s,a,r) =1,
2,0,
{(s, a, > as,ar
The Lagrangian associated to (18) is then defined as
H
-)+
Hr(s,a) E(s,a,r)
L=t+p
Σ
Σ
Mara
p)
Esra
(s)
A Σ ((s,a,r) (()
Σ Verae(s,a, a,),
+
where 0, are the Lagrange multipliers. Through the KKT conditions one derives Vera = 0 for every (s, a, r), and
dc = 0
Σ
Para = 1,
00
(
0C
0
Σ
Isra 1,
0p
s.r.aE0,())
Oc
(s, a)
0 = X para
0, s,r, Or(s),
(5 a,r)
{(s, a, r)
OC
H*
= 0 X 0
O, Or(s).
DEa
Sara
We further find that E.ar E(s, a)), 1, (s a)/E(s, r) for every s, T, a & O,(s) and H' for every s,r, E (s). Hence it follows that all the Eera have the same value, that p Euro
denote by Eo-
H,, to find t, observe that (s, rg(s, a,)) = Ennago, Hr(s,a) = =t(11 Esum), where Esum Eanaeo, Eo Eo|g), with g a()
From a(s,arr)
E S, R, O,(8). Thus
E(s, (,s,ar)) r) Msrat t + t= (1 Ssum)
Use the fact that E Earago (, a) = t(1 Eoum) to find
A
Σ
Hr(s,a,T) = =t?
(,
ac From HE..o
0 find À = 0rra H' / ara and
Esrad BeraP = p= Eo
27

---

Thus À = p/50 = H- (C and
H
Σ H,(s, f.
(,1.g0,(4)
Therefore
H*
Σ Hr(s,a)
Eo
G
(s)
Finally, to determine I, note that
Σ -((
(s).agO,())
Hence
Σ a) s,rap(,(0)
Gill
Σ He(s,a).
Therefore E(s,a,r) & (s, for all V H. Es.rago a)(x otherwise. The result in follows automatically from the definition (( = EFERR(s,a,r) a(),
S,r R,a & 0r(s) and g(s,a,r)
B.3 Extension to Random Rewards
In this appendix, we consider an extension of MR-BPI in which the observed rewards are random. We begin by motivating the setting, and comparing it the setting used in the main part of the paper. Then, we introduce the model, and its assumptions. Finally, we extend the lower bound to this setting (app. B.3.1) and derive the corresponding convex upper bound (app. B.3.2).
Setting motivation. So far, we have discussed the setting where the rewards are (endogenous signals) specified by the user, rather than being provided by the environment (exogenous signals). This distinction is crucial because it influences how we model and interpret the reward signals. Endogenous rewards are typically deterministic, as they directly reflect the user's specific objectives (e.g., a fixed reward for achieving particular goal, ensuring a consistent reinforcement signal). Conversely, rewards provided by the environment (exogenous) are typically variable and uncertain. These rewards may be modeled as random quantities with distribution conditioned on observed state-action pair, as described the next paragraph.
Model. We shortly describe the MR-BPI model with random rewards, which uses a slightly different notation (w.r.t. sec. to accommodate the random reward setting. In this section, we assume that the number of rewards is finite. Let Q be set of distributions over real numbers conditioned on the state-action space. In the following. we use E {I...., [Q] an index for the elements of Q, so that d: is the i-th reward distribution. The related problem specific-quantitie and definitions are hence indexed by i, (instead of in sec. 2). We also denote by rgg. (s, a) the expected reward for state and action (w.r.t. to the corresponding reward measure q:). Similarly to the deterministic-rewwr setting, we assume that for all rewards i E [1....,/[)] the optimal policy कद is unique.
Agent interaction. At each round / 2 1, the agent in state 8, selects an action at, and observes set of rewards samples (Fi, (rr.((s,a))))e) (t)) where (8,, 0x) ~ q.(-1se, (, az) and the rewards conditioned on the state-action are independent. It then transition interaction repeats. In this section, we denote by IP the probability law (resp. expectation) of the process (Ge)s, where Ç (St, Se, ...f....,,1... r))).)) We also denote by F, = a(( ... (() the o-algebra generated by the random observations made up to time t. For such algorithm, we define to be a stopping rule w.r.t. the filtration (Fz) This stopping rule t simply states when to stop the exploration phase. At the stopping time the algorithm outputs an estimate ी,, of best policy for any reward r R. using the estimated MDP M,. We focus on 6-PC algorithms, according to following definition, and we impose few mild assumptions.
new state 81+1
P(-|s,, a.). and the
28

---

Similarly to the deterministic reward setting. the goal is to devise a 6-PC algorithm with minimal sample complexity, according to the following definition
Definition B.1 (6-PC Algorithm). We say that an algorithm is 6-PC if, for any MDP M E M, P(r 0C, (Vi E (l..... 2 क... = n; 1
B.3.1 Lower bound with random rewards
Theorem B.1. Let E (0,1/2). For any 6-PC algorithm and under assumption (3), we have lim inf
r/r [1/5]
2 (M), where
sup WER(M M'EAB(M)
inf
Σ
D((s, a) MMpr
(19)
5,a
with KL M. (T((P((ss,), ()()),,a) and KT (8, (L a), (()))s,)).
(s,)) + E. KL Kg (s,a)
where (L
Proof. The proof proceeds similarly to the one of the lower bound with deterministic rewards app. B. The main difference is that the log-likelihood ratio L, also includes the reward observations sampled from distributions Q.
log-likel ratio. Let Q E Q, and consider the MDP Mg = (S,A,PP.,,)) and an alternative model M2 (S, A, P , , 7) such that P < Pr and < q'. The log-likelihood ratio between M and M' of sequence of observations (20, 21. where 2, (s ag f1,1, ...y Fi,s), J. is defined as
P(snlzn-1) log P'(8n|zn-1)
(Timn 2n-1)
Σ
Σ
log of (ri, 2n-1)
To simplify the analysis, let
(Log P(sn|s.a) log p'(snls,a)
10
9: (r(rmlls.a)
L
(s. =.)=))==aa))
+
log (T
n=1
1=1
Ne(s,a)
P(ynls,a) P'(nnlls,
qi qi(zimlssa a) log
log
(0,,,,18 (8,
where yn and Tan denotes the next state and 7th reward component collected after the pair (s, a) has been visited for the n-th time (s, a) and Ne(s, a) is be the number of times the state atate-action pair (s, a) has been visited by the algorithm up to time Then we can write L, E.o L
Hence, the stopping time we have
Ex [r]] = Σ
Es [4
8,0
(=(a.a)
P(
log T: (11i,11s ( 88 a)
Σ
EM
log P'(yn[s,a)
P(u (s, Pd P' 8,0)
Σ EM
Σ t=0
1 (N-(2))2
log
log
of (f a)
Since Ws.a = log PM.. s.a)
P(u. (..0)
log (asa) is independent of F. and since (N (8, S (3.,)1)))))
i=1
n 1]c= (N, a) 2 n
E F we have that
[. = ΣΣ PM (M((N(s, 2 & (
(s, a))KL (s, (s)
8,8
29

---

where KL M.M KL(P(18,aa) (+(s,))) E.e (I(a((1s,,) (l),))))
ô-PC argument. Consider a 6-PC algorithm Alg, and define the event & = UiE where
& = f + m!}- Note that, since we are considering a 6-PC algorithm, we have
(M) S 6,
Let then M' Al).M). Let Alt(M) (M' 3i ,,.... 12,, (M,) = 0), and note that write Alt(M) (I. Alt, gg.) where (M;) {M': ITM n II" (M, 0). Furthermore, we have that
P (E) - 8.
In view of the transportation lemma [82]. we can lower bound the previous quantity at the stopping time
Σ EMINN k)]KL 2 M (s, a) 2 kl P Par [&]) 2 kl(6, 6).
As the inequality above holds for all M' Alt(M), by optimizing over the of confusing model, we have
inf (M)
(N, (s, 2 kl - 8).
3,a
Sample complexity. By taking the minimum over the set of rewards, letting w(s, = N /))/Ex(T)) and optimizing over all possible allocations w E Ω we have
EM sup inf
Es( M (s, a) kl 8).
WEA(SXA) M'EAR(M)
Finally, taking the limit as > 0 yields the result.
B.3.2 Relaxed characteristic rate with random rewards
Theorem B.2. For any allocation A(S A) have that Te M) I Uolw; M), where
2( MD (s, a) +1) +1)
H. + 2/ 7)2
U2(w;
max (s)
(20)
A A, a (s.
A min, w(s', (8))
and H; = min
139 32(1-7)
maxx
16Vars
(1-9119
GMD
Proof. The proof follows similarly to the one of thm. 3.2 but uses different decomposition of the analyic form ([16, Thm. 2)). We sketch its main steps below.
Decomposition. We first state decomposition result the set of confusing parameters similar to the one presented in lem. B.1 for deterministic rewards.
Lemma B.4 (Decomposition lemma random rewards.). We have that the set of confusing models, for all = -,...., Q), satisfies
All,(Mg)) Unaazt All (M₃))-
where Alt (M = (M' E Alt,(M,)) (3 > VM (5)) is the set of confusing models for (8, I). Remark B.2. Note that T3 can be equivalently rewritten using thm. B.2 as
(TH)
sup min inf WE((M) 1,5,072((0) (s) Altaaa staa
Ew(s',a) (L ,') + Σ
KL KL (s'() .3))
3
30

---

Lower bound analytic form. We now rewrite the lower bound optimization problem analytically in a similar form to (5) in [16]. For all 8, s,a, let dr, a) (8, Th (s, a) and ds( (s,a) = Pir (s, Par (sr(s,a) a). Further define the vector difference between the value in M; and Mf:
dV.' = Vi (51) ( (s1)
(ss) - VM, (ss)
Finally, we let 1(s) = ea be the unit
vector with in position 8.
Fix 1, (s). Then, we find that M' E Alt s,0, i (M) if and only if
dr:(s, A.(s, < rdP(s, a) VM. + (7PM: (8, a) ( -(())) (1-7Pa:) -1 (v'z - Tmz)
-1 (1-)pp)) (m;))
+ (T)Pr - 1()))
Hence, the condition Qhr (8, > Vin (s) is equivalent to the above inequality. This inequal- ity only involves the {(s, (s n, (s))), and therefore the infimum Alt (M,) of Q Eea w1s KL (s a) is a model M' satisfying KL KIMM (s, a) 0 over all the other state- action pairs.
Hence, using lem. B.1, and the reasoning above, we have
min 1,,00 (o) M'EAlt (M)
inf
wis a ()KLMMMM
+ Σ ((s,
[L ( (('))) + KL KL (s'. (s()))
Sub-optimality gaps. We now relate the KL-terms to the sub-optimality gaps, similarly as in [53, 16]. By following similar approach to [16, Thm. 2] and the proof of the relaxed characteristic rate in app. B.2 one can show that, for any a E Dx. we have
KL KL (8, 2 (an = a3 (s.a)
(,
KLp,r (8, 2 (22( = a3 2D a)²
max, KT, nT (5 2 (,,3(03) = 03 (A,(1-)))
2
max, KLpjp('' (6) > (a,s(04) min
[a (1-2((1-2)1
[1.A(11~>))
16Var,
27/3MD
a3
a1 21log(2)
4/3 (1 (1-44// 25/3g//MM1
max, KLp)p(s', m) (s)) 2 (o.s(oa) = min
288 (2g(2)
Optimization. Putting all the inequalities together, we get
a. (e) an To(w; M) min w(s (a))
min w s, मं (Bi, + (ax), (a,s()))))
Then, proceeding as in thm. 3.2, and optimizing for E BS such that Σ, = 1 yields the result.
B.4 Extension to Continuous Set of Rewards
In this section consider the extension to continuous set of rewards We briefly motivate the setting, and then explain what are the challenges.
Setting motivation. So far, we have discussed the case where the set of rewards R is finite. However, it is also useful to compare with classical reward-free techniques, which do not rely on
In this context, by continuous set, are not necessarily referring to a connected set in _R"", but rather to set with non-countable number of elements.
31

---

pre-specified reward signal. Therefore. we extend our discussion to include a continuous set of rewards. This extension presents several challenges. First, may not be feasible assume that the optimal policy is unique for each reward. Second, the minimum gap can be non-convex and discontinuous, as we will diseuss in the following section. However, we find that, in practice, sufficient to consider finite set of rewards. This observation provides a basis for the implementation of practical algorithm.
First, we address the challenge of optimizing the inverse of the sub-optimality gap over a continuous set of rewards. Later, we propose a practical solution by considering a finite set of rewards.
B.4.1 Non-convexity of the minimum sub-optimality gap
The relaxed characteristic rate is mainly characterized by the minimum sub-optimality gap A, = oeEg)) A,, where (s) {a Qh, (s,a) (s)} is the set of optimal actions in for the MDP M,. Unfortunately, even with a convex sel of rewards, the minimum sub-optimality gap may be non-convex and possibly discontinuous. The discontinuity arises from the fact that in certain state(s) all actions are optimal for specific rewards.
We illustrate this intuition with example. Consider the MDP depicted in fig. 2 with states S {50, } and actions A = {ao, ). For this MDP, we have P(sol {50, $1), ao) = 1, P(s1 (0, =
0.3, P(solsu Su, a1) 0.7, ((1 ($1 a1) 0.3 and P(5o|s1, a1) = 0.7.
We use the following reward function, which parametrized by E [0, 1], vector form
(fa.80) 0
(#g.a:) )
0
= 022 + 0)e
(#1,00)
0
(s1,0:)
1 0
Next, we derive the sub- sub-optimane optimalltl gaps (o(s, = Vz (s) (s, a) as a function of A. Optimal Value function Vg and policy Tg.
For a discount factor ? = 0.5 we obtain that
7 Vo (so) 20
Vi (8o) max
Vo (so),
Vo (81)
20
action
action
7
3
(g max
V (so), 0
Vo (8o) +
(s1)
20
action og
action
One can immediately see that aj is optimal in 8q for all 0, while in 81 we need to distinguish between the two cases.
ag is optimal in 81, then we find
40
20
V (8o)
0,
(81(
0.
23
23
Alternatively, o, optimal in 81, then
Vi (80) = 7 + 10'
13
Vx =
0
5
10
is possible then to see that for 0 < 23/26 the optimal policy хे = [a] a1] is to choose action a in both states, while for 8 > 23/26 the optimal policy тे [ai ag changes that action du is now optimal in state $1. For 0 = 26/26 both actions {au, a1 are optimal in state $1-
Optimal Action-value function Q2-
We distinguish two cases. For 0 > 23/26 we have
20 0
Q7 a)
Go
())
ag
23
0
01
23
a1
32

---

4g = min, minagcuss) Au(s,a)
(ao, 1, 0); (a1, 0.7, 0)
(01, 0.3,
(a1, 0.3, 0)
80
81
(ao. 1, 0), (01, 0.7, 1 0)
Figure 2: On the left: MDP with two states and two actions; each tuple (a, p. r) consists of (1) the
action a that triggers the transition, (2) the transition probability and (3) the reward r. On the right: the minimum sub-optimality gap Ag as function of 0 [0, (note the discontinuity in 0 23/26).
While for 0 < 23/26 we have
@3(80:0)
26 [30+
20
a
ap a1
@3(,1,a)
10
7
20
a 4n
10
a
-3 0
5
+
10
a
= a1
Minimum sub-optimality gap. Hence, we conclude that the minimum sub-optimality gap is
0 +
a
0 < 21
10 20
13 0
<
23
Ag min min (s( agDa(s)
TO
23
26
26
26
23
<0
< 1.
23
26
Note that the minimum gap is non-convex on 0 and it has discontinuity at 23/26, shown in fig.
B.4.2 A finite set of rewards can be sufficient
In this subsection, we derive convex upper bounds on 7 (M) when R is a continuous set of rewards. The idea find finite of rewards R' that can still identify the optimal policies for all rewards in R. The proof follows similar step to the one in the discrete reward setting in app. B.2 but relies on the following assumption.
Convex hull (CH) assumption. We assume that the convex hull of R' contains R. This last assumption is easy to satisfy, since can just consider the canonical basis Reanonical in R'. Using this property, we derive a novel decomposition that leads to an alternative upper bound on T(w; M).
Theorem B.3. Consider continuous set of rewards R satisfying the non-degeneracy assumption, and a finite set of rewards R'. Assume that R' satisfies assumption (CH) with respect to R. Then, for all Q(S A) we have that
(s,
T(w; S min min
PRR 8,0 A - (w((s
Proof. Using the decomposition in lem. B.5 in conjunction with the results in prop. B. and lem. B.6 leads to the desired result. Using also that for any w E S
MD)
2
<
8
max KL (s, a)w(s, a)
(1 722
((),a)
MDc(6',a1P
< 8
(1 7)2 max KL KL a) max s'
w(s' a!)
Alternatively may consider the conic hull of R', yielding similar result
33

---

Then
Σ
wis ())
(w; 2
min rE (M)
inf
s,a
Σ ((s (((
min min min rER cER'
inf M'EAR
(xr))") (M)
A 7)2
min min min wss rER cER a.
8>2MD (5, a)2
A 7)2
min min eER s,
(s.
While the previous bound in the worst case scenario scales as (1 - -4- one can use techniques as in the proof of thm. 3.2 to find scaling of (1 - -)- (we refer the reader to the proof of prop. B.1 and note that we could use lem. B.3 find an alternative scaling).
B.4.3 Technical lemmas
Confusing set of models decomposition: continuous set of rewards. From the example in fig. know that an MDP may have a non-convex sub-optimality gap over continuous set of rewards. Instead of considering the entire set of rewards, an alternative could be to just deal with a finite set of rewards R' C R.
We obtain a dccomposition that depends on R' as long as every reward in r E R can also be written convex combination (or conic combination) of the rewards R' (which can be guaranteed simply by including Reanonical to R').
Lemma B.5 (Decomposition lemma for continuous set of rewards.). Consider a finite set rewards R' such that R C. Hull(R') and each E R' admits at-least confusing model with respect to M, (as in assumption (III)). Then, we have that the set of confusing models for any E satisfies
(M) C USER U2,afm;(s) AMrraeeM)
(21)
where Alt AlteareMM (M' (My (s).
Proof. Consider reward r R. From the fact that is contained in convex hull of R' we can always find 0 [o, 1] such that EeER Boe, where tg is the non-negative coefficient for the corresponding reward e (satisfying E. Og = 1). We start by showing that (M) S {M'l e R' S, (s) (s. (s){ with
(s)}
π -
By contradiction, assume there exists M' E Alt(M,, so that Ve E R', s S. + T(s) the inequality Qua (s, < (s) holds. Then, since Qh, (8, (s)) Vy, (s) the inequality (s,((,,)) S
Vig (s) holds for every e, 8, a.
By linearity, the inequality holds also if we multiply by x 2 0 both sides. Choosing I = 8g, and summing over e, obtain that
(. $ Σ Be VM (s).
HER'
Letting ja,a +L,...,,AA be the index corresponding the state-action pair (s, and (P')* be a), we obtain
the transition function associated to policy म, i.c., (P")" (s', a) = that"
JT (1- (1- = Qú, (s,
WWe indicate by e; the i-th element of the canonical basis.
34

---

Therefore, we conclude that Qúr; (s, I Vr (s) is valid for all state-action pairs.
Let now A be an optimal policy in M. Then, for all states we have Qhy, (s, #(s)) S My, (s). Hence, as in [16, Lemma 2], by repeated applications of the Bellman operator I with respect to the MDP My, one can conclude that Vas. (s) S VT (s) in all states.
However, this implies that is optimal in M', which contradicts that M' Alt(M,)
Remark B.3. While the previous lemma is stated for a convex hull of the vectors in R', it can be equivalently stated for a conic hull of R' This latter version can be used if, for example, one considers Reanonical (note that the conic hull of the canonical basis contains all rewards in [0, 1]SA).
Upper bound on the minimum sub-optimality gap. In the following proposition, we derive bound on the minimum sub-optimality gap-
Proposition B.1. Consider two rewards e and two MDPs M, M' such that 11" (M,)))I)) Then
27 AAP(s, a) VV.
A. S
VM.llss Il
(22)
where AP(s, aP (M a) (Mr a), and (s. (sim. Par(s,a)) is vector of size S representing the distribution of the next state given (s, a).
In particular we also have
72
A S
max KI. MI.MMMM (MM 8,a
(1 - 7)2
Proof. The fact that II" (M,) for all π E II (M,). Let so be a state such that in M, there a sub-optimal action. Henceforth, we have that A $ VM.. (su) Qi, (so, a) for some Hence
implies that in all states we have 0 S Vig (s) V (s).
A. S Vir (so) Qir. (so. + Virg (8o) Vir (su),
S ||V. Vuē; bloo 11Q Qialloo
Now bound the two terms separately.
1. For the first term, let n' E (Me), and since Qis, (s, ('s)) 2 Vis, (s, (s)) write V... (ss) = (s)))s - Qir. (s, n (s))),
[Vig
S Qās (s, (s)) - Qis. (s)),
< 10:; Q2a llo.
Therefore I|V V 10 5 110 Qīs. 01.00 = 117r. Qis Hence, since
1QM. (2g](3, a) = AP(s, a) TVi.. + Par a)T (Vir. vite)
we obtain
112 - Quo S 2 --1IAP(ss Vin
Icading to IIVù, - Visg 110 S - AP(s, a) T Vls..
2. For the second term have
Liv. (s) = AP(s,)) V (sr ((Vi,, -VM:)
hence, as for the first term, we have liiin: lir S 11 TV..
Therefore we have that A. < 2 I[PP(ss Vi. lloe.
Finally, an application of Pinsker inequality leads to
72
72
A3 < (1 7
max 5,a
V7
2 s
max KL s.a
(1 - 722
35

---

Lemma B.6. Consider two MDPs M. M' and two rewards e. for all policies π E II (M,) there exists a state-action pair (s. a) such that Qi: (s.a) a) VM (s). then II (M,) IT (M))
Proof. The proof simply follows by the fact that for all policies π E IT (M,) there exists state where the policy is improvable. Therefore, none of the policies in IT (M,) is optimal in M
36

---

C MR-NaS Algorithm
In this section we describe the MR-NaS algorithm in detail. We prove its 5-PC property and its guarantees the sample complexity.
Notation. In addition to the notation introduction sec. 2, in tab, 3 we provide a summary of the notation used in this section.
Table 3: Table of Notation
Symbol
Description
2
State-action space, 2 = S A.
Pr
Transition induced by æ, that
P=((s', a') (s., a)) P(s") s, a))((alss')
Ps
Transition induced by uniform policy,
Pi
Transition induced by the policy n. of MR- NaS.
Mr
Estimated MDP at time step
Stationary distribution induced by the policy Tt.
w
Stationary distribution induced by the policy n².
Averaged stationary distribution ,, == (1/t) En W
Wy
Stationary distribution induced by the uniform policy.
w
Optimal allocation w* == arg ini (a(()) U(w; M) w.r.t Uww; M).
T'(al (als)
Oracle exploration policy, defined as π² (a(ss) == (" E, (b(s). Exploration policy at time step I, defined as
#t (a)
(als) W/ / E, (bls).
Defined as 14 == 1/ 1/)
77p
Maximum number steps to move between any pair of states (s, s').
Maximum number of steps to move between any pair (8, a), s'',a'.. Equal to m mgg + 1.
T/k
Minimal probability reaching from = in n S k transitions using a uniform random policy, defined as
Tee = min (2''=))) 2, (1...., k), ( 0).
"
Defined as == 7mmm
PP(P) or (B))
Ball of radius around transition function P. defined as
{P" max, [[ a) - ('(-|s, a)ll S p}.
We
Rank-one matrix whose rows are equal to
Tu
Ergodicity constant such that PM (z (2) > for all r 2 ru-
Constant, defined as og = min prole #) /w (2').
du
(e,,, m)
Defined as (ee,, T) = (1 <)4 mins,a T(aass) + +,, Ou-
x)
((e, = -000-,EE,
C(E,TT
C(e,,)== 2)
ple,m T
p(e,T):= 0(e, 2//m0
L(c,T)
L(E,T) == (1 plc,
(1-p6,, T))
C(C,T)
Tt, O2, Oipe, Li
Respectively defined as o, = ole, mt), 0, == OlE, nT), etc.
Convergence of the MDP estimate and state-action visitation frequency 3 (V(s,u) E Z, lime N1 a)/l (s, a), lom Mr = M).
event
Ecut (A)
Count event, defined as Ecus (A)
[A) 1, V(, a), N.(s, a) >
Yim
log
2 k=
(km))+>
El (E)
Concentration of the empirical MDP event
()) nf n (M, E B)te)(M)
(E)
Concentration of the state-action visitation frequency event
E7(E) = Tr (1 - w=1 5 Kgt).
37

---

Remark C.1 (Extension to the setting of continuous/stochastic rewards.). In this setting we consider the case with funite rewards. For the other two settings described in app. B (continuous and stochastic rewards), HR-NaS can be directly adapted by using the relaxed characteristic rate specified in app. B.3.2 for stochastic rewards and app. B.4.2 for continuous rewards. The primary modification involves the computation of w², where the relaxed characteristic rate appropriate for the respective setting should be applied. Furthermor, for stochastic rewards, the algorithm also needs to account for additional exploration threshold in the stopping rule similarly to [17, Prop. 53.
Remark C.2 (Novelties with respect to previous works.). Our work is mostly inspired by [17]. With respect to previous works, we introduce novel forcing policy that does not use an exploration factor that depends MDP-specifie quantities, such as the "connectedness" of the MDP, that we denote by m. In [17] they use E 4==0 t 2mm4,, while we use e, 1/ max (s:))) This change requires a slight modification of the proofs in [17], since now c depends also on the number of visits of St. Additionally, we improve on the high probability forced exploration [17, Lemma 111,
1/4
17mm where the authors have scaling of N1(8,a) V. (L-
while obtain scaling
L 1. log( (AA(S) where Hay is the x-th generalized harmonic number of order y and 7m is the minimal probability of reaching state-action pair in m steps under a uniform random policy.
Ne(s, a) E Nm 11
C.1 Forcing policy
We begin by providing some results on the forcing policy, that serve as a basis to obtain sample complexity results.
Consider the forcing policy T-,a(- = tmax (x) N1 )), which is inspired by the classical Boltzmann distribution. Intuitively this forcing policy will choose actions that have been under- sampled. We find the following lower bound the probability of picking action at time
t 2 1.
Lemma C.1. Consider the forcing policy (f((-1s) = softtaaa ( (-B((s)N.(ss.)) with 3e(s)
max. (N,(). Nc(a.)] and 3 E [0, 1]. Then, for all t 2 we have
9 (c))
TTa(als) Z AN
(23)
Proof.
Note that proving (23) is equivalent to showing that
(((MMM))))))) (((())
We actually show the following stronger result:
ANe(s)& (olss)&e-&(0n (s.)) 2 Ae (B((s) min, Nc(s,b)
(c())).(s.)))
Therefore, taking the logarithm on both hand-sides, we obtain
3 (N) 2 (Nss) min N;(s)) = (log(N((s))NN(ss))) min, Ny
max. Ne(3, a) ming Ne(3, b)
Thus, we obtain the condition
N1(s, a) min, (s)s) max, Ne(s, a) min, Ne(s, b)
which is always true for all A. proving the lemma.
C.2 Almost Sure Sample Complexity Upper Bound of MR-NAS
We now describe the forced exploration property of MR-NaS. We conclude by showing that Ne a)/t w' (s, a) a.s., and the almost sure sample complexity bound of MR-NaS.
38

---

C.2.1 Forced exploration property
The following proposition is modification to [17, Lem. 4] which combines a result from [83].
Proposition C.1 (Forced Exploration). The sampling rule of MR MR-NaS with a E (0, E [0, and + 3 & satisfies P (V(s,a) E 8 x A, lim Ni(s,a) = xo) = 1.
Proof. Recall that that 6 = (s)) and TT,((-|s) = sof toft (-Br(s) -)) with B((s) = 3 (o)) max, (5.() ming Ns[s,]] Therefore, using lem. C.I and the fact that a + 3 S 1 we have that
00
1
Σ
P(ae alse Ns)) n)
1 A
A.
==1
00.
Thus if a state is visited infinitely often, by the Borel-Cantelli lemma we have that the action is also chosen infinitely often. Using [83, Lem. 4] we conclude that a communicating MDP we have that IP (V(s, a) l, N.(s,a) = oo) =
C.2.2 Convergence of the state-action visitation frequency
Next, using the previous results we establish the convergence of (s, a)/t. For the sake of com- pactness, denote by Z S A the set of state-action pairs, and by P=((s', a a') a)) P(5'|s, ()r((a(s') (s')s)) the transition induced by Similarly, we denote by P. the transition induced by uniform policy, and by P, the transition induced by the policy n, of MR-NaS. We also indicate by w* = arg (n(W) (w: Mf) the optimal allocation.
Proposition C.2 (Almost sure convergence of the allocation). Using MR-NoS guarantees that P (V(s,a) E 2, lim,+ (i a)ft (s, a)) where w* arg inf wemme U U(w, M).
Proof. To show the result it suffices ensure that MR-NaS satisfies the 5 assumptions of [16, Proposition 12] (see also [84, Corollary 2.9]). Assumption is a consequence of the fact that the MDP is ergodic under any policy that assigns positive probability all actions. Hence, also P. is ergodic. Assumption 2 is guaranteed by prop. C.I: since (s, a) + oo a.s. for all (s, a) E Z. then the estimate of the MDP converges M, + M almost surely. By continuity, and the fact that ae is a Cesâro mean, we also have wi - w" and wj + wt. Hence Pt + Pa. almost surely, where T* (als) w (s, a)) Ee (s d'). Assumption and 4 are satisfied as in the proof of [17, Thm. 7].
In fact, by employing lem. C.1 we have that
P. (1 - ex) + E2P=,, 21 (1- Px; + PrP
with μ4 (s) Hence, one can follow the same reasoning of [17, Thm. 71. by also noting that He 1/ for every 1. Similarly, assumption 5 satisfied by noting that wt w a.s.,
and for all (s, E 2, et. f4 > almost surely.
C.2.3 Sample complexity upper bound
Next, using the forced exploration property, prove that the stopping time is almost surely finite and an almost sure upper bound of the sample complexity of MR-NaS that holds asymptotically as 8 O.
Proof strategy. The idea to prove that Nf(s, a)/t + (s, a) and that the estimate Mr + M. If (s, a) prop. C.2 (given prop. C.1 ). At this point, one can conclude by continuity of the relaxed characteristic rate over its arguments in the stopping rule.
a.s. (prop. C.1 the latter follows automatically, while the former is given by
Theorem C.1 (Almost sure sample complexity bound). MR-NaS with the stopping rule in props. 3.1 and C.2 guarantees that MR-NaS stops almost surely, and that IP (lim sup;-10 log(788 S UMM) =
39

---

Proof. Consider the event
= (v((,, 2, lim a((s,a)/t=uu (8, a), lim M, -MM
t0000
t-000
By prop. C.I we have that & holds almost surely. Hence, one can prove straightforwardly prove that MR-NaS stops almost surely. Under E, by continuity, AA > 0, 36x N such that VT Lx have UNNe/t; M,) 2 >w= MM)
(M).
Now, recall the definition of stopping threshold 3(Nv. 6)
log(1/8) + (S Note that there exists C. > 0 such that 8(N1,8) S log(Ct/6). Thus,
1) ) s, log 1+ N((e.)) )
we have that
== inf[t 2 L (NN
8)),
x la A ( -1- 2 B(Nr, 8)},
6(1
S t A ft L, t(1 -1) log(Ct/5)).
Applying [19, Lem. 8] we get
(M)
(M) +
CU*(M)
S max
tx: 1-X
log 5(1 + /2
log
8(1 -) A)
Hence lim suPs-10 In(1/a] S (M)) A). Letting A - concludes the proof.
C.3 Expected Sample Complexity Upper Bound of MR-NaS
To derive sample complexity upper bound in expectation of MR-NaS we define the following quantities:
1. Let mo be the (maximum) number of steps to move between any pair of states (s, s'). Then we can move between any pair 22, in mo + 1 steps at-most [17]. Hence, mo can be interpreted as a sort of metric measuring the difficulty of navigating the MDP. We also define m == mu + 1.
2. Let my == min {P" (z'|=)]z,,'' Z,n E k), P" 0} be the minimal prob- ability of reaching z' from in n < h: transitions using a uniform random policy, with & E N.
3. We define by (P(P) ()) the ball of radius p around a transition function P, i.e. (p(P)= = (P': max P(.ls.a) (-|ss, a)]lı p}. Since in the setting of this work an MDP is identified by its transition function, for the sake of notation we also interchengeably write B, (M) to indicate the ball of radius around M.
4. We denote by wa the stationary distribution induced by the policy n. and by w,, the stationary distribution induced by the uniform policy. We also indicate by W, a rank-one matrix whose rows are equal wt.
5. From the ergodicity of Pa there exists an integer ro such that (= > for all r 2 ro and all (z',2) - (the existence of ro is guaranteed by [85, Proposition 1.7]).
6. The oracle exploration policy r ((ass) w (als)/ Es wn (b|s) and the exploration policy at time step t: # (als) = w/ (a En (b(ss.
We begin by proving two independent results: (I) the geometric convergence of PT to W, in app. C.3. a result that is used prove the concentration of the state-action visitation frequency; (2) the forced exploration property of MR-NaS in app. C.3.2, which is used to prove the concentration of the MDP estimate. This latter result is novel compared to previous works.
We subsequently present the concentration of the MDP estimate in app. C.3.3 and of the state-action visitation frequency in app. C.3.4. We conclude with the expected sample complexity of MR-NaS in app. C.3.5. Finally, at the end of the section, we present some technical lemmas as well as an alternative result to the forced exploration property presented in app. C.3.2.
40

---

C.3.1 Geometric ergodicity of the sampling rule
In the following lemma we adapt result from [17] to our forcing policy x,.t. We also define the following quantities
mii
<(c, (1 c) A (()s)
c
Ou:
2,
(((, = 1 )(,
C(e, m) 2/0(e, m);
x)), = x),, 1/10,
[e, = (1 x)) C(e,
where du = ming.a' Pao (z/lz)/w((z) and ro, a, B are as before. For the sake of brevity, we let oi (Ee, m,),6 f(e,, m;), and similarly for Ct, Pt, Lt.
Lemma C.2 (Geometric ergodicity of the sampling rule). For MR-Nos it holds that
1, 1PP." Wellon S C.pp.
(24)
Proof. For two state-action pairs 2 (s, = (s',a') denote by (= the probability of reaching from r steps. Then, for all (z, we have
P 2 (1 - (1 + c Pro (z')2),
2 - (1- P (z'12) +
(2'1z)))
2 (1 - c P (z'(z) ra(a+))
pro (='1z)
Let C m (als) and note that Pæ; (='1=) 2 Ac Pu('I() for all (z, 2).
Recall the definitions for the stationary distribution under the uniform policy by who and oa. ming,2' Pro (zn))) Then, we can rewrite the previous inequality as
mla++8
(a(2') wa(2")
Pr z
[11 Ac)
To Et
pro (z'
mla+
[11 (1--e) ex) Ace
ro c
o ouwi (z');
nula+8)
[11 Ac) To c
o owmiy (2') (2')
Then using [17, Lemma 21] we conclude that for all n 2 it holds that:
||P." Wello S 20
Hence Pt also satisfies |PP," Welloo I C.p..
C.3.2 Forced exploration with high probability
In the following lemma, we provide novel result for the forced exploration property of KR-NaS, which relies on lem. C.7.
Lemma C.3. For all E (0,1), m = mo + 1, define the event
Eent (A) = 1I 2 1, ESE (((,a)
T/m
log
SA 1
2 k=1
(km)a+D
Then, for MR-HaS with a + B S 1 we have that P (Een(A) SA
Proof. Fix a state-action pair = (s,a) and let Yú 1a=z and X₁ = 1y Dm Dm +Yem for
k L...., L.. Define N N (s, a) Σ
k=l Xx. and note that Ne(s, > Ni (s, a) for all
41

---

t2 1. Let Qx = F = 1k1), where F& = OYY1.... kmm). Note that we can also write Qk
as Q: P(3n E [l.....m] Y(k ((--1)mm 1)mmn k- Then
Qk B(x.) PP (3n fI,...,,, m. 1(k--)m++ 1 (TT))e) (
(Y<= 1)mmn F (TT)))
2 (()))
max mm
max PP (2(k-1)m-n = 212 = = 20, Fk (Tt)t) Isnsm
2 (x
R-1
max E (=)) Snsm
((=-))))((((--))mm =2 1)m+5 = 22)121..... 2n 2n = 2
120
2 (
(=)) I5nsm
max
(km))+8 Pu(=(k-1)mtt-1 11m+t-1 = 2j+1 2241(2(K-1)++
100---mms------ = ,. = 1z0
=B
max Isnsm
(km))a+B
P"t (2(k 1(k--))+nn 212 = 20)120
Mm (km)a-8"
Hence, for X 1 O due to lem. C.7 we also have
P 31: No:N((
7m (em)++.
X
SPP
71: N (8
Qk X
se-
2 k=1
Consequently, choosing X' = log(SA//) we get that
SA
1
(A) S Σ P
3t No(s a) S 2 Σ ax(s,a) - log
S
Σ 5,a
= A.
1
SA
s,a
The following result, automatically follows from the previous lemma.
Corollary C.1. For all i 1, under Eont() (A) we have
2
< S min(1, (A)) where (A) =
(25)
A Σ
(Amju FD 2 (lg((SA))))
C.3.3 Concentration of the empirical MDP
In the following lemma we bound the probability that M, is not close to M. In order to do recall that x* **(ass) w (als)/ Ee s (b|s) and # (a|s) (alss) s)/ Σ, w/ (b]s). Then, observe that by continuity of M2 + wi (due to Berge's theorem) we that for every & > 0 there exists such that for M, (MM) we have || 10 S.
Lemma C.4. For E 0, T 2 define the event (5) nf (T (M, (M)) where (T)) = T with E (0, 0.5). Then, there exists constant C > 0 that only depend on and M
such that
1 5 T2 CT (T) (2)p),
VT > 1,P (E)
(26)
where (T, (A)
(T) (A)=1
log Ax)
(km))+#
Proof. Consider the event Eent A) from lem. C.3 and let À = 1/T2. Note that
(E) S SA+P +
El (L) (A))
42

---

For simplicity, we omit the dependence on À and simply write Eent. Then, we have
P( (5) n Ecnt)
P(M, & Bp(M) n Eent)
(T)
Σ
P(max [|P((|)s P(-ls.a)ll > p Ecnt), 3,0
(2)
E
Σ P(IP)())))))) - P( > p/S Emnt)
t= (T) s,a
Now, let (x()) 2 Ex=1 (km)a+8 log () Then, we have
F(IP:(5'|s,a) - P(s''s 0,, | > &em) S (/ (g(()),
P(l k),
k
h k= (A)
f gi (A)
<
2expl (exp(-2(k-)) + ge (x()))²))
k=
(-
S (exp(-2g((A) (A)p)
Σ
2exp(-2kpp)
k=0
eexp( -2g(
1
- exp(-2pp²
Hence, we find
T
(ppp((2g(())))
T
25 A exxp(-29:(A)pp
Σ Σ
- exp( 2p2)
1 - -expp-120 (22p2)
(T) 8,a,
h
2 AT exp( - -1) (2)
1 expppx2ppp
C.3.4
Concentration of the state-action visitation frequency
Recall now that wi is the stationary distribution induced by the exploration policy ni at time t. Further, recall that Te (1 mz fLT w i Uw;; Mi), Wj (1/t) Eim w and that Ni (als) at (als) E at (8, d'). We have the following result.
Corollary C.2. Let T > L, E (0, 1). 0, E (0, For t 2 TP under (p,r(() we have that there exists and ni (A) such that
TP
IIwe -
-in-wwll w0 S KM
+ E +
(27)
[
As a consequence, under (E) we also have that
TP
P. - Pa- <
+ + (2-1
[-1
For simplicity, and w.l.o.g. consider hy(")) integer the summation.
43

---

Proof. Let (als) = w (als)/ Es w (6[s) and (a(ss) wi (als)/ Es wi (b(s).
Under (5) using [17, Lemma 23] there exists an MDP-specific constant AM such that
|| will 1/1 S Kas Pt Pr loc:
x kasl Tt T loo;
Ras ! xx 100 + cp.
Rad
[|| x l0 + ce)
Then, for & 2 TP, we have
T S t +
|| - n 1100 5
7 m
x*)
k=1
which concludes the first part of the proof. For the second part, simply note that
P| - Pr-1llo0 1 P|
Pa.lle
1l00
-1p. Pa-1llos
2
1-1 + + ((+1-1))
T
From the previous lemma we remark the following important fact: under (p) for k: 2 T 2 Tp we have
S Tp k + 7--P +
M x 100
In the following proof we provide a reformulation of [17, Proposition 19]. We require and T to be larger than some constants. Specifically, we require 2 7' (note that E (0, 0.5)) and
2 max (T)(S,
where E E0011) satisfies < 4,P + < 1 and Ty A) =
inf 2 1 2 KTM (A) Tu-3p773 with & > 0, E (0, 1) and defined in corollary C.I.
Proposition
C.3. Under AR-NaS there exists T(E, such that for all T 2
(g) go ++m and all 2 TL-P. and all functions f 2 - [0, 1]
have
wT) 2 (ec(e).r(3) n Eone (A) s 22exp(-16"
(am(()
(28)
where&
& > Kg a mapping with values o0) such that sumpup+ Kg sc.
Proof.
Let wz (ʃ) = Ez-w [s(=)] and wi wi) = Eznwn [=))). Then
D Eks f(*)) w0 (f),
1
k== {2x) - -w((f)
Ei-resi f(zn)) -
b
k==1 f(x) - -w*(f)
Eiero f(zx) - -ok)-wk-llle wk-
Eker wk-1(f) - wf)
t
t
(b)
(c)
First term (a). For the first term (a) for t 2 T and 1/T we have
(a) < T < T1-p-g SE
44

---

Last term (c). The last term (c) under E,, (5) fort 2 T is bounded as
x-1 (c) 5 Tk To 1 w01l:
t.
Ek=ro KMM (TP kk + 5 EIul
t
Tk T
S KM
{ ETT
T (og(()
S KM
{ ET +
+ en, + T
$ RM
vt)
S KM
+ ET, + T(1-3p)/2
Hence, under E (E) n Eent (A), since c $ nik (A) we get that (c) S AM (5 + Kr, (A) T0-3p7))
Let (5 A) = [T 2 1: 5 2 (AT + TC-3p172 } where ne is defined in corollary C.1. Then for T2 (E, A) we have (c) < 2
Second term (b). For the second term we use the function fa solution to the Poisson equation f(.) (f) = ffk Pafxl(-) [17, Lemma 23]. Hence
(b) (1/t)
Σ
fk-1(zx) Ph-1fa-1(2N) MM + C. Re,
k=T941
where
M, fi-rette-r(22))
fk-1(2x)
Ph- Ph- C. = Ei-ro41 PrSi(Zz)
t R₂ PraTFo((TT) Ptf((z))
Before proceeding, always under e Eone (A) for T' 2 T2(E, A) have that
lee| S KT, (2) S
and for 2 T9, 2 1/74-P
TF
T
| - n' 100 <
+ k
+
+ $ < 25.
-4-P
Therefore La S Lg, where Lg se <25 L(e, t.)
Bounding M,. As [17], f.M, martingale satisfying kh: (k 1)Ma-11 < 2L and
hence for f 2 - we bound using Azuma-Hoefiding inequality P[[MM]] 2 2L < <2exp(
For simplicity, and w.l.o.g.. consider 1 as integer in the summation.
45

---

Bounding Ct. Again, for 2 T
we have
C S (L/t)
- - + P - Pk-1lloeh
T=
(L/t)
Σ
Lk
| - wk-1l + +
1-1 (1-1+E+ + +
T
k=T041
T t-- + E + ((1))
(1/t)
Σ
Lx |W - w01 + || - w0ll || + -1
k=70+1
Tp
TV k-1 + + 66- )
(1/0) Σ
2 KM k- ( + + 6x-1) LK-1
k-70+1
s 2(111)
Σ Le(MM + -ee
T
+ + +tx-11
1 I-1
k=1+41
TP + KT, (2)
2Le(KMM Le)
Vt
2Lg(KM Le)
+ + KT,, (2)
T(1-3p)/2
4L + LE)5.
Bounding Ri. Finally, for the last term we get for 2 A) we have |Ral S
2L2//1
S
2Le/T S 2 /T (1-33/ & 2
Last step. Summing up all terms yields that for t 2 T2-P, max (Ty(S:));
1
we
g0- $ sT-p-
have
E (Eins f(E)) - w(( 2 ( Eama(A) $2exp(-
P
(29)
where Kg = 1 + 26a + 4Lç(1 + KM + Lg).
As corollary of the previous proposition, we find the following concentration result on Ne(s, and the high probability event (5) = nT- (1 -w"l $ KçE).
Corollary C.3. For MR-NaS we have
N((s.a) wn (s,aa 2 neE (ar(()r()))) n Ecai(2) (2) s 2SA exp(txxt)tt")
P a) Z, and
(30)
25 A exp(- exp(-
IP C.. (E) (5) n Ecme(A)
(31)
1 exp(-82)
C.3.5 Expected sample complexity of MR-NaS
Finally, we have the expected sample complexity upper bound of MR-NaS, which closely follows the classical proofs in [17, 20].
Proof strategy. To summarize, the proof strategy relies on ensuring that N2 a)/t concentrates around w/ (s, To that aim, the concentration happens under some events (E) (defined in lem. C.4) given that Ne(s, a) is visited sufficiently often (see lem. C.3, the alternative version in lem. C.5). As 8 + 0, by the properties (N,, 8), one can show that that B/r]/ In(1/8) does not exceed supar' Pates (M) [M)lll"""w "ll''w""[[l<""" Kgg U(w', M3) In(1/)), where Bp(e) (M) is ball of certain radius p(E) around M (see def. of p(E) in app. C.3.3) and Kg > for all g > 0. Hence, letting
f + 0 concludes the proof.
46

---

max A), (2)5), Ta(E, (E) Theorem C.2 (Expected sample complexity). MR-NoS with the stopping rule in prop. 3.1 guarantees E(r]
that B and lim sup5-10 log(1/8) (M).
Proof. Define
UE(E)
sup
U').
Mie (d00), I>x [I
Similarly to [17], by prop. C.3 under (5) (defined in lem. C.4) the event (f) (defined in
corollary C.3) holds with high probability, and there exists Ti A) such that for T 2 T(E, A) have U(N/ft,M, I (E) for all f > T'-
Further, by the properties of the threshold function ((N,, 6), there exists (T( such that for t 2 T2(E) we have ((N,,)) 5) < log(1/6) + (U)(E)) Then, let Ts(5,5) be such that log (E) (E)- 6) = T5 ō), that is
TE 0) U (E)
1-8
Hence, under (5) n (5)(() for T 2 max(TH T3()), it holds that TU (Nr/T, M,) 2 (NN,, 8), and thus (T s T) 2 ()) n (g,,(()))))))) (E)) Therefore, using that E[r] Σr= P(r T) can show?
E[r] < max (2,) T)) +
g3 P.r (5) U Ep)r(())
T==ax (Ti
(E) T2(),, TT
Σ
CT exp( (T), (A)p)
T
T'max (Tanaax(Tiinne (1
25A expl 1SAAexp(TTi-p"
exp( (E2)
and thus [[r] is finite since (T, (A) grows as 7 for a fixed X. Hence
[[T] log(1/8)
limsup sup
S lim sup
8-+0
6-+0
11g(1/5)
1 1-
Letting& g - 0 concludes the proof.
C.3.6 Alternative forced exploration with high probability
In this section we introduce an alternative result for the forced exploration property with high probability that follows the one proposed [17]. In addition to the quantities defined app. C.3, we also define 77 7m7 and m max
m,
2(a+))
The following lemma an alternative to lem. C.3, and it is adaptation of [17, Lemma 11]. Using this lemma, one can obtain sample complexity upper bound in expectation as in Alg. 2. For the sake of simplicity, we only state the main steps of the proof that differ from the one in [17].
Lemma C.5 (High probability forced exploration). For all X E (0, 1) we have
1/4
P
Vz 2, 2,
>
-
21-1,
(32)
9(A)²
where g(A) = 1h log (1 + S and m max (m,
Proof. Denote by (2) the k-th time agent visit state-action pair = (s,a), and define the
event & = (Vz E Z, vk 2 1, Tx(2)= < fkk) for some increasing function f N + N. satisfying f(0) = 0. One can find that
((b) ((0)
P(E)= < SA
bk
by
II i=0
(7(k - my + 1)a+8
For simplicity consider max(Ti (2(5), 6)) integer.
47

---

For s(k) = Akd we have
f(k)- 1)
AA and
1(6) ((k-))
m
1
b6
(f(k - 1) my + 1)at8
[(k) 11-
1
f(k)a+8
1500
11 f(k)maatt)
24
17
f(k)m(o++))
S exp
(-1
263
Now, since 2(++8)
S m, then we have that m(a + B) 2 1/2, thus by S exx
exp (- nkvA Hence
m
1
exp
bk
nv/A m
A=
exp
Finally, the conclusion follows similarly as in [17].
The previous result relies the following close adaptation of [17, Lemma 20). Again, only show the main steps of the proof.
Lemma C.6. Fix za Z, and let P. be the transition induced by the sampling policy n. of MR-NaS. Define the sub-stochastic matrix Qs obtained by removing from Pe the row and the column corresponding to zg:
Q₂
[P((2ol2))=>
[P((2 bn) 24200
Pr 20)
Then, we have
n+m
n+m
Vn 2 1,
II Qk k=n+1
< 1
II kmn+1
(33)
ka+B
Proof. Define (n 122) = ΣSA-1 (II Q1) to be the sum of the k-th row of the
product of matrices Qi for E {ni + ,,..., and observe that | Qi = (A-., ri(n, m).
Since the MDP is communicating, there exists = E Z s.t. (z(==)=) 2 m and k* the corresponding row of in Q.. Then, using lem. C.I and the fact that = 1/ max(1, (s))) for
n1 2 1 we have P. 2 N. 2 m/ta09, and thus
P.
SA-1
Tk- TT-(11 21 + 1) =
Σ (Qn = Pa Po)+i(2olz) S m (mn + 1)0+8
For n1, n2 2 1. by recursion
show that
SA
mi t
Tk- Tk- (11 01 + 122)
Σ
II
Smx-(m1, +1) $1 - " (n, + 1)048.
1
1=n++1
48

---

Similarly, for any E {I..... SA} \ {k*}, J, for all
we have
ri(n,
m) Σ
II
Qi
ry(n + n1, m),
j=1
1=++1
if
n+
1
II Qi
S m
(n +
ny + 1)at
Mmn+1
ik
To bound the last term, observe that for n4 S m
n+n; II Q
12+
II
Ni(s)
Pu
2 1mm
Vmn+1
Imn+1
1mn+1
Therefore
re + m)
1 7/ mm
|a+B:
[=++1
which concludes the proof.
C.4
Stopping Rule
Next, we provide the proof of the 5-PC property of MR-NaS. Note that a necessary condition for the algorithm to stop is that the model at the stopping time M, needs have a unique optimal policy for every r E R. Given this condition, we have the following proof of the stopping rule.
Proof of prop. 3.1. Let {ār R म., & (T, be the event that at the stopping time there exists reward such that the estimated optimal policy is not optimal.
Let Alt(M) = U,Allt(M,). Then, since M, E M,, admitting single optimal policy for all r E R. we can say that C C (3r E R : M E Alt(Me,r)) C U.(M Al)(M,,)) C {M e All(M.)) where M = (Me r). Then
P (To < C) < P 3t 2 1: (N,
((N,,)), E Alt(Mo)) 31 1: (NN 2 B(N,, E All(Mi)),
< P
P
3t 2 1: inf inf M.EAl((Me.))
Σ
Ni(s..)KLMIM 2 3(N,,),, M Al((M))
Σ [i( 2 8), M AH(M))
P
3t B211 1:
inf AM(M,))
Nols, (ds B(N.0))
< P
1:
8,0
88,
where the conclusion follows from [86, Prop. 1].
C.5 Technical Lemmas
We have the following adaptation of [87, Lemma F.4).
Lemma C.7. Let YI..., Y, be sequence of Bernoulli random variables. Let F; be filtration, and for i= L and m N let X, 1 1y mm be a sequence of Bernoulli random variables such that Q; = F-X, F -measuraaee and X₃ is F,-measurabl. Then, for A we have that
X,
<
Qi - Se-d
(34)
i=1
1=1
49

---

Finally, we report the following proposition from [86, 17] that bounds the self- normaaozdl KL process.
Proposition C.4 (Prop. 1, [86] and Lemma 15 [17]). Define the threshold 3(Ne, 8) = log(110) -
(S 1) log
) Then, for all 8 E (0, 1) we have + S N
P 1
Σ
Ni(s, (Kl..))KL B(N())) 2.,
(35)
8.0
with the convention that (s, a a (s, a) 0 whenever N1(8,,) =0.
50

---

D Numerical Results
In this section we present more in detail the numerical results for the tabular case and for Deep Reinforcement Learning. We also introduce additional numerical results radio network control problems.
D.1 Numerical Results for the tabular case
In this section we delve more into the detail of the numerical results for the tabular case. We focus on different hard-exploration tabular environments: Riverswim [54], Forked Riverswim [53], DoubleChain [22] and NArms [54] (an adaptation of SixArms to N arms). We compare MR-NaS against RF-UCRL [22] (a reward-free exploration method), ID3AL [33] (a maximum entropy exploration approach) and RF RF-PSRL, reward-free adaptation of PSRL [35] (posterior sampling for RL). As the baselines are not specific to our setting, we consider different sets of experiments.
We begin by describing the environments, and then present the results.
D.1.1 Environments Details
Here we provide brief description of the environments.
Riverswim. The RiverSwim environment is classic reinforcement learning benchmark designed to test exploration [54]. It consists of a series states arranged in linear chain, where an agent choose swim right (downstream) or left (upstream). In the single-reward setting the agent can achieve a positive return by swimming right, but requires overcoming strong current, making it a less probable event. Conversely, swimming left generally offers small to rewards, but is easier. This setup requires the agent to balance immediate, safer rewards with potentially higher but riskier returns. It is exponentially hard for a random uniform agent reach the final state.
In figure fig. 3 shown a depiction the environment. There are n states, and two main parameters, p.p' E (0, 1), and their Psum p + p' < 1. In the figure, each tuple (a, p) represents the action a that triggers the transition and the probability p of that event. The agent starts in state Su, and in every state can only take two actions {ap, }1}. For small values of p it becomes difficult for the agent to swim right (i.e., reach 1n and larger values p' can also hinder the progress. On the other hand, swimming towards the left easier, since the probability of P(si- 40) 1. For the experiments, we used n = 10, 0.3, p' = 0.6.
(co, (a1. p)
(a),p')
(a1.
(aa. 1), (a..p)
(a1.p)
(a).p)
(01.P)
(a1, p)
80
82
Sn-
Sp-1
(ap. 1), (a1. Poum)
(ap, 1), (a1. Doum) (ag. (0,,
Poum)
(oo 1), (ar, p)
Figure 3: Riverswim environment [54]. Each tuple (a,p) represents the action a that triggers the transition and the probability of that event.
Forked Riverswim. The Forked RiverSwim environment [53] a variation of the traditional RiverSwim reinforcement learning benchmark, designed to test more complex exploration strategies. In this variant, the state space branches into multiple paths, resembling a river that forks. At intermediate states the agent can switch between the forks, while the end states are not connected. This variant requires the agent to make more sophisticated decisions to explore the environment. This setup increases the sample complexity and challenges the agent's ability to generalize across different paths within the environment.
In fig. 4 is shown depiction of the environment, There are total of 2n++1 states, and two parameters p.p' (0,1), 1), so that Psum = p + p' < 1. In the figure, each tuple (a, represents the action that triggers the transition and the probability of that event. The agent starts in state so, and in
51

---

every state can chose between three actions {av, a1, 02). For small values of it becomes difficult for the agent to swim right in both forks, and larger values of p' can also hinder the progress. As in Riverswim, swimming towards the left is easier, since the probability of P(s;- (0) = 1. For the experiments, we used n 4, p = 0.3, p' 0.6.
(oo, 1), (oL, - p). (uz, 1)
(ar-p")
(a1.p')
(a1.p')
(al, p), (uz, 1)
(a1.p)
(ai.p)
(aI.p)
80
82
Sn-1
8n
(ap, 1), (a),
Peam
(ae, (a),
Poum
(ao, 1), (a,,
(o2.1) 1)
(a2.1)
(az,
(az: 1)
(os,
(as.1)
(op, 1)
(ar.1
Peum)
(ai.p)
(ai.p) p)
$/2
8
S'
(ag: 13 ponm)
(0o. 1), (or.1 p)
(ai.1
('1:p")
(OL.D))
(ai.p")
(a.. (02.
Figure 4: Forked Riverswim environment [53]. Each tuple (a.p) p) represents the action that triggers the transition and the probability of that event.
Double Chain. The Double Chain environment [22] consists of two chains, similarly to the Forked Riverswim. The main difference consists in the fact that it is not possible to switch between the two chains, and intermediate states are transient (there no parameter p').
In fig. is shown a depiction of the environment. There are a total of 2n 1 states, and one parameters p E (0, 1). In the figure, each tuple (a, p) represents the action a that triggers the transition and the probability of that event. The agent starts in state sg. and in every state can chose between two actions {ao, a.). For small values of p it becomes difficult for the agent to move the end of the chain in both chains. For the experiments, we used = 6, 0.7.
{uy p)
(a1, p)
(ar.p)
(as, p)
8n-1
8m
(0g. 1)
1.0 1)
(ao, p)
(ao. 1). (ar, p)
(oo. 1), (e11 p)
(a1. p)
90
(1
(a1.p)
(a1,p)
(01.
(ag. 1)
(a1.1 1 11--0 n))
S'
(ap. 1), (m1,
(0o. (as,1-
(ao. 1), (as, 1 p)
(#1.p)
Figure 5: Double Chain environment [22]. Each tuple (a.p) represents the action a that triggers the transition and the probability p of that event.
52

---

NArms. This environment is an adaptation to N arms of the original 6Arms environment from [54]. Differently from the previous environments, this bandit-like environment, where the agent is presented with n different actions (or arms) to choose from. 'he agent starts in a state 8o and selects an arm 0;- Upon selecting an arm, the agent may transition to corresponding state 8,. Certain arms are more difficult to observe, in the sense that the transition probability is lower. This property mimics the probability of collecting a reward a bandit problem.
In fig. 6 is shown depiction of the environment. There are total of n 1 states, and one parameters Po (0, 1). In the figure, each tuple (a.p) p) represents the action that triggers the transition and the probability p of that event. The notation +n indicates all the actions in {Ang....... tn
The agent starts in state So, and in every state she select between actions fao, a1...... an-1) } For small values of Po it becomes difficult for the agent to move to different states. Similarly, is harder to navigate states 8; for large values of n. We used po 1 and = 4.
(Rom 2. 1)
(ao. 1)
Sn
(an-1,
(aros, 1)
$1
(oc, po/(# + 1))
C0n-1.1)
1o0 1)
(an 2: s.po/(n 11)
so
(a2..1 1)
8n-1
(un-2mn 1)
(a1. Po/2)
82
(Ro:n-3,1)
(00.1.
Figure 6: NArms environment. Each tuple (a, p) represents the action a that triggers the transition and the probability p of that event. In the figure the notation Onomatn indicates all the actions in {amp..... anotn). state sy the probability to remain in sy for any action a, is P(su (a));)))) = 1 - po/(i + 1), with the exception that P(su Su, au) = 0.
D.1.2 Numerical Results
For the numerical results in the tabular case, we focus on different aspects of the problem: (1) policy estimation error; (2) value estimation error; (3) exploration properties.
For the first two aspects also consider the capacity of MR-NaS to generalize over rewards that do not belong to R, specifically:
TR-NaS uses the canonical basis of rewards Reanonical to compute the allocation w and explore the environments. We also use = 0.99, 3 = 0.01.
We also test the generalization capacity of MR- RR-NaS over continuous set of rewards. At each time step we collect 30 additional rewards from Read (RI..... R,0) which is set of 30 reward vectors uniformly sampled from [0, 1JAA, different for each seed. Note that these vectors are not used by MR-NaS to drive its exploration 8
We consider discount factor of y 0.9, confidence 5 = 10-2 and run each algorithm for T = 5- 10 steps. In all experiments we depict the average value and its 95% confidence interval over 100 seeds.
MR-PSRL algorithm and RF-UCRL. MR-PSRL simple adaptation of PSRL (posterior sampling for RL [35]). PSRL is an episodic algorithm that draws an MDP estimate from posterior distribution. We adapt PSRL by sampling at the beginning of an episode a random reward vector [0, 1
SSince use the canonical basis the second assumption (CH) in thm. B.3 is satisfied.
53

---

and exploring according to Mr for that episode. In our case. we simply draw ~ Dir(1) from Dirichlet distribution, where is vector of ones of size SA. Since we do consider finite horizon setting, and both RF-UCRL and RF- RF-PSRL are episodic algorithms, we set an horizon H = 1/(1 - 7).
Policy estimation error. We report in fig. 7 the estimation error of the optimal policies. In the plots we depict the average value of εt,- [11' (MI))) TII (MM,,. for a reward r", where AAB the symmetric difference between two sets A, B. Intuitively, et accounts for both policies that are not accurately estimated and policies that are optimal in Mar but not in M,.
MR-Na5
RF-UCRL
ID3AL
MR-PSRL
Riverswim
RiveeeRiverswin
DoubleChain
NArms
100%
Estimation esror Eje]
80%
60%
40%
0%
0
200000
40000
200000 Steps
40000
20030 Steps
40000
0
200000
40000
Stepe
Steps
Estimation error the canonical basis
MI NaS
RF UCRL
JDSAL
MR PSRL
Riverswim
ForkedRiivrswim
DoubleCbain
NArms
100%
60%
10%
30%6
0%
20000 Slapa
40000
2000 Stapa
20000
20000 Stepa
40000
20000 Steje
40000
Estinationn over random zewards
MR-Na8
RF-DCRI.
IDSAL
MR-PSRL
Riverswim
ForkedRiverswin
DoubleChsin
NArms
100%
5055
40%
20%
0%
0
20000
40000
0
20000
40000
20003
40000
20000
40093
Steps
Staps
Staps
Stapp
Figure Estimation error of the optimal policies. The plots depict the average value of Ct,r IT' (MT))ATT (r is random quantity) and its 95% confidence interval. In the first plot combine together the results for the canonical basis Reanonical and the random rewards Rynd- In the second plot we only consider the canonical basis of rewards R Reauonicals whilst in the third plot we only consider the random rewards Rynd-
(.M.)JUII(MM...)
In the expectation the reward is random variable.
54

---

In the first plot we combine together the results for the canonical basis Reanonical and the random rewards Rmd In the second plot we only consider the canonical basis of rewards canonical- whilst in the third plot we only consider the random rewards Rynd. When consider only the canonical basis the advantage of MR-NaS more noticeable, especially the Riverswim and NArms environments (observe that for Forked Riverswim to bring the estimation error to 0 requires far greater number of samples since the environment is more difficult and the canonical basis is larger).
We also see from the last plot, the estimation error over random rewards, that MR-NaS is able to identify the correct optimal policies over rewards uniformly sampled form [0, 1]
Value estimation error. We report in fig. 8 the value estimation error over different rewards. In the plots we depict the average value
V1,ll1 where the reward r is a random variable when 5
accounting for the random rewards in Rndd
From the results we observe the good performance MR-NaS, despite the fact that the objective of MR-NaS is not optimize the value estimation error.
Exploration properties. this paragraph we go more into the details of the exploration properties of the various algorithms. In partieular, focus three different metrics.
1. The deviation in visitation time, defined as Avisit, = max,' tvisit (s') -min, tvisit (sist(s).. where (visi(()) is the time step the algorithm last visited state This metric Avisit, quantifies how much an algorithms favours visitation of some states compared to others. In fig. 9 we show the results. We see that the initial transient of MR-NaS is relatively quick, and then converge to some steady-state value. While MR-NaS tends to focus on some states, it also manages to keep visiting all the other states, keeping the deviation to a small value.
2.
The least visited state-action pair mins,a (1,s, a). This metric particularly important since it is proxy value for the value estimation error and the policy estimation error. The top figure in fig. show this metric. Also in this case we see fast initial transient for MR-NaS.
3. The last metric we consider is the entropy of the number of state-action visits H(N)), defined as
H(N.) = - (r(s log(ps(s, a)); where (x a) a)(s,a)
8.0
This metric intuitively quantifies how spread the exploration across the state-action space. The bottom figure in fig. 10 shows this metric normalized in [0, 1]. Larger values indicate that the exploration is more uniform across the state-action space.
Compute resources and additional information. For these simulations we used I G5. 65.4XLARGE AWS instance with 16 vCPUs, 64 GiB of memory and A10G GPU with 24 GiB of memory. To obtain all the results 2-3 days are needed. The entire research project needed roughly 15 days of computation time for this experiment.
We set up our experiments using Python 3.11 1 [88] (for more information, please refer to the following link http:/ //ww://wwwww python. org), and made use of the following libraries: NumPy [89]. SciPy [90], CVXPY [91]. Seaborn [92], Pandas [93], Matplotlib [94]. In CVXPY we used the CLARABEL optimizer [95] and/or the ECOS optimizer [96]. Changes, and new code, are published under the MIT license. To run the code, please, read the attached README file for instructions.
D.2 Numerical Results: Cartpole swing-up and DeepSea problems
In this section we discuss the numerical results on the Cartpole swing-up problem and the DeepSea problem.
Libraries used in the experiments. We set up our experiments using Python 3. [88] (For more information, please refer to the following link http: //www//www..w.w python. org), and made use of the following libraries: Cython [97], NumPy [89], SciPy [90], PyTorc [98], Seaborn [92], Pandas [93], Matplotlib [94]. Changes, and new code, published under the MIT license. To run the code,
55

---

MRS
RE-UCRI.
ID3AL
MR-PSRI.
Riverswim
ForkedRiverswin
DoubleChain
NArms
Value astor E I Vullsss
1.0
0.5
0.0
20000
10000
0
20000
10000
20000
10000
20000
40000
Steps
Steps
Stops
Value error over the canonical basis
MRt-N8
RE-UCRI.
MR-PSRI
Rivenswim
Fivererii
DoubleChain
NArms
2.0
B0M
1.0
0.0
Steps
Stops
Steps
Stogs
Value erzor random rewards
UCRL
Riverswim
ForkedRiverswin
DoubleChain
NArms
0.20
0.10
0.00
20000
40000
40000
Stope
Stqps
Stops
Staps
Figure 8: Value estimation error. The plots depict the average value E
|| V. 1l S
In the first
plot we combine together the results for the canonical basis Resnonical and the random rewards Ryad- In the second plot we only consider the canonical basis of rewards Reanonical, whilst in the third plot we only consider the random rewards Rynd-
please, read the attached README file for instructions. the code, we make use of some code from the Behavior suite [36], which is licensed with the APACHE 2.0 license.
D.2.1 Cartpole swing-up
Environment details. The cartpole swing-up problem is well-known challenge in control theory and reinforcement learning [99]. The objective is to balance pole attached to cart by unactuated joint, where the cart moves along a frictionless track. Control is exerted by applying force to cart. Initially, the pole hangs downward, and the goal is to swing it up into upright position and maintain its balance there. Unlike the traditional cartpole balancing problem, this task requires both swinging the pole up and keeping balanced once upright.
56

---

MR-Na8
RF-UCRI
ID3AL
MR-PSRI.
Riverswim
ForkedRiverswin
DoubleChain
NArms
101
101
10
10
E [Avand
10a
10
10a
10a
WW
10a
40000
20000
20000
Steps
Strps
Steps
Stops
Figure 9: Average value of Avisit, maxs' Evisit (s') min, ( (s), where Evisie (8) is the time step the algorithm last visited state 8.
MR-NaS
RF-UCRL
ID8AL
MR-PSRL
Riverswim
ForkedRivesswin
DoubleChain
NArms
109
10P
108
10
101
10P
10P
10
10-1
10
40000
40000
Steps
Steps
Steps
Steps
9006
80%
90%
8076
60%
70%
70%
009%
415
60%
60/56
20%
20%
50%
30%
40000
20000
40000
20000
Steps
Steps
Steps
Steps
Figure 10: Top: average value of the least visited actton pair min Nr(s, a). Bottom: normal- ized average value of the entropy of N, over time (see text for definition).
Goal position
Cart
0.0 0
Pole
Figure 11: Diagram of the Cartpole swing-un up problem.
57

---

The system's state at any given moment is defined by four variables: the cart's position the cart's s velocity é. the pole's angle 6, and the pole's angular velocity 0. There are also four additional variables in the state, and for brevity, we direct the reader to [36].
This problem is challenging because the reward is sparse and includes a penalty for movement.
Reward functions. In the multi-reward variant the objective is to stabilize the pole vertically around a specified position zo. The agent receives a positive reward only the following conditions are met: (1) cos c0) > k/ for the pole's 's angle, (2) [6] S Bu for its angular velocity, and (3) |xc - - 1 - k/20 20 for the cart's 's position, where Og is constant and l is an integer indicating the difficulty level. Additionally, the agent incurs negative reward of -0.1 for moving, which hinders the learning process, Classical algorithms like DQN [100] tend to remain stationary due to this penalty,
Then, the reward at time for given value of 2gg is:
Tao (8t, 0z) = -0.1+ + (Ioa0(1)2A/200 16.1 10:-
We considered set of rewards Rhase (Tag Z that consists of rewards for different values for To. where To is evenly spaced in [-1.5, 1.5] (that is X' (-1.5, -0.75, 0, 0,0.75, 1)). To evaluate DBMR-BPI'S BPI's ability set Rynd. which consists of reward functions where, for each reward, zo is uniformly sampled in [-1.5, 1.5]. The set Rynd different for each seed, and observe that the random rewards in Ryad were not used during training of DBMR-BPI.
generalize unseen rewards, we also evaluate the rewards collected in the
Numerical results: performance. In figs. 12 and 13 we depict the performance of the various algorithms over Rass and Rand for two difficulty levels k E {3, 5]. tabs. and we report the values at the last time step T of the various metrics considered.
In partieular, we focus on the distribution of the following random variable
X,
11)30
T
where i the i-th reward in the corresponding set of rewards. This metric measures the average amount of information collected by the agent useful to learn how stabilize the pole upright. In the figures, and in the tables, the quantity Avgæ ((X,)) (sim. the others metrics) indicates the arithmetic mean of {x over the rewards. We average results across 30 seeds.
Base rewards E[stdg
E[medg(X.)
E' (X,)
E[maxx
Ejming (X,)
A = 3
DBMR-BPI
21.8(20.9,22) 22.77
21.3/20.6, 21.9)
6.1(5.5,6.6)
28.9(27.6, 30.2)
12.8(12.0, 13.6)
150000
RND
1.3(1.0, 1.7)
1.3(1.0, 1.6)
0.3(0.2, 0.3)
1.7(1.3, 2.1)
0.9(0.7, 1.2)
APT
0.3
0.3(0.3. 0.4)
0.1
0.5 0.6)
0.2(0.1,0.2)
Di Disagroement
0.9[0.7, 1.2)
0.9 1.2)
0.3(0.2, 0.6)
1.3(0.9,
0.5
k == 5
DEMR-BPP BPI
21.6(20.9, 22.3)
20.2(19.6, 20.6)
6.4(6.0, 6.9)
28.0(27.0, 29.0)
11.4(10.7, 12.0)
T = 200000
RND
1.2(0.9, 1.4)
1.2(0.9. 1.5)
0.2(0.2, 0.3)
1.5(1.2, 1.9)
0.8(U.6, 1.1)
APT
0.3 0.4)
0.3 0.4)
0.11
0.5(0.4,
0.2 0.2)
Diaagreement
0.7
0.7 1.0)
0.3(0.2,0.4)
(.2
0.4 0.6]
Table 4: Cartpole swing-up. Statistics for the random variable X, + DT_ (. with E Roase- Values are multiplied by 100 and rounded to the first digit. In bold statistically significant results (in parentheses we indicate the 95% confidence interval).
In general, we see that DBMR-BPI outperforms all of the unsupervised learning baselines. Interestingly, even though DBMR-BPI uses the base set of rewards Rbase to explore, we see better performance when collecting rewards from Ryna (which are not used by DBMR-BP1 BPI during exploration). The reason may be that some rewards in Roases (e.g., those with (rol = 1.5), are harder to learn, while it unlikely for the random rewards to have such values of xp. This result seems to suggest that the data collected by DBMR DBMR-BPI could also be used for rewards that are similar to those in R.
58

---

Statisties for the base rewards Ruase A ==3
3
DRMR-BPI
RND
Disegrommet
APT
EfmeedXX.d
E1std
Elmmax X1,l
Elming Xyx
20
30
20
10
10
10
2
10
100000
0
100000
100000
100000
100000 Timestep
Timestep
Timestep
Timestep
Timustep
Statisties for the base rewards Riss A
5
DEMR-BPI
RND
Disagroement
APT
E[Ang X.c]
Efmax, X.dl
Erring Xxy]
10
4
10
200000
200000
200000
200000
200000
Timestep
Timestep
Timestep
Timestep
Timestep
Figure 12: Cartpole swing-up. Statistics for the random variable X; T3ss E R.ase- Values are multiplied by 100 and rounded to the first digit.
T Σi= 1 ( with
Statistics for the base rewards Riss A = 3
DEMR-BPI
RND
Disagrocment
APT
EfmeedXX..]
Xly
Xyy
Eluuax, X..]
Elmin, X..]
30
20
20
20
10
10
10
10
0
100000
100000
100000
100000
100000 Timrstep
Timestep 1
Timmotteg
Timostop
Timestop
Statisties for the base rewards Russe k
5
DBMR BPI
RND
Dasagreemen
APT
D E/med,X... X
E Xul
X.s
Elmax, X..]
Efmin, X
20
15
10
10
2
10
0
100000
200000
100000
200000
100000 Timesttop
Timestep 1
Timostop (
Timestep 2
Timestop
Figure 13: Cartpole swing-up. Statistics for the random variable X; 1/4 ET 1 (r, with T; E Rynd- Values are multiplied by 100 and rounded to the first digit.
Numerical results: rewards chosen by DBMR-BPI. In fig. 14 we plot the value of A.. estimated from DBMR-BPI We see that according to the algorithm the third reward, which corresponds to To = O, is initially the easiest to learn. This fact is also depicted in fig. 15, which shows the number of time a certain reward was picked by DBMR-BPI for exploration (the plot does not account the uniform exploration over rewards, or the tracking procedure that ensures each rewards is selected at rate O( O(yn), where n is the number of episodes). Rewards corresponding to Janp = 1.5 are harder to learn since the episode terminates if the agent exceeds the boundary of the environment.
59

---

Random rewards Rydd
Elmede.... (X,))
R[Avge.... [X.]
Estde..... (X.]]
Kmmax (X,)
E/mine.... (x,]
==3
DECR-BPI
23. 23.7,22.5,244 24.9) 24.9)
23.1(22.2,2122
1.(336, 1.6)
28. 22.1( 29.3)
17.1(16.0, 18.2)
150000
1.7)
1.4(1.11.77)
0.2(0.1.0.2)
1.6[ 2.0)
1.1 1.4)
APT
0.4)
0.3
0.1(0.1.0.11
0.5
0.2(0.2,0.2
Disagreement
1.1(0.7,
1.0(0.7,
03((0.10.5)
1.3(0.8, 2.0)
0.6(0.5, 0.7)
DEKR-BPI
23.0(21.8, 21.11)
22,3(21.5,
23.1)
4.5(1.0.1.)
27.6(26.7, (..(66.7.88.)
15.3(1444 16.7)
7'
200000
RND
1.1(0.9, 1.4)
1.1(0.9.14)
0.2(0.1.0.2)
1.4(1111.7)
0.9(0.7, 1.1)
APT
0.3(0.3,
0.4))
0.1(0.1.0.1)
0,4
0.2(0.2, 0.3) 0.5 0.7)
Disagreement
0.7(0.5.0.9)
0.8(0.5. 1.0)
0.2(0.1.0.3)
1.0(0.7.1.4) 1.4)
Table 5: Cartpole swing-up. Statistics for the random variable X; = ri E Rynd- Values multiplied by 100 and rounded the first digit. bold statistically significant results (in parentheses we indicate the 95% confidence interval).
T Σ a)) with
Estimation of A,, for DBNR-BPI &
Reward
0.03
3 0.02
0.00
20000
40000
80000
100000
1400000
Timsolage
Estimation of A,, For DRMR-BP
Reward X
0.03
0.02
0.00
25000
50000
73003
100000
125000
150000
175000
200000
Timoolep
Figure 14: Estimate A., of DBMR-BP BPI over time steps. The i-th reward corresponds to the i-th reward in Rease. Shaded area corresponds to the 95% confidence interval over 30 seeds.
Nummber wowards chreen DANR-RPT up timestop 7(p
Number rowards chreen DANR-BPT timestop ( 5)
30
60
30
Reword
Reward kt
Figure 15: Distribution of the number times a certain reward r; was picked by DBMR-BPI up to time step T'. The i-th reward corresponds to the i-th reward in Rosse The plot does not account for rewards chosen uniformly at random or due to forced tracking.
Parameters and compute resources. For these simulations we used G5.4XLARGE AWS instance with 16 vCPUs, 64 GiB of memory and A 10G GPU with 24 GiB of memory. To obtain all the results 3-4 days are needed. The entire research project needed roughly days of computation time for this experiment.
60

---

The parameters are listed in tab. 6. Refer to app. E for further details on the parameters and the algorithms.
3BM2-BP1 BPI parameteers
Value
API parameters
Value 1128, 128]
Disagreenent parameters
Value
RED parameters
Value
20
Nayn
[128,
Veturted
128 128)
2-10"
2-10"
2-10"
l0
10
16
10
(6 1.5 10
10
5.10
10 -4
PaniJorm
0155
NeveriVee
Neep
612
Plrock
0.7
Merunk
112
Nelinn
Mond
128
2
125
11
10
Spedor
2- 2-10"
Goyd
10
12
Table 6: Parameters and values of the algorithms. For all algorithms used batch size of 128.
61

---

D.2.2 DeepSea
Environment details. The DeepSea problem is a hard- explorrtpoooii reinforcement learning challenge set in N N grid. The agent starts in the top-left corner (state (0. 0)) and, the classical version, aims to reach the bottom-right corner (state (N 1, N 1)) for large reward. The state vector is an Ni-dimeesional vector that one-hot encodes the agent's 's position in the grid. The agent can move diagonally, left right, and down when near the wall. Reaching the bottom-right corner yields reward of We also incorporate slipping, as described in [53], so that when the agent selects an action there is 5% probability that a different action a' o a is executed instead. Lastly, for each seed, in each state the action mapping is randomized (so that in two different states an action a can correspond to go left in the first state, and go right in the second state).
$,0,00
#60.13
*(1.1)
910,23
4(1.))
4(2.2)
$(0.5)
S(1.))
((2,3)
$33.33
Figure Depiction of the Deepsea problem as tabular MDP with
Reward functions. We adapt the DeepSea environment to multi-reward setting by introducing N different rewards, Rbase {[r--- .NN.. where r; assigns a positive reward whenever the agent reaches column i in the last row of the grid, that is:
r: ri(St, az) 1N
To evaluate the capability of DBMR-BP BPI I in collecting unseen rewards, we sampled 20 reward functions Rrnd (r for each seed. Each reward function is essentially vector of dimension N (N 1)/2, corresponding to the possible positions in the grid, and sampled from Dirichlet distribution with parameter (a:)., where a; 1/(10N) for all i 1, (NV + 1)/2.
When the agent is in state s, corresponding to row k, column j. collects the corresponding reward (ra)5.t from the reward function ry. We then computed the rewards for these additional reward functions assess performance. Note that these rewards are not used by DBMR-BPI during training.
Numerical results: performance. In figs. 17 and 18 we depict the performance of the various algorithms over Resse and Rynd for sizes N {20,30) ). In tabs. and 8 we report the values the last time step T' of the various metrics considered.
In partieular, focus the distribution of the following random variable
X;
T Σ ri(se, at),
where i the i-th reward in the corresponding set of rewards. This metric measures the average reward collected for the i-th reward in a specific instance.
62

---

In the figures, and in the tables, the quantity Avgr ((X,)) (sim. the others metrics) indicates the arithmetic mean of {X;;; over the rewards, while GMR([[)) (())) indicates the geometric mean over the rewards. We average results across 30 seeds.
DBMR-HPI
RND
Disagreement
APT
Elmed,Xax
X
max; Xi,e]
El min, X
E B 1x,==
60
20
10
40
2.0
15
3
1.5
10
20
1.
0.0
0
2000
2000
2000
2000
2000
2000
Episades
Episodes
Episodes
Episodes
Episudes
Episodes
DBMR BPI
RND
Disugreement
APT
Efmed,
Elstd; X
E max; X
El Emmin, X
B 1x,x-o)
10
50
1.25
30
40
1.00
20
30
0.75
20
0.50
10
10
25
0.00
2000 Rpisodes
2000 Episodes
2000 Episodes
2000
2000 Episndes
Episodes
Episodes
Figure 17: DeepSea environment. Statistics for the random variable X, + re( uz) (with E Raase). Values are multipled by 100 and rounded to the first digit (except for the last plot). Shaded areas depict 95% confidence intervals.
Base rewards Ruse
(imedg(X))
E|stdg
Eimaxg(X.)
Ejuing (X+)l
E|Y, 1 x
D8MR-3PI
5.0(4.9.6.1)
4.6(4.6,
18(17,
7.9.7.88800
1.7(166 1.8)
0.0(0.0, 0.0)
T" 50000
RND APT
4.8/4.7.4.0 4.9)
4.6/4.2, 4.7)
1.7(166 1.8)
8.9/8-5,92)
2.6
0.0(0.0, 0.1
3.3(3.0.36)
1.40.8, 1.9)
5.3(4.8.58)
19.7(17.7,21.9)
0.2(0.1.0.2)
0.9(0.6, 1.3)
Diesgreenent
1.7(1.4.2.1)
0.0(0.0, 0.00
6.2((.9.6.5)
20.4(18.7,2225
0.0(0.0. 0.0)
1.0(34,,
DPM
3.5(3.4.355)
3.1(2.9.32)
0.7
1.4(3.11)
1.1(10, 1.3)
T T 100000
RND
3.1(3.0.3.)
18 2.2)
1.9 2.0)
8,1.7.7,8.5)
0.3(0.2, 0.4)
0.3(0.2, 0.5)
2,0(18,22))
0.0(0.0.00
3.9(3.6.
16.0(11.5, 17.6)
0.000.0, 0.0)
3.3(2.8. 3.8)
Disagreenent
0.2(0.1.0.2)
0.0(0.0.000) 0.03
7.0 7.3)
27.3(26.1, 29.6)
0.0(0.0, 0.0)
11.5(10.8. 12.2)
Table 7: DeepSea environment. Statistics for the random variable X; T Er (i az) (with rs E R.ase). Values are multipled by 100 and rounded to the first digit. In parentheses we indicate the 95% confidence interval.
For the base case, we report the geometric mean the rewards, since the arithmetic mean would be a constant for this specific setting (the number of visits the last row, normalized by t, can be seen as frequency, and sums up to 1). hence, for this setting the geometric mean is more appropriate [58].
We also report the metric Σn 1x which indicates the number of cells in the last row of the grid that have yet to be visited at a certain time step.
63

---

DBMR-BPI
RND
Disagreement
APT
E/me
El Elmaax, Xy,el
El Eluin X.a0
20
5
10
60
4
9
3
10
40
2
2
20
0
2000
2000
2000
2000
2000
Episodes
Episodes
Episodes
Episodes
Episodes
DBMR-BPP BPI
RND
Disagroeneel
APT
E| X1,e
B Xast
max, X,,
El Elmin; Xi.k
15.0
12.5
50
3
10.0
10
30
5.0
20
2.5
0
2000 Episodes
2000
0
2000
2000
2000 Episodes
Episodes
Episodes
Episodes
Figure 18: DeepSea environment. Statistics for the random variable X, = E (5t, ae) (with Ti E Rmnd). Values are multipled by 100 and rounded to the first digit (except for the last plot). Shaded areas depict 95% confidence intervals.
Random rewards R.dd
E Eluedyg... (X.)
E[Avge (X.)
E sttdg.... (X.)
E Elmaxy...
(X.)
E Eiiing.... (X.)
20
DBMR-BPI RND APT
8.0(7.7,
9.9(
3.6(3.2,
18.7(17.00 20.5)
4.3(4.0, 4.6)
50000 T
7.9(7.6,
9.7(8.1.9.1)
3.5
18.6(16.7. 20.8)
4.5(1.1, 1.8)
6.6(6.0,7.1 7.1)
8.7(8.2.9.2) 9.2)
6.6(5.9..74)
27.2(24.6, 30.1)
1.6(133 1.9)
Disagreement
7.9(7.3,
8.9
6.4(5.8.7.1)
21.4(22.1, 26.88)
0.8(0.5,
30
DBMR-BPI
5.0(4.9.5.))
6.0(5.8663)
3.0(25.3.6)
16.0(13.4, 18.8)
3.4(3.2,
T 100000
RND
5.1(5.3,5.6
6.1((.9.6.1)
3.0(24433.5
15.1 17.9)
2.7(2.5, 3.0
4.6(4.3,49)
6.9(5.6.622)
4.7
18.6(16.7, 20.7)
1.3(100 1.6)
Disagreement
4.3(3.6,5.1)
6.2())
6.1.6.6.
22.2(20.2,21.3
0.2(0.1, 0.3)
Table 8: DeepSea environment. Statisties for the random variable X; ΣT (s az) (with E Ryad). Values are multipled by 100 and rounded to the first digit. In parentheses we indicate the 95% confidence interval.
When considering the base set of rewards Rhase used by DBMR-BPI we see that APT and Disagremeent do match the performance of DBMR-BPI and RND, focusing most of the time few rewards. On the other hand, while DBMR-BPT and RND show similar performance for N = 20, the difference increases for 30 on the base of rewards. We also note that DBMR-BP1 BPI tend to focus less specific rewards (on average max, X; is smaller). For larger N FBMR-BPI seems also to explore more uniformly (lower standard deviation, and higher minimum). When considering the total reward collected from the set Rrud, we see that DBMR- -BII achieves performance similar to RND, which confirms the capability of DBMR-BPI to collect reward from unseen reward functions.
Numerical results: rewards chosen by DBMR-BPI. In fig. 19 we plot the value of A estimated from DBMR-BP -PI. According DBMR-BPI the rewards in R initially the hardest to learn
64

---

(Arrr is small for those rewards), but then, as the algorithm eventually reaches those states, the estimated gap grows larger, and the hardest reward to learn actually the first one, corresponding to the one that yields positive reward in state (N - 0). This is indeed expected, since there are different paths the MDP that the agent can take to reach that state, while to reach state (N 1, N - 1) there is only one possible sequence of actions (and one can verify that the sub-optimality gap is also larger).
Fig. 20 shows the number of time certain reward was picked by DBMR-BPI for exploration (the plot does not account the uniform exploration over rewards, or the tracking procedure that ensures each rewards is selected at rate of ((vn), where n is the number of episodes). The last rewards (those with high id value) have been chosen the most since their sub-optimality gap was smaller for a longer period of time.
Fatimation of D2 for DEMR-BPT V 20
Reward sf
0.50
0.05
0.00
0.94
0.02
10
0.00
0
10030
200000
30000
43000
50000
Timestog
Estimation of Ap for DRMR-BFT 30
0.06
Roward
0.04
21
0.02
23
0.01
11
28
0.00
Timestop
29
Figure 19: Estimate A,r of DBMR-BPI over time steps. The i-th reward corresponds to the i-th reward in Roase. Shaded area corresponds to the 95% confidence interval over 30 seeds.
by DEVS-BFI up timestop T(N 20)
Number of rewards chuee by DONA-DPT up to timestep T(V = 30)
1200
500
100
Figure 20: Distribution of the number of times certain reward picked by DBMR-BI -PI up to time step T'. The i-th reward corresponds to the i-th reward in R The plot does not account for rewards chosen uniformly at random due forced tracking.
Parameters and compute resources. For these simulations we used G5.4XLARGE AWS instance with 16 vCPUs, 64 GiB of memory and A AOGG GPU with 24 GiB of memory. To obtain all the results 2-3 days are needed. The entire research project needed roughly days of computation time for this experiment.
65

---

The parameters are listed in tab. 9. Refer to app. E for further details on the parameters and the algorithms.
DaNR-BB 8PI parameters
Value
AFI parumelers
Value
Uisagroenent parameters
Value
RRD parameters
Value
Neceemete
Naan
Ngg
[6,,0
Mahnorkpi
64
10'
10"
10"
I1
10
10
10
dg Ol
(5
1,5
0.5
Neep
512
2 Nensemmtee
20
Neep
512
Phiaal
Nigaodk
[64.04
Ne
64
Ostonn
10
Ored
10
Ng
64
Our
Ag
Table 9: Parameters and values of the algorithms. For all algorithms used batch size of 128.
D.3 Radio network control problems
D.3.1 Downlink link adaptation problem
In this section we describe how the DBMR-BR BPI can applied to the Downlink link adaptation problem [37] in radio networks.
Overview. Link adaptation, or adaptive modulation and coding (AMC), technique used in wireless communication systems, such the 3GPP HSDPA, LTE or NG-RAN, to dynamically adapt the transmission rate of a communication link to the time- and frequency- [37]. Modulation and Coding Schemes (MCS) effectively adapt the transmission rate by matching the modulation and coding parameters used for communication (such as modulation order, code rate, etc.) to the conditions of the radio link, such propagation loss, channel strength, interference from other signals concurrently transmitted in the same radio resources, etc. Link adaptation is a dynamic process that acts potentially as frequently each transmission time interval (e.g., sub-millseccond time-scale in the 3GPP NG-RAN system) wherein a communication scheduled between base station (a radio node that facilitates wireless communication for user equipment within its coverage area) and a user equipment (UE, a mobile device such as a smartphone or tablet).
channel conditions
Link adaptation algorithms attempt to optimally adapt the transmission data rate chosen for link to the current channel and interference conditions of the link. These algorithms select the most appropriate modulation order and coding rate (also known as modulation and coding scheme, MCS) based on the latest information available about the state of the communication system as well as the state of the individual communication link (e.g., Channel Quality Indicator, CQI) for which the MCS value is selected.
cNB
UE
MCS
RI Agent
ACKNACK
Figure 21: Downlink link adaptation diagram.
Problem Objective. In wireless communication systems, there is fundamental trade-off between throughput and spectral efficiency, which can be understood in terms of resource elements. Resource elements are the smallest units fime-freyuency resources allocated for transmission, encompassing specific duration of time and specific frequency bandwidth. Our objective is to explore the environment using DBMR-BP BPI to design policies that optimize this trade-off based on the desired intent.
66

---

Higher throughput, the amount of data transmitted successfully per unit of time, often requires higher-order modulation schemes and denser coding rates, which can reduce spectral efficiency- the effective use of available spectral resources. Conversely, enhancing spectral efficiency through lower-order modulation schemes and robust coding rates can ensure more reliable transmissions but may limit throughput.
Since measuring throughput directly is challenging due various influencing factors, we consider Transport Block Size (TBS) as proxy. TBS represents the amount of data that can be transmitted in a given time interval based on the selected Modulation and Coding Scheme (MCS). However, increasing larger TBS can lead to higher Block Error Rate (BLER) the percentage of transport blocks that fail to be decoded cerrectly-ippceee the reliability of data transmission and reducing the actual amount of successfully received data.
TBS does not necessarily result in higher throughput,
Duplexing (TDD) 5G system operating at a 3.5GHz carrier frequency, with PHY layer numerology μe of the 3GPP technical specifications 38.211 and single-user Multi-Inpur Multi-Output (SU-MIMO) transmission. Each base station is configured as massive MIMO (mMIMO) with an 8x4x2 antenna array. We consider 1 site, 3 sectors, and fixed number of 10 UEs with full buffer traffic, thereby experiencing stable interference conditions. We generated 150 randomized scenarios during training that randomize across several variables (e.g., UEs movement and traffic). Each scenario lasted 5 seconds.
Environment, RL formulation and setup. We consider
The downlink link adaptation problem can be formulated as a multiple-rewards RL problem as follows:
The base station represents the RL agent that, depending on the channel measurements transmitted by the UEs, chooses the modulation and coding scheme (MCS).
The state includes current CQI values, number of the antennas of the UE, estimated speed of the UE, rank indicators, and other relevant metrics that affect link quality, including a windowed history of these values.
Actions involve selecting different MCS values, which dictate the modulation order and coding rate for the packet transmission.
The transmission of packet from UE is modeled as an episodic MDP of at most 5 steps. At each time step I, the agent chooses an action d (the MCS). If the transmission is successful, the agent receives an ACK and the episode terminates. Otherwise, the agent receives a NACK and observes the new channel measurements (next state) until the episode is done.
The environment was simulated using a proprictary simulator" 10 the code for which cannot be disclosed. We evaluated the DBMR-BB BEMR-BPI algorithm along with RND, APT and Disagreement.
Reward design. We consider two rewards, that optimize for different intents. For each episode we let 2, be boolean value indicating if the packet was successfully transmitted (ACK) not (NACK). We also let TBS, indicate the transport block size for the n-th transmission, and Nye., the number of resource elements for the n-th transmission.
1. Transport block size: Fı,= = TBS, 1,,=1, this reward encourages the agent to choose actions that maximize the transport block size (at the expense of other metrics, i.e., error rate, spectral efficiency). measured as the number of bits successfully transmitted packets.
2. Spectral efficiency: F2,n 0 if the transition is not terminal; otherwise, 72,n
- -Knnn Nre. representing the total number of resource elements used up to the final time step n of the episode.
These rewards, if weighted together, can optimize for different intents, between throughput, efficiency and transmission rate.
Numerical results: performance. In fig. 22 we report the performance of the various algorithms in terms of (1) throughput, (2) BLER (block error rate) and (3) spectral efficiency (which measures the number of resource elements used).
The environment design and MDP formulation come, are inspired, from forthcoming publication [101].
67

---

DEMR BPI: 14.70 Mbps
RND: 11.64 Mbps
Disagreement: 9.09 Mbps
APT: 12.67 Mbps
0.100
1.0
0.08
0.6
0.04
0.4
0.02
0.00
0.0
Throughput (Mbps)
Throughpat: (Mbps)
BBMMR-BPI: 0.40 bier
RND: 0.71 bler
Disagroement: 0.56 bler
APT: 0.51 bler
1.0
0.8
PDF
0.6
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
DEMR-BPL: 6.9 bits/re
RND: 5.2 bits/re
Disagreement: 144 bits/re
APT: 5.6 bits/re
0.20
0.15
0.10
0.4
0.05
0.2
0.00
2
6
6
Spectral efficiency (bits per re)
Spectral efficiency (bits per re)
Figure 22: From top to bottom: (1) throughput distribution achieved during training; (2) BLER distribution during training; (3) distribution of the number of bits transmitted per resource elements (spectral efficiency) during training. In the legend we also write the average value for each algorithm.
In fig. 23 present the distribution of the number of transmissions attempted per packet and the action selection (MCS index) for each algorithm.
We observe that DBMR-BPI achieves better performance both in terms of throughput and spectral efficiency. The MCS index distribution reveals that DBMR-BPI tends to use all the available actions during the first transmission (note that only the last 5 index values used during re- (e-raasmmissoons), which seems to indicate that it is effectively learning which action to take depending on the state features. On the other hand RND and Disagreement tend only focus the initial MCS index values during the first transmission.
We also note lower BLER target for DBMR-BPI, as evidenced also by the fact that the average number transmissions is lower for DBMR-BPP BPI compared to the other methods.
In general, these performances appear to be primarily due to optimized usage of resource elements, as shown fig. 24. This figure illustrates the distribution of rewards collected during training for each episode. While the TBS is similar across all algorithms, DBMR-BP1 clearly focuses on optimizing the number resource elements.
This type of analysis is valuable for practitioners to understand the properties and impacts of each reward function.
Numerical results: rewards chosen by DBMR-BPI. In fig. 25 we plot the estimate A for both rewards (left plot) and the number times DBMR-BPI selected each reward (right plot; does not account for forced tracking uniform exploration). From the left plot see that optimizing
68

---

Disagreement:
1.0
1.5
1.0
0.6
0.4
0.2
0.0
0.0
2
5
2
Number of transmissions per packet
Number of transmissions per packet
DBMM--PPE: 20.4
RND: 23.5
Disagreement: 19.1
APT: 20.4
0.3
1.0
0.8
0.2
PDF
0.6
0.4
0.1
0.2
0.0
0.0
10
15
20
25
30
5
10
15
20
25
30
MCS index
Figure 23: From top to bottom: (1) distribution of the number of re-transmissions per packet during
training; (2) MCS index selected by the algorithms during training (note that only the last values are used during re-transmissions) In legend we also write the average value for each algorithm.
TBS
RE
0.0
-0.1
0.2
0.3
0.4
-0.5
DBMR-BPI
RND
Disagreement
APT
DBMR-BPI
RND
Disagreement
APT
Figure 24: Distribution of the normalized rewards collected during training by the algorithms.
the number of resource elements seems to be harder task due to the lower value of Ar, which explains why DBMR-BPI focuses more on optimizing the number of resource elements used per packet transmission.
1e6
Number of rewards chosen by DBMR BPI
D estimate
1.5
T3S
0.003
RD
1.0
0.002
6.001
0.000
1.5
RE
TBS
Reward
Figure 25: Left plot: value of Ar, estimated by DBMR-BPI during training for both rewards. Right plot: distribution of the rewards chosen by DBMR-BP during training.
69

---

Parameters, compute resources and libraries. For these simulations we used 4 private workstation each with 24 vCPUs, 128 GiB of memory and A10 NVIDIA GPU. To obtain all the results 6 days of computation time are needed. The entire research project needed roughly 24 days of computation time for this experiment.
The parameters are listed in tab. 10. Refer to app. E for further details on the parameters and the algorithms.
LCBRAC4 Reanats
Natucdes
10 1-
10
10
15- 1.--0-1
1-10
Routtons
5:10
10
No
256
125.125,
120
1000
5-10"
Table 10: Parameters and values of the algorithms. For all algorithms the batch size was 512. The notation [xr, k indicates stack of k layers of size
We set up our experiments using Python 3.10 [88] (For more information, please refer to the following link http:// /wwp///wwww//// python. org), and made use of the following libraries: NumPy [89], SciPy [90], PyTorch [98], Seaborn [92], Pandas [93], Matplotlib [94].
70

---

E Deep-RL Algorithms Details
E.1 DBMR-BP1 BPI algorithm
Overview. As mentioned in sec. 4, extending MR-NaS to Deep-RL is not straightforward. Firstly MR-NaS is a model-based method, secondly there is no closed-form solution to arg inf U* (w; M. To circumvent these issues, we adapt the DBMF-BB BPI algorithm from [53], where the authors propose BBM. a deep-RL exploration approach for single-reward BPI. In [53], the authors suggest that a model-free solution can be achieved by (i) using the generative solution arg inf AE(S (w; M). which can be computed in closed form, and (ii) by estimating the parametric uncertainty of the MDP-specific quantities (sub-optimality gaps, etc.). In other words, the generative solution may be close enough to the model-based one. Nevertheless, this solution may be biased because we do not know what are the true sub-optimality gaps, and therefore we need to take into account the parametric uncertainty that we have in the estimates.
Hence, we propose DBMR-BP an extension of DBMF-BPI, which learns an ensemble of Q-functions of the optimal policy and, similarly, the k-th moment of that Q-function (called M- M-ffnncion). More precisely, the extension of DBMF-BPP to a finite set of rewards, mainly consists of few modifications that we describe in the following paragraphs.
1. Value learning for different rewards. The Q-function in OBMR-BPI (sim. the M-function) learns the value for multiple rewards. In the finite action setting this implies that there are ARt values to estimate in every state. Alternatively, we also tried to feed the networks with one-hot encoding of the chosen reward, but this resulted to be less effective in terms model capacity.
2. Reward exploration. We explore according to the difficulty of the reward function. For the sake of stability, the beginning of each episode (or, for example, every 1/(1 -n) steps) we sample reward r ~ R to explore, and apply DBMF-BPP -PI on this reward. To estimate the exploration difficulty, simply the estimate time of the minimum sub-optimality gap Air (see paragraph below), and explore a reward with probability 1/4..r
In addition to the mechanism described above, we also introduce random uniform exploration of the rewards and forced tracking of the rewards:
Random exploration: with probability Puniform we choose reward uniformly at random.
Forced tracking: this mechanis ensures that each reward is explored sufficiently often. We let U, (r E R: Vt Nra/2 < 0} be the of sampled rewards at time where Nr, is the number of times the algorithm has chosen reward r in the previous t steps, and choose arg min, Nr,, whenever U, is non-empty (otherwise, we sample it as in Alg. 2). This procedure guarantees that each reward is sampled at a rate of O(VI) [20].
Algorithm DBMR-BPP BPI Reward selection
I: if X S Punsform then
2: Choose a reward uniformly at random.
3: else if Us is not empty then
4: Choose reward arg min, Nr.e-
5:
else
6:
Choose reward r with prohability x AT,"
7:
end if
3. Estimation of the sub-optimality gaps A.r To estimate the minimum sub-optimality gap for a fixed reward r, initially used the method described in DBMF-BPI. However, their estimates often overly conservative, In DBMF-BI -BII, the minimum gap for each batch across all models in the ensemble is calculated and added rolling window. The smallest value in this window is then used as the target for stochastic approximation, employing decreasing learning rate.
We instead compute Aer as follows:
71

---

1. For each reward in the batch, we calculate the gaps and take the minimum across the models in the ensemble. We then average these minimum gaps over the transitions in the batch to obtain an estimate At, This approach is less conservative than taking the minimum across both transitions and models the ensemble.
2. We treat A,, as learnable parameter and use the estimated gap å., as the target value. We compute the Huber loss between A.r and A,,, and perform gradient step update
L.r
3. To further stabilize the estimate of Ar. we can apply Polyak averaging over time steps.
The main parameters for DBMR-BPI are as follows:
Symbol
Description
Nensemble
Ensemble size
Nibmmrbpi
Hidden layers sizes for each model in the ensemble
Rate which the target network updates
ag, RMM
Learning rates of Adam for the Q.M Q.M-nkeworks
Punsform
Uniform random reward probability
Pmaak
Mask probability used by DBMF-BPI
k
k-value used by DBMF-BPP
Sprior
prior scale value used by DBMF-BB
C
Maximum size of the replay buffer
Table 11:
parameters.
E.2 Other algorithms
For APT, Disagreement and RMD we used the open-source implementation from [24]. However, the implementation in [24] only works for continuous action spaces, therefore adapted the implementation to discrete action spaces as described below. For all the algorithms we used the same architecture in the original papers, and only did slight tuning of the parame-arameters..
DQN agent. Each algorithm uses a Double DQN agent learn the Q-values using the intrinsic reward computed by the corresponding algorithm. The main parameters for this DQN agent are
Symbol
Description
Ndgn
Hidden layers sizes
Maximum size of the replay buffer
T
Rate at which the target network updates
Learning rate of Adam
Table 12: DQN parameters.
APT Agent. This agent uses forward network F& and a backward network Bg to learn a represent- ation that used compute the intrinsic reward. The forward network predicts a representation of the next state $1+1 given the current state and action while the backward network predicts the action that was taken à given two consecutive state representations St, St+1-
The representation is Nrep -eep-dimessional, and learnt by a trunk network Mg.
The loss is computed by averaging over batch B the forward and backward errors. The forward error computed as in [24]
eforwerd(B)
Σ
[F)))M()):))a - Mo(s441)l2.
B
($
where Fo(:)a is the a-th predicted representation.
We adapt the backward error to discrete action spaces by using the cross-entropy loss
Obackward (B3) =
Σ
Σ ((a=a)) (o)()))) Mo(s)+1))a,,
B
(Nt au
BBB
72

---

where B. is the predicted probability of action a by the network. The overall loss over a batch elB) e forward Cbeckward (B).
For this agent, in addition to the parameters tab. 12, we also have the following parameters
Symbol
Description
Nrep
Representation dimension
Ntrunk
Hidden layers sizes for the trunk network
NF
Hidden layers sizes for the forward network
NB
Hidden layers sizes for the backward network
Oapt
Learning rate for APT
K
Number of neighbors used to compute the particle based entropy Table APT parameters.
Disagreement agent. This agent variance across the models then used to quantify the parametric uncertainty and compute the intrinsic reward. We kept the same implementation in [24]. For this agent, in addition to the parameters tab. 12, we also have the following parameters
ensemble of models predict the next state. The
Symbol
Description
Nensemble
Ensemble size
Ndisag
Hidden layers sizes for each model in the ensemble
adisng
Learning rate for Disagremeent
Table 14: Disagreement parameters.
RND agent. This agent uses predictor and target network estimate the parametric uncertainty, which is then used as intrinsic reward. This is similar to the mechanism employed by prior networks in [102]. Simply, for given state both the predictor and target networks output a representation of dimension Nrep- The predictor is then trained to minimize the lg norm distance between the predictor representation and the target representation.
For this agent, in addition to the parameters in tab. 12, we also have the following parameters
Symbol
Description
Nrep
Representation dimension
Nyud
Hidden layers sizes for the predictor/target networks
Olynd
Learning rate for RND
Table RND parameters.
73

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We reported in the abstract and (mainly) in the introduction the contributions the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in app. A.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an import- ant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
74

---

Answer: [Yes]
Justification: All theorems/results are numbered and cross-referenced and we make clear the assumptions used in the paper. For each result we indicate where to find the proof in the appendíx.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our contributions, the MR-NaS and DBMR-BPI algorithms, are fully described in app. and app. E. Numerical experiments, including details and parameters used, are fully described in app. D. We further release the code of the algorithms, and of the environments, except for the simulator used in app. D.3.1, which is proprietary and not disclosable (we provided all the details to be able replicate the experiment).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
75

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Yes, in the code we provide the instructions in the README file to run the simulations, collect data, and plot the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp cc/
public/guides (holic/guudees/Coddeubbiisesss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https:
//niss. wttps.cccpubliiiii cttppblcc/aaaeecccccccccccccccct heee/guieee wwweeeee//ooobbmmeeeeeeee cestuummissioonne ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all the details of the experiments, including ppper-parameters, optimizers used, etc. in the appendix. Also the code is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In all results we report the average value and confidence intervals. For some results we also show directly the data distribution.
Guidelines:
The answer NA means that the paper does not include experiments.
76

---

The authors should answer "Yes" if the results are accompanied by error bars, confid- ence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: For each experiment we reported the appendix the resources used and the total computation time.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //teuri///s//s//// cc/public// c/Ethi wwwideeileeeeeeneeee line??
Answer: [Yes]
Justification: Yes, the authors followed the NeurlPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: It is discussed in app. A.
77

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe that the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: For all the assets used we cited the original authors. In the README of the code we cite the license of the assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
78

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: For all the code published we provide documentation in the code or README file. Licensing mentioned in the REAME file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
79

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
80


Reviews:
[{"review_id": "Dl914ZVzvZ", "reviewer": "Reviewer_1UCp", "summary": "The paper addresses the challenge of identifying the best policy in RL when there are multiple rewards. The authors get a lower bound on the sample complexity and design an optimal exploration policy. The authors propose two algorithms: MR-NaS for tabular environments and DBMR-BPI for Deep RL. These algorithms efficiently identify the best policy across multiple rewards in RL.", "questions": "Please address the issues mentioned in the weaknesses.", "limitations": "As noted in the paper, the assumption of a unique optimal policy limits the method's applicability to a broader range of scenarios. The computational cost of convex optimization may prevent it to deal with large-scale dataset.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper presents a comprehensive and well-balanced analysis of theoretical and empirical results. The appendix provides supplementary evidence that strengthens the authors' arguments.", "weaknesses": "1. The paper  is inspired by [17], but it would be better to explicitly acknowledge this inspiration in the main part, rather than mention it at Remark C.2. Furthermore, a more in-depth discussion of the challenges in proof caused by the novel forcing policy would strengthen the paper's contribution.\n\n2. Even though more details is covered in the appendix, the paper should provide some details on the convex optimization. For example, a discussion of the computational costs associated with these methods would provide valuable context for readers. Sometimes, the computational cost of convex optimization methods are high. \n\n\n3. The abstract would be better if providing a more impressive motivation for multi-reward RL, emphasizing its significance and potential impact.\n\n4. Didn’t put some innovative aspects in the main text, leaving vital details to be discovered in the appendix. This can lead to important contributions being overlooked.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and valuable feedback. We appreciate the time and effort spent reviewing our paper, as well as your positive comments on the comprehensive analysis of theoretical and empirical results.\n\nBelow, we address each of your concerns and outline the corresponding revisions we plan to make to improve the paper.\n\n> The paper is inspired by [17], but it would be better to explicitly acknowledge this inspiration in the main part [...] a more in-depth discussion of the challenges in proof caused by the novel forcing policy would strengthen the paper’s contribution.\n\nWe would like to clarify that we acknowledge this inspiration in multiple points, including at the beginning of Sec. 3 (line 118), Sec. 3.1 (lines 133-134), and Sec. 3.3 (line 172). To further highlight this point we plan to include this sentence in the introduction: \n\"Our work is inspired by [17] for single-reward BPI and extends the results and analysis to the multi-reward setting\".\n\nRegarding the challenges in the proof, we agree with the reviewer that expanding on these in the main text would enhance the paper and highlight an important contribution. We have already briefly described how our approach removes the need for an MDP-specific constant in the forced exploration (discussed at line 195), which previously limited the usability of NaS [17]. Due to lack of space, more details on the novelty of the forcing policy were left in the appendix. We will make sure to include these in the main part of the paper by using the extra page in the final version of the paper. More precisely, we will further enhance our discussion by highlighting the challenges addressed in our proof and emphasizing our improved result for the high-probability forced exploration theorem, which we believe is of independent interest. \n\n> Even though more details is covered in the appendix, the paper should provide some details on\nthe convex optimization. For example, a discussion of the computational costs [...]. The computational cost of convex optimization may prevent it to deal with large-scale dataset.\n\nWe agree with the reviewer that the paper should provide more details on the convex optimization problem defining $U^\\star$.\nWe plan to include a subsection discussing the technical aspects of solving the  optimization problem in the paper (note that currently in  appendix D we provide the total runtime of our simulations), including implementation details and further results on the computational cost.\n\nLastly, for Deep-RL, our algorithm DBMR-BPI has similar computational complexity as  DBMF-BPI [40], or Boostrapped DQN [43] at inference and training time (due to  a  vectorized implementation of DBMR-BPI). \n\n> The abstract would be better if providing a more impressive motivation for multi-reward RL, emphasizing its significance and potential impact.\n\nWe appreciate the suggestion and we agree that the abstract could better emphasize the motivation for multi-reward RL. In the introduction, we already highlight the practical importance and potential impact of Multi-Reward RL and its relevance with respect to existing similar settings. For instance, reward-free RL might not always applicable in industry. In some applications, there are only a finite number of rewards to optimize. \n\nTo illustrate this aspect concretely,  in Section D.3 of the appendix, we present an example of applying DBMR-BPI to a radio network control problem using an industry-level network simulator, demonstrating how current reward-free exploration techniques are limited when the number of rewards is finite.\n\nWe will make sure to highlight these aspects in the abstract and include these consideration in the final version of the paper.\n\n> Didn’t put some innovative aspects in the main text, leaving vital details to be discovered in the appendix.\n\nWe agree with the reviewer that, due to the limitation in space, some important aspects were left to the appendix. We will integrate the main innovative aspects into a dedicated section by using the extra page in the final version of the paper. This section will include a summary of the theoretical and practical contributions, as well as their implications.\n\n> The assumption of a unique optimal policy limits the method’s applicability to a broader range of scenarios.\n\nWhile we agree that the uniqueness assumption may be limiting for a continuous set of rewards, we believe that it is less restrictive when the set of rewards is finite, as it is generally easier to guarantee the uniqueness of an optimal policy in such cases. \n\nFurthermore, note that, as discussed in Appendix A (Limitations section), the assumption on the uniqueness of the optimal policy is common in the BPI literature [18, 16, 17, 40, 20]. Addressing MDPs with multiple optimal policies or identifying $\\varepsilon$-optimal policies  necessitates the use of more complex overlapping hypothesis tests [67]. We refer the reader to this Appendix for more details and further consideration on this extension.\n\nLastly, while the theoretical results may require this assumption, in practice we experienced both MR-NaS and DBMR-BPI to perform well in the numerical experiments even in presence of multiple optimal rewards.", "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": "yYAxJt2TEf", "reviewer": "Reviewer_N1yn", "summary": "This paper studies the problem of best policy identification for RL with multiple rewards. The goal is to efficiently identify the best policy for given rewards with a high-level confidence. Authors provide an instance-dependent lower bound for the studied problem and introduce a provably-correct algorithm for a convex approximation of the original problem in the tabular setting. Extensions to deep RL is discussed with numerical results.", "questions": "1. Do we treat MR-BPI as dedicated exploration strategies for multi-objective RL?\n\n2. Most reward-free RL focuses on episodic settings, whereas this paper studies discounted settings for multi-reward MDPs. Is there any particular reason for choosing this (simpler) setting? Do you foresee any technical challenges that can be difficult to resolve in episodic multi-reward settings?\n\n3. In Line 81 - 86 (Set of rewards), for each reward vector, each coordinate $i$ represents the reward for the $i$-th state-action pair, which is a scalar, why do we need the canonical basis $\\mathcal{R_{canonical}}$ of rewards, where each element is a vector? (When you write $\\mathbb{R}^{SA}$, I assume each element is a real number, not a vector). Do you assume for each $(s, a)$, there is a different reward function? Could you provide a concrete example of your definition of \"set of rewards\" with your notation? I assume you intended to say there exists $m$ (global) reward functions, and this set of functions $\\mathcal{R}$ is thus in $\\mathbb{R}^{m \\times SA}$.", "limitations": "There are no unaddressed ethical considerations in the studied context.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors demonstrate how to efficiently identify optimal policies across multiple rewards. The strengths of this work are summarized as follows:\n\n1. The studied setting is interesting and of practical concern when we seek to optimize the performance across a set of rewards.\n\n2. An instance-dependent lower bound is identified for any Probably-Correct algorithm in the setting of multi-reward best policy identification problem.", "weaknesses": "While this paper clearly articulates the idea of performing, here are some problems and potential improvements that authors are suggested to address and consider. More specifically,\n\n1. Environments for the deep RL part is too simple. The Cartpole swing-up and DeepSea environments cannot fully demonstrate the performance of the proposed algorithm in more complex, real-world scenarios. It would be beneficial to include experiments on more challenging benchmark environments for better assessment of scalability and practical applicability.\n\n2. The policy optimality is only considered and defined for stationary deterministic policy (as in definition 2.1), which can be too restrictive. It is not clear when considering the set of Markovian policies (which can be stochastic), whether the proposed lower bound still holds, and whether the performance of the algorithm is still optimal. \n\n3. Theoretical guarantees for the deep RL extension is unavailable. Sample complexity bounds are only provided for tabular settings, which leads to the dependencies on the cardinality of state and action space. And empirical studies for the deep RL settings are not sufficiently convincing due to the simplicity of the environments.\n\n4. In terms of the theoretical results of the lower bound, the proof structure closely follows the prior results (e.g. Marjani et al. 2021, Taupin et al. 2022) in single-reward RL. It is not quite obvious what are the main technical challenges and novelties of extending the prior results (e.g. Marjani et al. 2021) from single-reward RL to multiple-reward RL.\n\n5. While the studied setting can be interesting, the relationship between the MR-BPI problem and reward-free RL as well as multi-objective RL somewhat remains unclear throughout the context. Though discussion has been provided in Section 1 and 5, I am not fully convinced that reward-free RL cannot solve the concerned practical scenario in multi-reward best policy identification problem. Indeed, reward-free RL assumes rewards are unknown, whereas the studied settings assume the knowledge of rewards. As a result, it is not surprising to see that properly utilizing the knowledge of rewards can lead to better performance as shown in the numerical results: the proposed algorithm (MR-NaS) significantly outperforms RF exploration strategies (RF-UCRL, ID3AL). However, reward-free RL is a more general type of algorithms and can be particularly useful in practice when it is hard to accurately learn rewards or when rewards are sparse.  As such, the emphasis of the two settings are rather different. It might not be a fair comparison, and it is desirable to provide the fundamental reasons that can explain such performance improvement in numerical experiments. Therefore, more thoughtful insights should be provided to clearly explain the difference and relationship between these settings.\n\n6. Some minor aspects:\n    - Grammatical errors need to be addressed, e.g. Line 354, line 91.\n    - In line 75-80, if only deterministic policies are been considered, it is more appropriate to write $a_t = \\pi(\\cdot|s_t)$ etc. Do not use the probability simplex notation for policies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and for the time and effort spent reviewing our paper. Below we provide detailed responses to the main concerns raised by the reviewer.\n\n> Simple environments for deep RL\n\nWe appreciate the reviewer's concern. However, the selected environments are intentionally designed as hard exploration challenges, as referenced in [36,40,43]\nAdditionally, we  included  experiments for a real-world application in appendix D.3 (a radio network control problem). These  experiments show the effectiveness of our algorithm  in a realistic environment using an industry-level network simulator. \n\n> Optimality is only considered and defined for stationary deterministic policy\n\nFor finite MDPs, the optimal policy is stationary and deterministic (see Theorems 6.2.9 and 6.2.10 in [39]). Therefore, in this context, the lower bound holds, and the performance of our algorithm is asymptotically optimal  with respect to $U^\\star$.\n\n> Theoretical guarantees for the deep RL extension\n\nWe acknowledge the absence of theoretical guarantees for the deep RL extension. \nHowever,  our primary goal was to establish a foundational understanding of the multi-reward setting for finite MDPs, which is crucial for building towards more complex cases.  \n\nProviding theoretical guarantees for deep RL  would merit its own manuscript.\n\n> Main technical challenges and novelties of extending the prior results  from single-reward RL to multiple-reward RL.\n\nFor the lower bound, as in prior work, the proof builds upon classical change of measure arguments. The main difference with respect to the single-reward setting lies in the additional optimization over the set of rewards. \n\nHowever, there are several differences compared to prior work, highlighted throughout the paper. For example:\n\n1. Concerning the relaxed characteristic rate, deriving a tractable  optimization problem for $U^\\star$ in presence of a continuous set of rewards is challenging, since the minimum sub-optimality gap can be non-convex (see Sec. B.4 of the appendix). To address this issue, we show that it is sufficient to consider a finite set of rewards. This finding is  used in our numerical results (see Sec. D.1.2 in the appendix or Sec. 3.4 in the main text).\n\n2.  Regarding the algorithm, we remove the need for an MDP-specific constant in the forced exploration (see line 195), which  limited the usability of NaS [17]. We further provide a novel high-probability forced exploration result (see also remark C.2, page 35).\n\n3. Regarding the extension to Deep-RL,   prior works in BPI mostly consider the tabular case. Furthemore, the extension of [40] to the multi-reward setting is non-trivial. First, by inspecting $U^\\star$,  we design an exploration procedure that explores according to the difficulty of the rewards. Secondly, we experimented with various architectural changes of the neural  networks to accommodate the multi-reward setting.\n\n\n> I am not fully convinced that reward-free RL cannot solve the concerned  scenario  [...] reward-free RL is more general  and can be useful when it is hard to accurately learn rewards or when rewards are sparse.\n\nAs correctly noted by the reviewer, considering a set of known rewards can provide superior performance with respect to the more general reward-free RL setting and this is the main motivation behind our setting. \n\nDetermining the best policy for any possible reward  is a harder problem that is unlikely to occur in some practical problems. Hence, for applications where there are only a finite number of rewards to optimize, the multi-reward setting would provide a better model choice w.r.t. the reward-free setting. We provide a concrete example of this scenario in Appendix D.3.\n\nRegarding the sparsity of the reward, our  method can also handle scenarios with sparse rewards, as demonstrated in our numerical results.\n\nLastly, while the comparison may not be completely fair, there are currently no other pure exploration algorithms in the multi-reward setting (and reward-free RL is one of the closest to our setting). For this reason, we compare to different reward-free methods, as well as an adaptation to the multi-reward setting of PSRL [35] that we provide in the appendix.\n\n> Do we treat MR-BPI as dedicated exploration strategies for multi-objective RL?\n\nThe multi-reward setting, as well as reward-free RL, share some similarities to multi-objective RL. In multi-objective RL, one seeks to identify the Pareto frontier of non-dominated policies. This objective is, in general, a significantly harder challenge compared to identifying the optimal policies for a finite set of rewards. \n\n>  Is there any particular reason for choosing the discounted setting instead of the episodic one?\n\nWhile  most reward-free approaches focus on episodic settings, in practice, many algorithms used in industry employ the discounted setting. Our goal was to strike a balance between providing theoretical results and developing a practical algorithm that practitioners can readily apply. \n\nWe believe the discounted setting can be extended to episodic, leveraging recent advances in [A].\n\n> Why do we need the canonical basis of rewards? Could you provide a concrete example  of ”set of rewards” with your notation? \n\nEach element of the canonical basis is a vector of size $SA$. For example, $e_1$ represents a sparse reward where $r(s_1,a_1)=1$ and $0$ otherwise, expressed in vector form as $e_1 = \\begin{bmatrix} 1 & 0 & \\dots & 0 \\end{bmatrix}^\\top$. Similarly, $e_2$ is a reward vector that assigns a reward of $1$ to the second state-action pair and $0$ otherwise.\n\nIn some experiments we explored according to this canonical basis of rewards (as previously explained, see also Sec B.4 in the appendix).  For a concrete example, we also refer the reviewer  to section B.4.1 of the appendix.\n\n**Additional references**\n\nA. Al-Marjani et al. \"Towards instance-optimality in online pac reinforcement learning.\" arXiv:2311.05638 (2023).", "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": "2tHVj2bkPc", "reviewer": "Reviewer_YFyE", "summary": "The present article extends the track-and-stop approach of Garivier et al. to a multi-reward MDP setup. Given an MDP problem with a finite number of reward functions the aim is to develop an algorithm that learns optimal policies for all reward functions simultaneously. Under (drastic) assumptions the authors present a sample based variant of track-and-stop in the multi reward setup. The algorithm is based on replacing the theoretical model complexity $T^*$ (in a multi reward variant) from Garivier et al. by an upper bound $U^*$ that can be estimated. Estimating $U^*$ during the exploration phase results in a practically implementable termination condition that results in worse complexity than the theoretical termination condition. The algorithm is tested on a few (very similar) tabular examples and compared to simple algorithms. An educated guess is performed to design a deep variant of the algorithm that is tested on a multi reward card pole variant and deep sea. Results beat easily the (terrible) results of the benchmark algorithms used.", "questions": "Here is a number of questions and comments.\n\n- $\\alpha$ should also be an input for the algorithm 1. Why is there no dependence on $\\alpha$ in the theoretical results?\n- How do you compute U in Algorithm 1 without knowing the rewards gaps? You estimate M, but what about the gaps? They are estimated in the deep setup, why not in the tabular setting?\n- I think the algorithms are not sufficiently explained. In the tabular case $M_t$ should be explained in more detail. What shall the reader get from \"use estimate $M_t$ of the model\", \"update $M_t$\" without knowing $M_t$? In the present form the article is hardly comprehensible (even for me as a Mathematician). In that generality (what estimate is used?) I am a bit sceptical about the validity of Theorem 3.3, but as said, I could not try to understand all proofs.\n- The use of Borel-Cantelli in the proofs is not correct as it is. The events are not independent and this direction of Borel-Cantelli requires (pairwise) independence. I am pretty sure the SARSA paper contains the details on how to use a conditional independence version of Borel-Cantelli.\n- I am a bit puzzled about the connection of Theorem 3.1 and 3.3. If I am not wrong, Theorem 3.1 is a bandit theorem, requiring to play independent \"arms\" $(s,a)$ while Theorem 3.3 (the algorithm) is an RL theorem requiring rollouts $(s_0,a_0, s_1,a_1,...)$. The latter is obviously much harder and depends a lot on the exploration method. Unfortunately, I have six 50pages NeurIPS papers on the table and cannot go fully through every proof. Could you add two sentences why the theorem should hold? For instance, SARSA convergence holds by rewriting SARSA as Q-learning plus an error that goes to zero by the exploration condition. Here, the situation is much harder.\n- A crucial point is to replace $T$ by $U$. In line 169 you mention an upper bound for $U$, which has an additional $1/\\Delta^2$ compared to the theoretical bound. Is there a better theoretical bound? The authors should at least discuss briefly in the main text that there is something non-trivial going on (as in the SARSA paper where on-policy exploration is essentially as good as off-policy exploration). As it is it one quickly overlooks the difference in the algorithm to the \"allocation\".\n- I cannot see a scaling in the number of rewards. Is there any theoretical understanding on how $\\tau$ scales in the number of rewards?\n- How does your algorithm compare to just train for one reward after the other? Does that make sense? The training time for card pole seems quite high but I might be wrong. Typically card pole plots show the number of episode (ca. 200-300), not the number of steps. Is it clear your algorithm is faster than just training 5x card pole? How about comparing your algorithm to training 5x card pole with your different reward settings but keeping the neurone network from the reward before (and using some replay buffer to avoid overfitting)? My feeling is that such a naive approach might be better than the benchmarks used. \n- Similar question: Comparing your deep algorithm to performing several deep trainings for different rewards. Is your approach particularly suitable to avoid overfitting? Does your algorithm help for generalisation (as you see in the cardpole example?).", "limitations": "The tabular setting requires drastic assumption (but gives a clean analysis), the deep setting is an interesting educated guess but does not allow a mathematical analysis. I would say that is quite normal for RL, except, perhaps, the deviation of the educated guess Algorithm 2  from the tabular algorithm 1 is pretty big.\n\nThere is no good benchmark to compare to, this makes the numerical results a bit boring. Perhaps a better benchmark would be to compare to training individually the policies. While that might even beat the proposed algorithm in the tabular case (for few rewards) I doubt the same holds for the deep case as the NN would only remember to solve the last reward problem.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The article is extremely dense with information, perhaps it would have been better to split the article in 2 or 3. The theoretical development is an extension of several earlier articles of the authors with very detailed mathematics. While the tabular examples are of limited practical interest (the assumptions are just too strong) the deep variant is interesting. While I am not so sure about the relevance of the tabular setting, the relevance in the deep setting is obvious (and was realised of the authors for cardpole). The ability of generalisation of NN makes it interesting to train the network simultaneously on perturbations of the true reward function in order to learn a more stable policy that might work well for even more reward settings.\n\nThe scientific quality of the article is very high. There is hardly any typo. I appreciate a lot the critic discussion of limitations, this is far above the rather low scientific standard in ML. I could not check the entire proofs of the appendix, what I read seemed solid. \n\nGood article! I am curious to follow up on the future development of the robust DQN variant.", "weaknesses": "- I did not enjoy reading the article very much as I was pushed into first reading other articles to get a rough understanding of what is going on. Even reading the basis of the present article ([17], [40]) was not enough. To get an idea why $T^*$ is considered one needs to go all the way back to [20], and even further. It feels a bit like a community wants to stay among each other, the usual RL researcher is excluded by the style of writing. I would suggest to completely skip the discussion in the end (almost a page) and instead use the space to explain the reader what the technique is about and why the theoretical estimate naturally lead to Algorithm 1.\n- The assumptions are drastic and should be discussed more clearly. I guess the authors have bandit background and skip discussions of issues that are typical for bandits. In particular, assuming knowledge of rewards and/or the reward gaps. While this is not unusual in bandits it is very much in RL. I am perfectly fine with such theoretical results in particular, as the authors implemented an educated guess algorithm in the deep setting that addresses this issue with the reward gaps.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and the time spent on our paper. Below, we address each concern in detail.\n\n>I was pushed into first reading other articles to get a rough understanding of what is going on\n\nWe acknowledge  the current format assumes familiarity with related literature. We will add a background section to make the technique accessible to a broader audience.\n\n> How do you compute $U$ in Algorithm 1 without knowing the rewards gaps? \n\nWe briefly explain the procedure in lines 178-182 and we do not assume knowledge of the gaps in the algorithm. \n\nWe use the current estimate of the model $M_t$ and the set of rewards to compute the sub-optimality gaps. We use the data gathered up to time $t$ to estimate the transition function $P_t$ and perform value iteration for each reward to find the sub-optimality gaps. These estimates are used in place of the true gaps to compute $U$.\n\nThis technique is known as \"certainty-equivalence\" principle, meaning that we use the current estimates as if they were exact when computing $\\omega_t^\\star$. Note that, as more data is gathered, the estimate of the transition function improves, and $\\omega_t^\\star$ tends to $\\omega^\\star$.\n\n> I think the algorithms are not sufficiently explained. In the tabular case $M_t$ should be explained in more detail\n\nCurrently, the main text provides a brief description: lines 178-182 outline how $M_t$ is updated by estimating the transition function $P_t$, and lines 183-189 explain how to compute the instance-dependent quantities to determine $U$.\n\nIn the revised manuscript we will provide a more detailed explanation of the algorithm.\n\n>  Why is there no dependence on $\\alpha$ in the theoretical results?\n\nThe main theoretical results are asymptotic in $\\delta$, causing $\\alpha$ dependence to vanish. Intermediate results do show $\\alpha$ dependency (e.g., see Remark C.2, line 1099).\n\n> The use of Borel-Cantelli in the proofs is not correct as it is. The events are not independent\n\nWe rely on Observation 1 in [70] (in the text of the proof there is a typo, since there is no Lemma 4 in [70]). We use the  fact that there exists another stochastic process (the one provided by the forcing policy) such that the sum of the probabilities with which action $a$ is chosen is infinite. This sum lower bounds the sequence of probabilities of selecting action $a$ and satisfies the independence conditions required by the Borel-Cantelli Lemma.\n\n> What is the connection of Theorem 3.1 and 3.3?\n\nBoth theorems are for MDPs. Deriving Theorem 3.1 requires additional steps compared to the bandit setting, and the optimal allocation $\\omega_{opt}$ must satisfy the forward Chapman Kolmogorov equation.\n\nTo explain how the two theorems are connected, we consider an information-theoretical approach.\n\nFirstly, note that the optimal exploration strategy induces the stationary distribution $\\omega_{opt} =\\arg\\sup_{\\omega \\in \\Omega(M)} \\inf_{r,M'\\in Alt(M_r)} \\mathbb{E}\\_{(s,a)\\sim\\omega}[{\\rm KL}\\_{M|M'}(s,a)]$, and $T^\\star$ can be interpreted as the average amount of information extracted per time-step from the MDP at stationarity under $\\omega_{opt}$.\n\nSecondly, as $T^\\star$ is a hard non-convex optimization problem, we instead use $U^\\star$ in the design of our algorithm.\n\nAs more data is collected, the estimate of the model $M_t$ tends to $M$, and one can show that $\\omega_t^\\star$ approaches the optimal stationary distribution $\\omega^\\star$. Asymptotically, the algorithm will visit the MDP according to $\\omega^\\star$, so the amount of information extracted approaches $U^\\star$. Hence, with a proper stopping rule, this is roughly  why, as $\\delta \\to 0$, the sample complexity of the algorithm approaches the  value $U^\\star$ in Theorem 3.3. \n\n> You mention an upper bound for $U$, which has an additional $1/\\Delta^2$ compared to the theoretical bound. Is there a better  bound?\n\nPlease note that also $U$ has a dependency on $1/\\Delta_r^2$. In general, we believe that it is hard to find a better dependency in the gaps that does not depend on some specific property of the MDP. \n\n>Is there any theoretical understanding on how $\\tau$ scales in the number of rewards?\n\nThe result in Theorem 3.1 indicates that the scaling depends on the \"worst\" reward in the considered set. Practically, according to $U^\\star$, the sample complexity is dictated by the  minimum sub-optimality gap $1/(\\inf_{r\\in {\\cal R}} \\Delta_r^2)$ (and $\\tau$ will scale as $U^\\star \\ln(1/\\delta)$). This scaling is consistent with the scaling obtained in classical reward-free exploration, see  for example [17; A]. In [A], the authors show a similar result in a different setting, where the sample complexity also scales according to the worst reward (with a similar $1/\\Delta^2$ scaling, though their gap definition is slightly different). \n\n> How does your algorithm compare to just train for one reward after the other? Typically card pole plots show the number of episode, not the number of steps. Does your algorithm help for generalisation? \n\nThe optimization problem formulated to compute $\\omega^\\star$ shows that the scaling depends on the worst-case reward in the set (i.e., the reward with the minimum sub-optimality gap) rather than the number of rewards. Consequently, a sequential exploration process would generally not be optimal (since that would scale according to the number of rewards). Such an approach would likely increase training time and associated costs. \n\nRegarding the Cartpole swing-up experiments, each episode may have a different number of steps. Further note that we use a modified version of the Cartpole swing-up problem,  designed to assess the exploration properties of RL algorithms.\n\nLastly, with a sequential training the ability to generalize may be limited, especially for very different rewards, reducing the effectiveness of such an approach.\n\n**Other ref.**\n\n[A]. Jedra et al. \"Nearly optimal latent state decoding in block mdps.\" AISTATS 2023.", "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:
We would like to thank the reviewers for their comprehensive  reviews.  We are pleased that you recognize the scientific quality and the rigor of our theoretical and empirical contributions.

Our work strives to bring a comprehensive and well-balanced analysis, bridging both theoretical analysis and practical methods.  Our work provides not only fundamental theoretical results in the tabular setting but also practical extensions to deep reinforcement learning (DeepRL). 
The numerical experiments for both the tabular and DeepRL cases are conducted on  environments designed to be challenging for exploration, highlighting the effectiveness of our approach across different settings.

Lastly, we present a real-world application in Section D.3 of the appendix, where we apply DBMR-BPI to a radio network control problem using an industry-level network simulator. This example emphasizes the relevance and applicability of our contributions.

We hope our responses clarify and address the reviewers' concerns, and we are committed to revising the paper based on their feedback in our final submission.

Meta-review: This paper presents a comprehensive study on the Multi-Reward Best Policy Identification (MR-BPI) problem in Reinforcement Learning (RL), where the objective is to identify the best policy for a set of rewards with minimal sample complexity and high confidence. The authors provide an instance-specific lower bound on the sample complexity required by any Probably Correct (PC) algorithm and introduce a convex approximation to design efficient, sample-optimal algorithms. The proposed algorithms, MR-NaS for tabular settings and DBMR-BPI for Deep RL, are evaluated on both synthetic and real-world tasks, showing competitive performance, particularly in hard-exploration environments.

Pros & Cons:
+ A significant theoretical advancement by deriving an instance-specific lower bound and extending classical RL concepts to the multi-reward setting.
+ Algorithm design is supported by both theory and experiments.

- Some reviewers expressed concerns that the environments used for the deep RL experiments, such as Cartpole swing-up and DeepSea, maybe too simplistic.
- It may need more clarification for readers to understand the dense details.

Summary:
The majority of reviewers appreciate the depth and rigor of the paper’s contributions, particularly in advancing theoretical understanding and proposing novel algorithms in the multi-reward RL setting. However, concerns about the clarity of the presentation and the complexity of the experimental validation were raised. Overall, the AC recommends acceptance of the paper.
Decision: Accept (poster)