Multi-Reward Best Policy Identification

Authors: alessio  russo
filippo  vannella
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:24:38

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.

Main paper: 
 introduction: 
 Reinforcement Learning (RL) provides a powerful framework for sequential decision-making, which has achieved a number of breakthroughs in a wide range of applications, including mastering video games [1, 2] , accelerating algorithm design [3] , optimizing fusion control systems [4, 5] , and enhancing autonomous robotic control [6, 7, 8] .Rewards are a critical aspect of formulating an RL problem. Yet, designing a reward function can require numerous iterations of reward engineering [9] . Furthermore, in many practical scenarios, the reward signal is not necessarily a scalar, and the agent may seek to optimize performance across a set of reward functions [10, 11] (e.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, a setting we refer to as Multi-Reward Best Policy Identification (MR-BPI). This setting is 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 a 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, as 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 problem remains relatively unexplored in the current RL literature. Closely related settings are 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.com/rssalessio/Multi-Reward-Best-Policy-Identification 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 multi-objective RL, the agent optimizes over multiple (potentially conflicting) rewards, with the goal of identifying a Pareto frontier of optimal policies. While reward-free RL is the closest to our setting, exploration for any possible reward is unlikely to occur in practical problems. On the other hand, unsupervised RL and multi-objective RL do not directly address the multi-reward pure exploration problem -a setting we deem to be of practical use in a 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 a 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-specific 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 a 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-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 rewardfree exploration method), ID3AL [33] (a maximum entropy exploration approach) and MR-PSRL, a 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-Reward BPI), a model-free exploration algorithm for continuous-state MDPs. We assess its performance, along with RND [26] (Random Network Distillation), Disagreement [27] , and APT [29] , on hard-exploration problems from the DeepMind BSuite [36] and on link adaptation (a radio network control problem [37] ). 
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.Markov Decision Processes (MDPs). We consider discounted MDPs of the type M = (S, A, P, γ), where S is the finite state space (of size S = |S|), A is the finite action space (of size A = |A|), P : S × A → ∆(S) is the transition function, which maps state-action pairs to a distribution over states and γ ∈ (0, 1) is the discount factor. We indicate by by M r = (S, A, P, r, γ) the MDP when considering a reward r : S × A → [0, 1]. For a given reward r, we define the discounted value of a Markov policy π : S → ∆(A) to be V π r (s) = E π [ t≥0 γ t r(s t , a t )|s 0 = s], where s t+1 ∼ P (•|s t , a t ) and a t ∼ π(•|s t ). We also let V ⋆ r (s) = max π V π r (s) be the optimal value in s and, for MDPs with a unique optimal policy, we indicate it by π ⋆ r (s) = arg max π V π r (s). Similarly, we also define the action-value function Q π r (s, a) = r(s, a) + γE s ′ ∼P (•|s,a) [V π r (s ′ )]. For an MDP M r , we indicate by Π ⋆ (M r ) = {π ∈ Π d : ∥V ⋆ r -V π r ∥ ∞ = 0} the set of optimal policies in M r and Π d is the set of deterministic policies.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, 1] SA , with each coordinate i 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 R canonical = {e 1 , . . . , e SA } in R SA (with e i being the i-th vector of the canonical basis).Best Policy Identification consists of finding an optimal policy in an MDP using the least number of samples with a given confidence level for a 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 to identify an optimal policy. Interestingly, the lower bound is often formulated as an optimization problem, whose solution ω ⋆ allows us to derive an optimal exploration algorithm. In other words, the solution ω ⋆ provides the best proportion of static draws. That is, a policy following ω ⋆ matches the lower bound and is therefore optimal [20, 17] .Change of measure. The recipe to derive 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-likelihood 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] .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 r ∈ R as quickly as possible. This objective can be formalized in the δ-Probably-Correct (δ-PC) framework [51, 22] , where the learner interacts with the MDP until she can output an optimal policy with confidence 1δ. Contrarily to the classical BPI framework, that solely considers a single reward, here we are interested in algorithms that identify a best policy for all rewards in R.Algorithm. Formally, an algorithm consists of (i) an exploration strategy (a.k.a. sampling rule), (ii) a stopping rule τ and (iii) an estimated optimal policy πτ,r , for any reward r ∈ R. At each time step t, the algorithm observes a state s t , it selects an action a t , and then observes the next state s t+1 ∼ P (•|s t , a t ). We denote by P (resp. E) the probability law (resp. expectation) of the process (Z t ) t , where Z t = (s t , a t ). We indicate by F t = σ({Z 0 , . . . , Z t }) the σ-algebra generated by the random observations made under the algorithm up to time t in the exploration phase. For such algorithm, we define τ to be a stopping rule w.r.t. the filtration (F t ) t≥1 . This stopping rule τ simply states when to stop the exploration phase. At the stopping time τ the algorithm outputs an estimate πτ,r of the best policy for any given reward r ∈ R using the collected data. We focus on δ-PC algorithms, according to the following definition, and we impose a few mild assumptions. Definition 2.1 (δ-PC Algorithm). We say that an algorithm is δ-PC if, for any MDP M , it outputs (in finite time) an optimal policy for any reward r ∈ R with probability at-least 1δ, i.e., P[τ < ∞, (∀r ∈ R, πτ,r ∈ Π ⋆ (M r ))] ≥ 1δ. Assumption 2.1. (I) M ∈ M, where M is the set of communicating MDPs [52] with a unique optimal policy for every r ∈ R ; (II) M is aperiodic under a policy that assigns a positive probability to all actions in every state; (III) for all r ∈ R there exists a model P ′ such that P (•|s, a) ≪ P ′ (•|s, a) for all (s, a), and Π ⋆ (M r ) ∩ Π ⋆ (M ′ r ) = ∅, where M ′ r = (S, A, P ′ , r, γ) and for any two measures (µ, λ), µ ≪ λ denotes absolute continuity of µ w.r.t. λ.Assumptions (I)-(II) 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 ∈ R. For example, this occurs when the reward is identical in all state-action pairs (therefore all actions are optimal). 
best policy identification with a set of rewards: 
 In this section, we investigate the MR-BPI problem, i.e., how to optimally explore an MDP to derive the best policy for any reward in R. In the first subsection, we derive a sample complexity lower bound for any δ-PC algorithm. Later, in the second subsection, we present MR-NaS, a δ-PC algorithm inspired by NaS [17] with asymptotic optimality guarantees.In the next theorem, we state an instance-specific lower bound on the sample complexity of any δ-PC algorithm. This bound provides a fundamental limit on the performance of any δ-PC algorithm and guides the design of optimal exploration methods for MR-BPI.To state the bound, we indicate by ω ∈ R SA the allocation (or exploration policy), and by ω(s, a) the corresponding frequency of visit of a state-action pair (s, a); we introduce the set of confusing models Alt r (M ) for M r as the set of MDPs that are statistically similar to the original model M r , but admit a different set of optimal policies under r. Specifically, we let Alt r (M ) := {M ′ : M ≪ M ′ , Π ⋆ (M r ) ∩ Π ⋆ (M ′ r ) = ∅}, where M ≪ M ′ if for all (s, a) we have P (•|s, a) ≪ P ′ (•|s, a). Theorem 3.1. Let δ ∈ (0, 1/2). For any δ-PC algorithm we have lim inf δ→0EQUATIONwith KL M |M ′ (s, a) := KL(P (•|s, a), P ′ (•|s, a)) and Ω(M ) := {ω ∈ ∆(S × A) : a ω(s, a) = s ′ ,a ′ P (s|s ′ , a ′ )ω(s ′ , a ′ ), ∀s ∈ S}.Discussion. The proof of the theorem is presented in app. B.1. The result, obtained by classical change-of-measure arguments [20] , extends the corresponding lower bound in the case of a single reward [17] .The quantity T ⋆ (M ) is referred to as the characteristic rate and is a non-convex optimization problem. It can be interpreted as a zero-sum game between an agent choosing a distribution (or allocation) ω, and an opponent choosing a 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 a stationary distribution over states and actions that takes into account the transition dynamics, and, interestingly, the optimal solution ω opt to the optimization problem in eq. ( 1) also defines the optimal exploration strategy (as π exp (a|s) = ω opt (s, a)/ b ω opt (s, b)).In principle, with access to an optimization oracle that solves (1), we 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 T ⋆ (M ) is in general a non-convex problem [16] . Instead, as in previous works [16, 17, 53] , we focus on deriving a convex upper bound U ⋆ (M ) of T ⋆ (M ), which we call relaxed characteristic rate, that guarantees that we are still identifying the optimal policy at the cost of an increased sample complexity. We focus on the case of a finite set of user-specified rewards. The extension to externally provided reward signals and the consideration of a continuous set of rewards are detailed in the appendix (app. B.3 and app. B.4, respectively).To define the relaxed characteristic rate, we state a few definitions of problem-dependent quantities for MDPs. We let ∆ r (s, a):= V ⋆ r (s) -Q ⋆ r (s, a) be the sub-optimality gap in (s, a), Var r (s, a) := E s ′ ∼P (•|s,a) [(V ⋆ r (s ′ ) -E ŝ∼P (•|s,a) [V ⋆ r (ŝ)]] be the variance of the optimal value function in the next state, and MD r (s, a):= ∥V ⋆ r -E s ′ ∼P (•|s,a) [V ⋆ r (s ′ )]∥ ∞ be the maximum deviation starting from (s, a). Additionally, for a given reward r ∈ R we also let ∆ r := min s,a̸ =π ⋆ r (s) ∆ r (s, a), Var r := max s,a∈A(s;Mr) Var r (s, a) and MD r = max s,a∈A(s;Mr) MD r (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 T (ω; M ) that holds for all possible allocations ω ∈ ∆(S × A), whereEQUATIONTheorem 3.2. For any allocation ω ∈ ∆(S × A) we have that T (ω; M ) ≤ U (ω; M ), whereEQUATIONwhereH r = min 139(1+γ) 2 (1-γ) 3 , max 16γ 2 Varr(1+γ) 2 (1-γ) 2 , 6γ 4/3 MD 4/3 r (1+γ) 4/3 (1-γ) 4/3. We define the optimal value U ⋆ (M ) = U (ω ⋆ ; M ), where ω ⋆ = arg inf ω∈Ω(M ) U (ω; M ) is the optimal allocation w.r.t. U ⋆ (M ).Discussion. In the above theorem (the proof can be in found in app. B.2), the various instancespecific quantities Var r (s, a), ∆ r (s, a), H r and ∆ r are computed with respect to M . The result extends the corresponding upper bound in [17, 53] .We make some observations to clarify the key aspects of this result. First, U (ω; M ) is convex in ω for a finite set of rewards. Hence U (ω; M ) can be computed efficiently by using convex optimization methods (we report the runtime of our simulation in app. E.1).For a 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, it is sufficient to optimize over a 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 ω ⋆ guarantees that we identify the optimal policy, at the cost of an increased over-exploration [53] , since U ⋆ (M ) ≥ T ⋆ (M ). The cost of this over-exploration is limited, since by plugging ω(s, a) = 1/(SA) one can see thatU ⋆ (M ) = O SA (1-γ) 3 min r∈R ∆ 2 r; note that the dependency in (1γ) -1 can be improved whenever the maximum deviation is smaller than (1γ) -1 . Lastly, observe that the dependency ∆ 2 r ω(s ′ , π ⋆ r (s ′ )) in the second term in eq. ( 3) can be improved to ∆ r (s, a) 2 ω(s ′ , π ⋆ r (s ′ )) as in [53] .In this section we devise MR-NaS, an adaptation of MDP-NaS [17] to MR-BPI for a finite set of rewards. The algorithm consists of (1) an exploration policy (a.k.a. sampling rule) and (2) a 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, as in [16, 17, 53, 20] , is that the exploratory policy should follow the allocation ω ⋆ = arg inf ω∈Ω(M ) U (ω; M ), as this will yield a sample-efficient exploration policy. However, as the model M is unknown, we cannot directly compute ω ⋆ . Alternatively, we employ the certainty-equivalence principle, and use the current estimate of the model M t in place of the true model M to compute the allocation ω ⋆ t = arg inf ω∈Ω(Mt) U (ω; M t ), whereEQUATIONIn the above expression, for any t ≥ 1, the estimate M t is completely defined by the empirical transition function P t :EQUATIONwhere N t (s, a) is the number of visits for each state-action pair up to time t (sim. N t (s, a, s ′ ))). Letting V ⋆ t,r denote the optimal value in M t,r := (M t , r) (sim.EQUATIONs)} is the set of optimal actions for reward r in state s (and O c t,r (s) is the complement), MD t,r (s, a) = ∥V ⋆ t,r (s) -E s ′ ∼Pt(•|s,a) [V ⋆ t,r (s ′ )]∥ ∞ is the maximum deviation starting from (s, a)Update Nt(st, at), Mt and set t ← t + 1. 8: end while Output: an optimal policy π⋆ r,τ for a given reward r.forM t,r , Var t,r (s, a) = E s ′ ∼Pt(•|s,a) [(V ⋆ t,r (s ′ ) -E ŝ∼Pt(•|s,a) [V ⋆ t,r (ŝ)]) 2 ]is the corresponding nextstate variance of the optimal value for M t,r , and ∆ t,r (s, a) = V ⋆ t,r (s) -Q ⋆ t,r (s, a). These quantities can also be used similarly to compute H t,r (i.e., H r computed w.r.t. M t,r ).At the same time, the sampling strategy must ensure that the estimated model M t converges to M . To that aim, we mix the computed allocation with a forcing policy π f , ensuring that each state-action pair is sampled infinitely often. We use the forcing policy π f,t(•|s) = softmax (-β t (s)N t (s, •)) with β t (s) = β log(Nt(s)) maxa |Nt(s,a)-min b Nt(s,b)| , β ∈ [0, 1]and (softmax(x)) i = e xi / j e xj for a vector x. This choice encourages to select under-sampled actions for β > 0, while for β = 0 we obtain a uniform forcing policy π f,t (a|s) = 1/A. In [16] , the authors use an exploration factor ϵ t = t -1/(m+1) , 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 ϵ t = 1/ max(1, N t (s t )) α , with N t (s) = a N t (s, a) and α ∈ (0, 1], which only depends on the number of states visits. This change requires a modification of the proofs in [17] , since now ϵ t depends also on the number of visits of s t . Finally, to ensure convergence of ω ⋆ t → ω ⋆ , we simply require that α + β ≤ 1.Stopping rule. The stopping rule (line 3) is defined through the relaxed generalized likelihood ratio term tU (N t /t; M t ) and a threshold function β(N t , δ). The term N t /t simply refers to the rates of visit of each state-action pair, while M t is the current estimate of the MDP (based on ( 5)). The threshold function is selected to guarantee that the algorithm is δ-PC (the proof is in app. C.4). .Then, the stopping rule τ := inf{t ≥ 1 : tUEQUATIONPutting everything together. Following our discussion, MR-NaS uses the estimate M t to compute the allocation ω ⋆ t = arg inf ω∈Ω(Mt) U (ω; M t ) (line 4). To stabilize the exploration, we use an averaged allocation to obtain π ⋆ t = (1/t) t n=1 ω ⋆ n (similarly to the C-navigation rule in [20, 17] ). Lastly, we mix π ⋆ t with a forcing policy π f,t (line 5). The samples observed from the MDP are then used to update the number of state action visits and the estimate of M t . 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-NaS with the stopping rule in prop. 3.1 satisfies: (i) it stops almost surely andP lim sup δ→0 τ log(1/δ) ≤ U ⋆ (M ) = 1; (ii) E[τ ] < ∞ and lim sup δ→0 E[τ ] log(1/δ) ≤ U ⋆ (M ).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. More precisely, we consider the problem of correctly estimating the optimal policies in a convex set of rewards [0, 1] SA as well as the optimal policies of the canonical basis, with discount factor γ = 0.9.We consider R = R canonical ∪ R rnd , where R rnd = {R 1 , . . . , R 30 } consists of 30 reward vectors uniformly sampled from [0, 1] SA , 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 R canonical is sufficient to identify the optimal policies in a continuous set.We run each algorithm for T = 50 • 10 3 steps, and we report the fraction of misidentified policies e t,r at time step t and for reward r. Fig. 1 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.1 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 a model-based method, secondly there is no closed-form solution to arg inf ω∈Ω U ⋆ (ω; M ). To circumvent these issues, we adapt the DBMF-BPI algorithm from [53] , where the authors propose DBMF-BPI, 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 ω∈∆(S×A) U ⋆ (ω; 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. Nevertheless, 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.Hence, we propose DBMR-BPI, an extension of DBMF-BPI to the multi-reward setting with a 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-values1 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 a one-hot encoding of the chosen reward, but we experienced this change to be less effective. and compute allocation ωt using DBMF-BPI with reward r.Sample at ∼ ωt(st, •) and observe st+1 ∼ P (•|st, at).Add transition (st, at, r1,t, . . . , rR,t, st+1) to the buffer D, with ri,t = ri(st, at), i = 1, . . . , |R|.Train the ensemble θ according to DBMF-BPI and update estimates ∆t,r for each reward r ∈ R. 7: end for 2. We explore according to the difficulty of the reward function. Specifically, we explore a reward r with probability ∝ 1/∆ 2 t,r , 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 a reward r ∼ R to explore, and apply DBMF-BPI on this reward.The main steps of the algorithm are outlined in Alg. 2, and all the details can be found in app. E.1.We evaluate the performance of DBMR-BPI and compare it with state-of-the-art method in unsupervised 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), Disagreement [27] and APT [29] . The exploration procedure of these methods is 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 [55, 53] , we evaluate on different challenging environments from the DeepMind behavior suite [36] : the Cartpole swing-up problem and a stochastic version of 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.3.1. Lastly, we also evaluate the exploration quality of DBMR-BPI both on a 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 a 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 a specific position x 0 . 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(θ) > k/20, (2) | θ| ≤ θ 0 , and (3) |xx 0 | ≤ 1k/20, where θ 0 is a fixed constant and k is an integer representing the difficulty. We considered 5 values of x 0 linearly spaced in [-1.5, 1.5], so that |R| = 5. To assess DBMR-BPI's capacity to generalize on unseen rewards, we uniformly sample 5 additional values of x 0 in the same interval that are not used during training, and we denote them by R rnd . EQUATIONr i ∈ R or r i ∈ R rnd ).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).In tab. 1 we present results for two levels of difficulty k ∈ {3, 5} and different training steps T . The table presents statistics for the random variable X i = 1 T T t=1 1 ri(st,at)>0 , where i is the i-th 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 R ({X i }) (sim. the others metrics) indicates the arithmetic mean of {X i } i over the rewards. We average results across 30 seeds.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 R to explore, we see better performance when collecting rewards from R rnd (which are not used by DBMR-BPI during exploration). The reason may be that some rewards in R, (e.g., those with |x 0 | = 1.5), are harder to learn, while it is unlikely for the random rewards to have such values of x 0 . 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. D.2.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 in the top-left corner of a grid of size N × N , and can only move diagonally, towards the bottom of the grid. In the classical setup, the agent observes a N 2 -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 = {r 1 , . . . , r N }, so that r i assigns a positive reward whenever the agent reaches column i in the last row of the grid. As in [53] , we include a small probability of the agent taking the wrong action.To assess the capacity of DBMR-BPI to collect unseen rewards, for each seed, we sampled 20 reward functions R rnd = (r ′ i ) 20 i=1 , each of dimension N (N + 1)/2 (where the i-th value corresponds to a possible position in the grid), from a Dirichlet distribution with parameter α = (α i ) i , with α i = 1/(10N ) for all i = 1, . . . , N (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. T T t=1 r i (s t , a t ) (with r i ∈ R or r i ∈ R rnd ). Values are multiplied by 100 (except the third metric for the base rewards) and rounded to the first digit. In bold statistically significant results (in parentheses we indicate the 95% confidence interval over 30 seeds).EQUATIONIn tab. 2 we show some statistics for the random variable X i = 1 T T t=1 r i (s t , a t ), that quantifies the average reward collected for the i-th reward in a specific instance. In the table GM R ({X i }) 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 [56] ), and N i=1 1 Xi=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-BPI and RND, focusing most of the time on a 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 R rnd , we see that DBMR-BPI achieves performance similar to RND, which confirms the capability of DBMR-BPI to collect reward from unseen reward functions (refer to app. D.2.2 for further details). 
discussion and conclusions: 
 Exploration in RL and Best Policy Identification. There exists a variety of exploration methods in RL [57] and DRL (see [58, 53] and references therein). Our setting is a generalization of classical single-reward BPI with fixed confidence [16, 17, 59, 60, 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 a multi-reward generalization applicable to both the tabular case and DRL, along with some technical improvements (see app. C and app. E.1). Lastly, while not directly related, in [61, 62, 63] the authors study the identification of the Pareto optimal frontier in a multi-objective bandit model, a framework yet to be explored in MDPs.Multi-Reward. There are several works considering a setting where the agent deals with multiple diverse reward signals [10, 64, 11, 31] . Shelton [10] investigates the case where an agent observes a vector of rewards from multiple sources at each time step. The author proposes an algorithm attaining a Nash equilibrium on the average return of each source. In [64] 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. [11] , where they investigate multi-reward 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, 65, 31] , a technique with various applications in areas such as molecular design [66] and pricing strategy optimization [67] . In this framework, the agent seeks to optimize multiple rewards simultaneously. To the best of our knowledge there are no work investigating the exploration problem in Multi-Objective RL, a 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, 68, 69, 23, 70] , where the agent learns behaviours without a specific reward. For example, Jin et al. [21] study reward-free RL in the tabular episodic case to identify ε-optimal policies for any possible reward. They provide a lower bound on the length of exploration phase scaling as Ω(H 2 S 2 A/ε 2 ) and devise an algorithm nearly matching it of order Õ(H 5 S 2 A/ε 2 ). This bound was improved in [22] and [68] , where the authors propose the RF-UCRL and RF-Express algorithms for episodic reward-free RL. On a similar line, the authors of [23] focus on an RFE setting where the minimal sub-optimality gap is a known quantity, and provide an algorithm with reduced sample complexity. Another relevant RFE framework is maximum entropy exploration [32, 33, 24, 71] , which studies the problem of state entropy maximization. This type of exploration is particularly useful for offline RL [72] since it is well know that the coverage of the state space characterizes the sample complexity of the problem [73, 74] . Lastly, the reward-free 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 a self-supervised manner [75, 76, 77] ), some RFE techniques can be impractical in 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 determining the best policies for a 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 multi-reward 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 a dataset that performs well across different rewards.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: For each experiment we reported in 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 or 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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 is 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 as 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: A Limitations and Broader Impact Limitations. We discuss some limitations of the current work and highlight major directions of improvement.• Tabular MDP. The current theoretical analysis only applies to tabular MDPs, and may not necessarily extend to continuous domains in a similar way. • Tracking of the allocation. In MR-NaS we employ a probabilistic policy, which may lead to worse tracking performance compared to 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 ω ⋆ t to ω ⋆ . • Lazy updates. MR-NaS computes an allocation ω ⋆ t = arg inf ω∈Ω(Mt) U (ω t ; M t ) at each time step, which could be computationally prohibitive for large-dimensional problems. A possible way to address this issue is to use "lazyness" [78] , i.e., to compute ω ⋆ t only at time steps t ∈ T , where T ⊂ N prescribes the allocation update schedule (see [78] ).• Scaling of the rewards for DBMR-BPI. The method that we introduce for exploration in deep-RL, DBMR-BPI, explores according to a 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 in DBMF-BPI is A • |R|. However, our experiments with an ensemble size of 20 and A • |R| ≈ 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 DBMR-BPI. In this paper, we analyze DBMR-BPI within a finite action space. Although continuous action spaces are equally important, extending the algorithm to such spaces requires additional work. It is currently unclear how to 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 a unique optimal policy. This assumption is common in the BPI literature [18, 16, 17, 53, 20] . Addressing MDPs with multiple optimal policies or identifying ε-optimal policies necessitates the use of more complex overlapping hypothesis tests [79] . 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 an even greater challenge. In that sense, we can provide some insights on the main problems and potential solutions:-In presence of multiple optimal policies, one may be interested in ensuring that at the stopping time we have Π ⋆ (M τ,r ) ⊆ Π ⋆ (M r ) for all rewards r ∈ R. This guarantees that we identify a 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 ∈ Alt(M t ) 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 a union, or intersection, over the optimal policies in 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 r (s) in the decomposition, where O r (s) = {a :Q ⋆ Mr (s, a) = V ⋆ Mr (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 in decision-making systems in healthcare, finance, and autonomous vehicles, where biases or errors 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.In this appendix we first prove thm. 3.1. In 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, in the last subsection, we present some useful lemmas.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 ω ∈ ∆(S × A)), while the extension to 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 δ-PC event and a data processing inequality yields the lower-bound.Log-likelihood ratio. Consider the MDP M = (S, A, P, γ) and an alternative model M ′ = (S, A, P ′ , γ) such that P ≪ P ′ . The log-likelihood ratio between M and M ′ of a sequence of observations (z 0 , z 1 , . . . ), where z i = (s i , a i ), is defined asL t = t n=1 log P (s n |z n-1 ) P ′ (s n |z n-1 ) ,To simplify the analysis, letL s,a t := t n=1 1 {Zn-1=(s,a)} log P (s n |s, a) P ′ (s n |s, a) = Nt(s,a) n=1 log P (y n |s, a) P ′ (y n |s, a) ,where y n denotes the next state after the pair (s, a) has been visited for the n-th time (s, a) and N t (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 t = s,a L s,a t . Taking the expectation over the measure induced by M , we haveE M [L t ] = E M t n=1 log P (s n |z n-1 ) P ′ (s n |z n-1 ),where E M [•]is the expectation under the probability measure induced by a model M (sim. P M [•]). Then, at the stopping time τ we haveE M [L τ ] = s,a E M [L s,a τ ] , = s,a E M   Nτ (s,a) n=1 log P (y n |s, a) P ′ (y n |s, a)   , = s,a E M ∞ t=0 1 {Nτ (s,a)≥t} log P (y t |s, a) P ′ (y t |s, a) .Since X s,a n := log P (yn|s,a)P ′ (yn|s,a) is independent of F n-1 , and since {N τ (s, a) ≤ n -1} c = {N τ (s, a) ≥ n} ∈ F n-1 we have that E M [L τ ] = s,a ∞ t=0 P M [N τ (s, a) ≥ t]KL M |M ′ (s, a), = s,a E M [N τ (s, a)]KL M |M ′ (s, a),where KL M |M ′ (s, a) = KL(P (s, a), P ′ (s, a)). δ-PC argument. Consider a δ-PC algorithm, and define the eventE = {∀r ∈ R, πτ,r ∈ Π ⋆ (M r )} and observe that E c = {(∃r ∈ R, πτ,r / ∈ Π ⋆ (M r ))}. Let Alt(M ) = {M ′ ∈ M|∃r : Π ⋆ (M ′ r ) ∩ Π ⋆ (M r ) = ∅}, which can be rewritten as Alt(M ) = ∪ r∈R Alt r (M ), where Alt r (M ) = {M ′ ∈ M|Π ⋆ (M ′ r ) ∩ Π ⋆ (M r ) = ∅}.In view of the transportation lemma in [80] , for any M ′ ∈ Alt(M ) we can lower bound the expected log-likelihood at the stopping time τ asE M [L τ ] = s,a E M [N τ (s, a)]KL M |M ′ (s, a) ≥ kl(P M [E], P M ′ [E]) ≥ kl(1 -δ, δ).As the inequality above holds for all M ′ ∈ Alt(M ), and by optimizing over the set of confusing model, we have infM ′ ∈Alt(M ) s,a E M [N τ (s, a)]KL M |M ′ (s, a) = min r∈R inf M ′ ∈Altr(M ) s,a E M [N τ (s, a)]KL M |M ′ (s, a) ≥ kl(1 -δ, δ). Sample complexity. By letting ω(s, a) = E M [N τ (s, a)]/E M [τ ],and optimizing over all possible allocations ω ∈ Ω, we haveE M [τ ] max ω∈∆(S×A) min r∈R inf M ′ ∈Altr(M ) s,a ω(s, a)KL M |M ′ (s, a) ≥ kl(1 -δ, δ).Finally, taking the limit as δ → 0 yields the result.The extension from the generative model to the forward model can be done as in [17, Proposition 2] .Since the characteristic time T ⋆ (M ) is a non-convex optimization problem [16] , we focus on deriving a convex upper bound of T ⋆ (M ) that is convex for a finite set 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 a convex upper bound of T (ω; M ) that holds for all possible allocations ω ∈ ∆(S × A). Recall the definition of T (ω; M )T (ω; M ) -1 := inf r∈R inf M ′ ∈Alt(Mr) s,a ω(s, a)KL M |M ′ (s, a) .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 (ω; M ) to the sub-optimality gaps of the MDP, and formulate the problem of computing the relaxed characteristic rate as a convex problem.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 ∈ R satisfiesEQUATION) where Alt sar (M ) := {M ′ ∈ Alt π r (M ) : Q π M ′ r (s, a) > V π M ′ r (s)} is the set of confusing models for (s, a, r, π).Step 2: relating the KL divergence to the sub-optimality gaps Using lem. B.1, we can convexify the characteristic rate and related the KL-divergence terms with the sub-optimality gaps ∆ r (s, a). The goal is to 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 begin by decomposing the set of confusing models. After that, we relate the sub-optimality gaps to the inner product between the transitions and the value functions. Using this relation, we can lower bound the KL terms in T (ω; M ). Finally, through an optimization step, we establish the upper bound. In the proof, we indicate by V π Mr the value of a policy π in MDP M r , and similarly Q π Mr .Decomposition. Fix r, s, a ̸ = π ⋆ r (s). As in [16] , we combine the condition Qπ ⋆ r M ′ r (s, a) > V π ⋆ r M ′ r (s) with the fact that Q ⋆ Mr (s, a) + ∆ r (s, a) = V ⋆ Mr (s) to obtain that ∆ r (s, a) < V ⋆ Mr (s) -Q ⋆ Mr (s, a) + Q π ⋆ r M ′ r (s, a) -V π ⋆ r M ′r (s). This is similar to Eq. ( 5) in [16] . Next, let ∆P (s, a) = P M ′ (s, a) -P M (s, a), where P M (s, a) (sim. P M ′ (s, a)) is a vector of dimension S representing the distribution of the next state given (s, a). Further define the vector difference between the value in M r and M ′ r :∆V π ⋆ r = V π ⋆ r M ′ r (s 1 ) -V ⋆ Mr (s 1 ) . . . V π ⋆ r M ′ r (s S ) -V ⋆ Mr (s S ) ⊤ .Then, letting 1(s) = e s be the unit vector with 1 in position s, we findEQUATIONHence, the condition Qπ ⋆ r M ′ r (s, a) > V π ⋆ r M ′r (s) is equivalent to the inequality in (8) . This inequality only involves the pairs {(s, a), ∪ s ′ (s ′ , π ⋆ r (s ′ ))}, and therefore the infimum overAlt sa (M r ) of s,a ω(s, a)KL M |M ′ (s, a) is a model M ′ satisfying KL M |M ′ (s, a) =0 over all the other stateaction pairs. Hence, using lem. B.1, and the reasoning above, we can writeT (ω; M ) -1 = min r∈R min s,a̸ =π ⋆ r (s) inf M ′ ∈Alt π ⋆ r sar (M ) ω(s, a)KL M |M ′ (s, a) + s ′ ω(s ′ , π ⋆ r (s ′ ))KL M |M ′ (s ′ , π ⋆ r (s ′ )) .Sub-optimality gaps. We now relate the KL-terms to the sub-optimality gaps, similarly as in [53, 16] . For any state s and action a ̸ = π ⋆ r (s), we write each of the terms (8) as a fraction of ∆ r (s, a)using {α i } 2i=1 , which are real values satisfying2 i=1 α i > 1: α 1 ∆ r (s, a) = γ|∆P (s, a) ⊤ V π ⋆ r Mr |, α 2 ∆ r (s, a) = (γP M ′ (s, a) -1(s)) ⊤ ∆V π ⋆ r .For the first term, we obtain(α 1 ∆ r (s, a)) 2 = γ 2 |∆P (s, a) ⊤ (V π ⋆ r Mr -E s ′ ∼P (•|s,a) [V π ⋆ r Mr (s ′ )])| 2 , ≤ γ 2 ∥∆P (s, a)∥ 2 1 MD r (s, a) 2 , ≤ 2γ 2 KL M |M ′ (s, a)MD r (s, a) 2 ,where we applied Pinsker inequality. Therefore, we can writeKL M |M ′ (s, a) ≥ α 2 1 ∆ r (s, a) 2 2γ 2 MD r (s, a) 2 =:B1,r(s,a)For the second term in (8) we have ∥γPEQUATIONEQUATIONEQUATIONOptimization. Putting all the inequalities together, we findT (ω; M ) -1 ≥ min r∈R min s,a̸ =π ⋆ r (s) inf α: i αi>1 α 2 1 ω(s, a)B r,1 (s, a) + min s ′ ω(s ′ , π ⋆ r (s ′ ))K r (s, a, α 2 ).As in [16] , the above inequalities are satisfied also when α belongs to the simplex, and in particular we also haveα 2 i ≤ α 4/3 i ≤ |α i |, for i ∈ {1, 2}.Therefore we can writeEQUATIONEQUATION)Optimizing for α, we getT (ω; M ) -1 ≥ min r∈R min s,a̸ =π ⋆ r (s) 1 ω(s, a)B r,1 (s, a) + 1 max s ′ ω(s ′ , π ⋆ r (s ′ )) max(B r,2 , B r,3 )(s, a) -1.Then, using that ∆ r ≤ ∆ r (s, a) we haveT (ω; M ) ≤ max r∈R max s,a̸ =π ⋆ r (s) H r (s, a) ω(s, a) + min(H r,1 , H r,2 ) min s ′ ω(s ′ , π ⋆ r (s ′ )), whereH r (s, a) = 2γ 2 MD(s, a) 2 ∆ r (s, a) 2 , H r,1 = max 16γ 2 Var r (1 + γ) 2 ∆ 2 r (1 -γ) 2 , 6γ 4/3 MD 4/3 r (1 + γ) 4/3 ∆ 4/3 r (1 -γ) 4/3 , H r,2 = max 139(1 + γ) 2 ∆ 2 r (1 -γ) 3 , 17γ(1 + γ) ∆ r (1 -γ) 5/2 , 14MD 4/3 r (1 + γ) 4/3 ∆ 4/3 r (1 -γ) 4/3 .Finally, as ∆ r < 1 (see [16] ) and MD max ≤ 1/(1γ), we have that H r,2 = 139(1+γ) 2 ∆ 2 r (1-γ) 3 . Henceforth, we can derive the following simplified expression for the upper boundT (ω; M ) ≤ max r∈R max s,a̸ =π ⋆ r (s) 2γ 2 MD r (s, a) 2 ∆ r (s, a) 2 ω(s, a) + H r ∆ 2 r min s ′ ω(s ′ , π ⋆ r (s ′ )),with H r = min 139(1+γ) 2 (1-γ) 3 , max 16γ 2 Varr(1+γ) 2 (1-γ) 2 , 6γ 4/3 MD 4/3 r (1+γ) 4/3 (1-γ) 4/3 . Remark B.1. Note that one can improve the dependency in ∆ 2 r in the second term of U (ω; M ) by considering ∆ r (s, a) 2 instead, as done in [53] (we did not for the sake of readability).In this subsection, we present and prove some lemmas useful for the proofs of previous results. Lemma B.2 (Lemma 4 [16] ). Consider two transition functions P, P ′ and let ∆P (s, a) = P (•|s, a)-P (•|s, a). Then, ∀r ∈ R, we have for the optimal value function V⋆ r ∈ R S we have |∆P (s, a) ⊤ V ⋆ r | 2 ≤ 8Var r (s, a)KL(P (•|s, a), P ′ (•|s, a))+4 √ 2MD r (s, a) 2 KL(P (•|s, a), P ′ (•|s, a)) 3/2 . Therefore min |∆P (s, a) ⊤ V ⋆ r | 2 16Var r (s, a) , |∆P (s, a) ⊤ V ⋆ r | 4/3 2 7/3 MD r (s, a) 4/3 ≤ KL(P (•|s, a), P ′ (•|s, a)).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 a fixed state-action pair. The second inequality comes from a simple application of the inequality a + b ≤ 2 max(a, b) to the first inequality.Lemma B.3. Consider two MDPs M, M ′ with transitions P, P ′ and a reward vector r ∈ R. Let∆V π r = V π M ′ r -V ⋆ Mr, where π ∈ Π ⋆ (M r ) and V ⋆ Mr is the optimal value in (M, r). ThenEQUATIONwhere K r := max s,a∈Or(sEQUATIONEQUATION)Proof. First, note that V ⋆ Mr = V π Mr , and hence,∆V π r = V π M ′ r -V π Mr .Since the reward is the same, we have that∆V π r = γ(P ′ ) π ∆V π r + γ∆P π V π Mr , where ∆P π = (P ′ ) π -P π . Hence, ∥∆V π r ∥ ∞ ≤ γ 1-γ ∥∆P π V π Mr ∥ ∞ .Following the same logic as in lem. B.2, and upper-bounding over all states and optimal actions we obtain MD(s, a).∥∆V π r ∥ 2 ∞ ≤ 4γ 2 (1 -γ) 2 (2Var r K r + √ 2MD 2 r K 3/2 r ),ThereforeK 1 := min ∥∆V π r ∥ 2 ∞ (1 -γ) 2 16γ 2 Var r , ∥∆V π r ∥ 4/3 ∞ (1 -γ) 4/3 2 7/3 γ 4/3 MD 4/3 r ≤ K r ,and note that 2 7/3 < 6. Secondly, we can also write∆V π r = [(I -γ(P ′ ) π ) -1 -(I -γP π ) -1 ]r. Using Lem. 5 in [16], we derive ∥∆V π r ∥ ∞ ≤ 32 log(2) 2 K r (1 -γ) 3 + 8 log(2)γK r (1 -γ) 5/2 + 2 5/4 K 3/4 r MD r (1 -γ) .Using the fact that a + b + c ≤ 3 max(a, b, c), we find the following lower bound on K rK 2 := min ∥∆V π r ∥ 2 ∞ (1 -γ) 3 288 log(2) 2 , ∥∆V π r ∥ ∞ (1 -γ) 5/2 24γ log(2) , ∥∆V π r ∥ 4/3 ∞ (1 -γ) 4/3 3 4/3 • 2 5/3 MD 4/3 r ≤ K r ,and note that 288 log(2) 2 < 139 (natural logarithm), 24 log(2) < 17 (natural logarithm) and3 4/3 • 2 5/3 MD 4/3 r < 14. Combining the two inequalities K 1 ≤ K r and K 2 ≤ K r , we conclude that max(K 1 , K 2 ) ≤ K r .As a corollary, we find an upper bound on U (ω; M ) that admits a closed form solution in the generative case (ω ∈ Ω(S × A)). Although this solution is not optimal (i.e., it does not attain the optima of U (ω; M ) under the constraint ω ∈ Ω(M )), we can consider it as a computational-efficient approximation of the optimal solution. Corollary B.1. Consider ξ ∈ ∆(S × A × R). We have that an approximate solution to arg inf ω∈∆(S×A) U (ω; M ) is given byEQUATION)with ω(s, a) = r∈R ξ(s, a, r), H r (s, a) = 2γ 2 MD r (s, a) 2 /∆ r (s, a) 2 , H ⋆ = max r∈R H r /∆ 2 r .Proof. We first derive an upper bound of U (ω; M ) and then show the it can be solved in closed form.Upper bound on U (ω; M ). Introduce the variable ξ(s, a, r) such that ω(s, a) = r∈R ξ(s, a, r), for all (s, a) ∈ S × A. By rewriting U (ω; M ) as a function of ξ, we haveU (ξ; M ) = max r∈R max s,a̸ =π ⋆ r (s) 2γ 2 MD r (s, a) 2 ∆ r (s, a) 2 r ′ ξ(s, a, r ′ ) + H r ∆ 2 r r ′ min s ′ ξ(s ′ , π ⋆ r (s ′ ), r ′ ) , ≤ max r∈R max s,a̸ =π ⋆ r (s) 2γ 2 MD r (s, a) 2 ∆ r (s, a) 2 ξ(s, a, r) + H r ∆ 2 r min s ′ ξ(s ′ , π ⋆ r (s ′ ), r) , ≤ max r∈R max s,a̸ =π ⋆ r (s) 2γ 2 MD r (s, a) 2 ∆ r (s, a) 2 ξ(s, a, r) + H ⋆ min s ′ ξ(s ′ , π ⋆ r (s ′ ), r) , = max r∈R max s,a̸ =π ⋆ r (s) H r (s, a) ξ(s, a, r) + H ⋆ min s ′ ,r ′ ξ(s ′ , π ⋆ r ′ (s ′ ), r ′ ), where we used that 1/(x + y) ≤ 1/x for x, y > 0 in the first inequality and we bounded the second term using H ⋆ = max r∈R H r /∆ 2 r in the second inequality. Finally, to lighten the notation, we let H r (s, a) = 2γ 2 MD r (s, a) 2 /∆ r (s, a) 2 .Closed-form solution. We now show that the problem at the last line of the previous equation can be solved in closed form. For the sake of notation, in the proof we denote by O r (s) = {a :Q ⋆ Mr (s, a) = V ⋆Mr (s)} the set of optimal actions in state s for the MDP M r . To distinguish ξ when the action is optimal, or not, we write ξ sra if a ∈ O r (s) and ξ(s, a, r) otherwise. After introducing the auxiliary variables t, p ≥ 0 the optimization problem can be equivalently rewritten as minEQUATIONThe Lagrangian associated to (18) is then defined asL = t + p + s,r,a∈Or(s) θ sra H ⋆ ξ sra -t + s,r,a / ∈Or(s) µ sra H r (s, a) ξ(s, a, r) -p + λ s,a,r ξ(s, a, r) -1 + s,a,r ν sra ξ(s, a, r),where θ, µ, ν are the Lagrange multipliers. Through the KKT conditions one derives ν sra = 0 for every (s, a, r), and ∂L ∂t = 0 ⇒ s,r,a / ∈Or(s)µ sra = 1, ∂L ∂p = 0 ⇒ s,r,a∈Or(s) θ sra = 1, ∂L ∂ξ(s, a, r) = 0 ⇒ λ -µ sra H r (s, a) ξ(s, a, r) 2 = 0, s, r, a / ∈ O r (s), ∂L ∂ξ sra = 0 ⇒ λ -θ sra H ⋆ ξ 2 sra = 0, s, r, a ∈ O r (s).We further find that s,a,r ξ(s, a, r) = 1, t = H r (s, a)/ξ(s, a, r) for every s, r, a / ∈ O r (s) and p = H ⋆ ξsra for every s, r, a ∈ O r (s). Hence it follows that all the ξ sra have the same value, that we denote by ξ 0 .From ξ(s, a, r) = H r (s, a)/t, to find t, observe that H r (s, a) = tξ(s, a, r) ⇒ s,r,a / ∈Or(s) H r (s, a) = t(1 -ξ sum ), where ξ sum = s,r,a∈Or(s) ξ 0 = ξ 0 |G|, with G = {(s, r, a) : s ∈ S, r ∈ R, a ∈ O r (s)}. Thus ξ(s, a, r)λ -µ sra t = 0 ⇒ t = (1 -ξ sum )λ.Use the fact that s,r,a / ∈Or(s) H r (s, a) = t(1 -ξ sum ) to find λ s,r,a / ∈Or(s) H r (s, a, r) = t 2 .From ∂L ∂ξsra = 0 find λ = θ sra H ⋆ /ξ 2 sra and ξ sra λ = θ sra p ⇒ p = ξ 0 |G|λ.Thus λ = p/ξ 0 = H ⋆ /(ξ 2 0 |G|) and H ⋆ ξ 2 0 |G| s,r,a / ∈Or(s) H r (s, a) = t 2 .Thereforeξ 0 = 1 t H ⋆ |G| s,r,a / ∈Or(s) H r (s, a)Finally, to determine t, note thats,r,a ξ(s, a, r) = 1 ⇒ s,r,a / ∈Or(s) H r (s, a) t + |G|ξ 0 = 1 Hence t = s,r,a / ∈Or(s) H r (s, a) + |G|H ε s,a̸ =π ⋆ (s) H ε (s, a).Therefore ξ(s, a, r) ∝ H r (s, a) for all s ∈ S, r ∈ R, a / ∈ O r (s) and ξ(s, a, r) ∝ H ⋆ s,r,a / ∈Or(s) H r (s, a)/|G| otherwise. The result in ω follows automatically from the definition ω(s, a) = r∈R ξ(s, a, r).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 to 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 a 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 in the next paragraph.Model. We shortly describe the MR-BPI model with random rewards, which uses a slightly different notation (w.r.t. sec. 2) to accommodate the random reward setting. In this section, we assume that the number of rewards is finite. Let Q be a set of distributions over real numbers conditioned on the state-action space. In the following, we use i ∈ {1, . . . , |Q|} as an index for the elements of Q, so that q i is the i-th reward distribution. The related problem specific-quantities and definitions are hence indexed by i, (instead of r as in sec. 2). We also denote by r qi (s, a) the expected reward for state s and action a (w.r.t. to the corresponding reward measure q i ). Similarly to the deterministic-reward setting, we assume that for all rewards i ∈ {1, . . . , |Q|} the optimal policy π ⋆ i is unique. ). We also denote by F t = σ({ζ 0 , . . . , ζ t }) the σ-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 (F t ) t≥1 . This stopping rule τ simply states when to stop the exploration phase. At the stopping time τ the algorithm outputs an estimate πτ,r of a best policy for any reward r ∈ R using the estimated MDP M τ . We focus on δ-PC algorithms, according to the following definition, and we impose a few mild assumptions.AgentSimilarly to the deterministic reward setting, the goal is to devise a δ-PC algorithm with minimal sample complexity, according to the following definition Definition B.1 (δ-PC Algorithm). We say that an algorithm is δ-PC if, for any MDP M ∈ M, P[τ < ∞, (∀i ∈ {1, . . . , |Q|}, πτ,i = π ⋆ i )] ≥ 1δ.Theorem B.1. Let δ ∈ (0, 1/2). For any δ-PC algorithm and under assumption (3), we have lim inf δ→0E[τ ] log(1/δ) ≥ T ⋆ Q (M ),whereEQUATIONwithKL Q M,M ′ = KL P |P ′ (s, a) + |Q| i=1 KL qi|q ′ i (s, a) where KL P |P ′ (s, a) = KL(P (•|s, a), P ′ (•|s, a)) and KL qi|q ′ i (s, a) = KL(q i (•|s, a), q ′ i (•|s, a)).Proof. The proof proceeds similarly to the one of the lower bound with deterministic rewards app. B.1.The main difference is that the log-likelihood ratio L t also includes the reward observations sampled from distributions in Q.Log-likelihood ratio. Let Q ∈ Q, and consider the MDP M q = (S, A, P, q, γ) and an alternative model M ′ q = (S, A, P ′ , q ′ , γ) such that P ≪ P ′ and q ≪ q ′ . The log-likelihood ratio between M and M ′ of a sequence of observations (z 0 , z 1 , . . . ), where z i = (s i , a i , r i,1 , ..., r i,s ), is defined asL t := t n=1   log P (s n |z n-1 ) P ′ (s n |z n-1 ) + i∈|Q| log q i (r i,n |z n-1 ) q ′ i (r i,n |z n-1 )  To simplify the analysis, let + |Q| i=1 log q i (x i,n |s, a) q ′ i (x i,n |s, a)   ,where y n and x i,n denotes the next state and i th reward component collected after the pair (s, a) has been visited for the n-th time (s, a) and N t (s, a) is be 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 t = s,a L s,a t . Hence, at the stopping time τ we haveE M [L τ ] = s,a E M [L s,a τ ] , = s,a E M   Nτ (s,a) n=1   log P (y n |s, a) P ′ (y n |s, a) + |Q| i=1 log q i (x i,n |s, a) q ′ i (x i,n |s, a)     , = s,a E M   ∞ t=0 1 {Nτ (s,a)≥t}   log P (y t |s, a) P ′ (y t |s, a) + |Q| i=1 log q i (x i,n |s, a) q ′ i (x i,n |s, a)     .Since W s,a n := log P (yn|s,a) P ′ (yn|s,a)+ |Q| i=1 log qi(xi,n|s,a) q ′ i (xi,n|s,a) is independent of F n-1 , and since {N τ (s, a) ≤ n -1} c = {N τ (s, a) ≥ n} ∈ F n-1 we have that E M [L τ ] = s,a ∞ t=0 P M [N τ (s, a) ≥ t]KL Q M |M ′ (s, a), = s,a E M [N τ (s, a)]KL Q M |M ′ (s, a),whereKL Q M,M ′ = KL(P (•|s, a)|P ′ (•|s, a)) + |Q| i=1 KL(q i (•|s, a), q ′ i (•|s, a)).δ-PC argument. Consider a δ-PC algorithm Alg, and define the event E = ∪ i∈{1,...|Q|} E i , whereE i = {π i,τ ̸ = π ⋆ i }.Note that, since we are considering a δ-PC algorithm, we haveP M (E) ≤ δ, Let then M ′ ∈ Alt(M ). Let Alt(M ) = {M ′ : ∃i ∈ 1, ..., |Q|, Π ⋆ (M qi ) ∩ Π ⋆ (M ′ qi ) = ∅}, and note that we can write Alt(M ) = ∪ i∈{1,...,|Q|} Alt i (M qi ), where Alt i (M qi ) = {M ′ : Π ⋆ (M qi ) ∩ Π ⋆ (M ′ qi ) = ∅}. Furthermore, we have that P M ′ (E) ≥ 1 -δ.In view of the transportation lemma in [80] , we can lower bound the previous quantity at the stopping time τ ass,a E M [N τ (s, a)]KL Q M |M ′ (s, a) ≥ kl(P M [E], P M ′ [E]) ≥ kl(δ, 1 -δ).As the inequality above holds for all M ′ ∈ Alt(M ), by optimizing over the set of confusing model, we have infM ′ ∈Alt(M ) s,a E M [N τ (s, a)]KL Q M |M ′ (s, a) ≥ kl(δ, 1 -δ).Sample complexity. By taking the minimum over the set of rewards, letting ω(s, a)= E M [N τ (s, a)]/E M [τ ],and optimizing over all possible allocations ω ∈ Ω, we haveE M [τ ] sup ω∈∆(S×A) inf M ′ ∈Alt(M ) s,a ω(s, a)KL Q M |M ′ (s, a) ≥ kl(δ, 1 -δ).Finally, taking the limit as δ → 0 yields the result.Theorem B.2. For any allocation ω ∈ ∆(S × A) we have thatEQUATIONandH i = min 139 ∆ 2 i (1-γ) 3 , max 16Vari ∆ 2 i (1-γ) 2 , 6MD 4/3 i ∆ 4/3 i (1-γ) 4/3 .Proof. The proof follows similarly to the one of thm. 3.2 but it uses a different decomposition of the analyic form ([16, Thm. 2]). We sketch its main steps below.Decomposition. We first state a decomposition result on 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 i = 1, . . . , |Q|, satisfiesAlt i (M qi ) ⊆ ∪ s,a̸ =π ⋆ i Alt π ⋆ i sai (M qi ). where Alt π sai (M qi ) := {M ′ ∈ Alt i (M qi ) : Q π M ′ i (s, a) > V π M ′ i (s)} is the set of confusing models for (s, a, i, π).Q can be equivalently rewritten using thm. B.2 as(T ⋆ Q ) -1 = sup ω∈Ω(M ) min i,s,a̸ =π ⋆ i (s) inf M ′ ∈Altsai(Mq i ) s ′ ,a ′ ω(s ′ , a ′ )   KL P |P ′ (s ′ , a ′ ) + j KL qj |q ′ j (s ′ , a ′ )   ,Lower bound analytic form. We now rewrite the lower bound optimization problem analytically in a similar form to (5) in [16] . For all s, a, i let dr i (s, a) = r qi (s, a)r q ′ i (s, a) and dP (s, a) = P M ′ (s, a) -P M (s, a). Further define the vector difference between the value in M i and M ′ i :dV π i = V π ⋆ i M ′ i (s 1 ) -V ⋆ Mi (s 1 ) . . . V π ⋆ i M ′ i (s S ) -V ⋆ Mi (s S ) ⊤. Finally, we let 1(s) = e s be the unit vector with 1 in position s.Fix i, s, a ̸ = π ⋆ i (s). Then, we find that M ′ ∈ Alt π ⋆ i s,a,i (M i ) if and only if dr i (s, a) + ∆ i (s, a) < γdP (s, a) ⊤ V ⋆ Mi + (γP M ′ i (s, a) -1(s)) ⊤ I -γP ′ π ⋆ i -1 (r ′ π ⋆ i -r π ⋆ i ) + (γP M ′ i (s, a) -1(s)) ⊤ (I -γP ′ π ⋆ i ) -1 -(I -γP π ⋆ i ) -1 -1 r π ⋆ i ).Hence, the conditionQ π M ′ q i (s, a) > V π M ′ q i(s) is equivalent to the above inequality. This inequality only involves the {(s, a, i), ∪ s ′ (s ′ , π ⋆ i (s ′ ))}, and therefore the infimum overAlt sai (M i ) of s,a ω(s, a)KL Q M |M ′ (s, a) is a model M ′ satisfying KL Q M |M ′ (s, a)= 0 over all the other stateaction pairs. Hence, using lem. B.1, and the reasoning above, we haveT Q (ω; M ) -1 = min i,s,a̸ =π ⋆ i (s) inf M ′ ∈Alt π sai (M ) ω(s, a)KL i M |M ′ (s, a) + s ′ ω(s ′ , π ⋆ i (s ′ )) KL P |P ′ (s ′ , π ⋆ i (s ′ ))) + KL qi|q ′ i (s ′ , π ⋆ i (s ′ )))Sub-optimality gaps. We now relate the KL-terms to the sub-optimality gaps, similarly as in [53, 16] .By following a similar approach to [16, Thm. 2] and the proof of the relaxed characteristic rate in app. B.2 one can show that, for any α ∈ Σ 4 , we have                         KL qi|q ′ i (s, a) ≥ B i,1 (α 1 ) := α 2 1 ∆ 2 i (s,a) 2 KL P,P ′ (s, a) ≥ B i,2 (α 2 ) := α 2 2 ∆ i (s, a) 2 2γ 2 MD i (s, a) 2 max s ′ KL qi|q ′ i (s ′ , π ⋆ i (s ′ )) ≥ B i,3 (α 3 ) := α 2 3 (∆i(1-γ)) 2 2 max s ′ KL P |P (s ′ , π ⋆ i (s ′ ) ≥ B i,4 (α 4 ) := min [α4∆i(1-γ)] 2 16Vari , [α4∆i(1-γ)] 4/3 2 7/3 MD 4/3 i max s ′ KL P |P (s ′ , π ⋆ i (s ′ )) ≥ B i,5 (α 4 ) := min α 2 4 ∆ 2 i (1-γ) 3 288 log(2) 2 , α4∆ 2 i (1-γ) 5/2 24 log(2) , α 4/3 4 ∆ 4/3 i (1-γ) 4/3 2 5/3 3 4/3 MDiOptimization. Putting all the inequalities together, we getT Q (ω; M ) -1 ≥ min i,s,a̸ =π ⋆ i (s) inf α∈Σ4 ω(s, a)(B i,1 (α 1 ) + B i,2 (α 2 )) + min s ω(s, π ⋆ i (s))(B i,3 + max(B i,4 (α 4 ), B i,5 (α 4 ))).Then, proceeding as in thm. 3.2, and optimizing for α ∈ R 4 ≥0 such that i α i = 1 yields the result.In this section we consider the extension to a continuous set of rewards 3 . 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 a pre-specified reward signal. Therefore, we extend our discussion to include a continuous set of rewards. This extension presents several challenges. First, it may not be feasible to assume that the optimal policy is unique for each reward. Second, the minimum gap can be non-convex and discontinuous, as we will discuss in the following section. However, we find that, in practice, it is sufficient to consider a finite set of rewards. This observation provides a basis for the implementation of a 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.The relaxed characteristic rate is mainly characterized by the minimum sub-optimality gap ∆ r = min s,a∈O c r (s) ∆ r , where O r (s) = {a : Q ⋆ Mr (s, a) = V ⋆ Mr (s)} is the set of optimal actions in s for the MDP M r . Unfortunately, even with a convex set of rewards, the minimum sub-optimality gap may be non-convex and possibly discontinuous. The discontinuity arises from the fact that in a certain state(s) all actions are optimal for specific rewards.We illustrate this intuition with an example. Consider the MDP depicted in fig. 2 with states S = {s 0 , s 1 } and actions A = {a 0 , a 1 }. For this MDP, we have P (s 0 |{s 0 , s 1 }, a 0 ) = 1, P (s 1 |s 0 , a 1 ) = 0.3, P (s 0 |s 0 , a 1 ) = 0.7, P (s 1 |s 1 , a 1 ) = 0.3 and P (s 0 |s 1 , a 1 ) = 0.7.We use the following reward function, which parametrized by θ ∈ [0, 1], in vector formr =    (s0,a0) 0 (s0,a1) θ (s1,a0) 0 (s1,a1) 1 -θ    = θe 2 + (1 -θ)e 4 .Next, we derive the sub-optimality gaps Optimal Value function V ⋆ θ and policy π ⋆ θ . For a discount factor γ = 0.5 we obtain that∆ θ (s, a) = V ⋆ θ (s) -Q ⋆ θ (s, a) as a function of θ. s 0 s 1 (a 1 , 0.3, θ) (a 0 , 1, 0), (a 1 , 0.7, 1 -θ) (a 0 , 1, 0), (a 1 , 0.7, θ) (a 1 , 0.3, 1 -θ) 1 2 23 26 1 0 1 2 θ ∆ θ = min s min a / ∈Oθ(s) ∆ θ (s, a)V ⋆ θ (s 0 ) = max     1 2 V ⋆ θ (s 0 ) action a0 , θ + 7 20 V ⋆ θ (s 0 ) + 3 20 V ⋆ θ (s 1 ) action a1     , V ⋆ θ (s 1 ) = max     1 2 V ⋆ θ (s 0 ) action a0 , 1 -θ + 7 20 V ⋆ θ (s 0 ) + 3 20 V ⋆ θ (s 1 ) action a1     .One can immediately see that a 1 is optimal in s 0 for all θ, while in s 1 we need to distinguish between the two cases.If a 0 is optimal in s 1 , then we findV ⋆ θ (s 0 ) = 40 23 θ, V ⋆ θ (s 1 ) = 20 23 θ.Alternatively, if a 1 is optimal in s 1 , thenV ⋆ θ (s 0 ) = 7 5 θ + 3 10 , V ⋆ θ (s 1 ) = - 3 5 θ + 13 10 .It is possible then to see that for θ < 23/26 the optimal policy π ⋆ θ = [a 1 a 1 ] is to choose action a 1 in both states, while for θ > 23/26 the optimal policy π ⋆ θ = [a 1 a 0 ] changes so that action a 0 is now optimal in state s 1 . For θ = 23/26 both actions {a 0 , a 1 } are optimal in state s 1 .Optimal Action-value function Q ⋆ θ . We distinguish two cases. For θ ≥ 23/26 we have Minimum sub-optimality gap. Hence, we conclude that the minimum sub-optimality gap is Note that the minimum gap is non-convex on θ and it has a discontinuity at θ = 23/26, as shown in fig. 2 .Q ⋆ θ (s 0 , a) = 20 23 θ a = a 0 40 23 θ a = a 1 , Q ⋆ θ (s 1 , a) =∆ θ = min s min a / ∈O θ (s) ∆ θ (s, a) =       In this subsection, we derive a convex upper bounds on T ⋆ (M ) when R is a continuous set of rewards. The idea is to find a finite set of rewards R ′ so that we 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 hull4 of R ′ contains R. This last assumption is easy to satisfy, since one can just consider the canonical basis R canonical in R ′ . Using this property, we derive a novel decomposition that leads to an alternative upper bound on T (ω; M ). Theorem B.3. Consider a 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 ω ∈ Ω(S × A) we have thatT (ω; M ) ≤ min r∈R ′ min s,a 8γ 2 MD r (s, a) 2 ∆ 2 r (1 -γ) 2 ω(s, a).Proof. Using the decomposition in lem. B.5 in conjunction with the results in prop. B.1 and lem. B.6 leads to the desired result. Using also that for anyω ∈ R SA >0 ∆ 2 e ≤ 8 γ 2 (1 -γ) 2 max s,a KL M |M ′ (s, a)ω(s, a) MD e (s, a) 2 ω(s, a) , ≤ 8 γ 2 (1 -γ) 2 max s,a KL M |M ′ (s, a)ω(s, a) max s ′ ,a ′ MD e (s ′ , a ′ ) 2 ω(s ′ , a ′ ) . Then T (ω; M ) -1 ≥ min r∈R inf M ′ ∈Altr(M ) s,a ω(s, a)KL M |M ′ (s, a) , ≥ min r∈R min e∈R ′ min s ′ inf M ′ ∈Alt π ⋆ r s ′ ,π ⋆ r (s ′ ),r,e (M )s,a ω(s, a)KL M |M ′ (s, a) ,≥ min r∈R min e∈R ′ min s,a ω(s, a) ∆ 2 e (1 -γ) 2 8γ 2 MD e (s, a) 2 , = min e∈R ′ min s,a ω(s, a) ∆ 2 e (1 -γ) 2 8γ 2 MD e (s, a) 2 .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 a scaling of (1γ) -3 (we refer the reader to the proof of prop. B.1 and note that we could use lem. B.3 to find an alternative scaling).Confusing set of models decomposition: continuous set of rewards. From the example in fig. 2 we know that an MDP may have a non-convex sub-optimality gap over a 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 ′ ⊂ R.We obtain a decomposition that depends on R ′ as long as every reward in r ∈ R can also be written as a convex combination (or conic combination) of the rewards R ′ (which can be guaranteed simply by including R canonical to R ′ ). Lemma B.5 (Decomposition lemma for a continuous set of rewards.). Consider a finite set of rewards R ′ such that R ⊂ Hull(R ′ ) and each r ∈ R ′ admits at-least a confusing model with respect to M r (as in assumption (III)). Then, we have that the set of confusing models for any r ∈ R satisfiesEQUATIONwhere Alt π sare (M ) := {M ′ : Q π M ′ e (s, a) > V π M ′ e (s)}.Proof. Consider a reward r ∈ R. From the fact that R is contained in a convex hull of R ′ we can always find θ ∈ [0, 1] |R ′ | such that r = e∈R ′ θ e e, where θ e is the non-negative coefficient for the corresponding reward e (satisfying e θ e = 1).Alt r (M ) ⊆ {M ′ |∃e ∈ R ′ , s ∈ S, a ̸ = π ⋆ r (s) : Q π M ′ e (s, a) > V π M ′ e (s)} with π = π ⋆ r . By contradiction, assume there exists M ′ ∈ Alt(M r ) so that ∀e ∈ R ′ , s ∈ S, a ̸ = π(s) the inequality Q π M ′ e (s, a) ≤ V π M ′ e (s) holds. Then, since Q π Me (s, π(s)) = V π Me (s) the inequality Q π M ′ e (s, a) ≤ V πM ′ e (s) holds for every e, s, a. By linearity, the inequality holds also if we multiply by x ≥ 0 both sides. Choosing x = θ e , and summing over e, we obtain thate∈R ′ θ e Q π M ′ e (s, a) ≤ e θ e V π M ′ e (s).Letting j s,a ∈ {1, . . . , SA} be the index corresponding to the state-action pair (s, a) and (P ′ ) π be the transition function associated to policy π, i.e., (P ′ ) π (s ′ , a ′ |s, a) = π(a ′ |s ′ )P ′ (s ′ |s, a), we obtain that5 e θ i Q π M ′ e (s, a) = e θ e e ⊤ js,a (I -γ(P ′ ) π ) -1 e = e ⊤ js,a (I -γ(P ′ ) π ) -1 r = Q π Mr (s, a).Therefore, we conclude thatQ π M ′ r (s, a) ≤ V π M ′r (s) is valid for all state-action pairs. Let now π be an optimal policy in M ′ r . Then, for all states we haveQ π M ′ r (s, π(s)) ≤ V π M ′r (s). Hence, as in [16, Lemma 2] , by repeated applications of the Bellman operator Γ π with respect to the MDPM ′ r , one can conclude that V ⋆ M ′ r (s) ≤ V π M ′r (s) in all states. However, this implies that π is optimal in M ′ r , which contradicts that M ′ ∈ Alt(M r ).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 R canonical (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 a bound on the minimum sub-optimality gap.Proposition B.1. Consider two rewards r, e and two MDPs M, M ′ such thatEQUATIONwhere ∆P (s, a) = P M (s, a) -P M ′ (s, a), and P M (s, a) (sim. P M ′ (s, a)) is a vector of size S representing the distribution of the next state given (s, a).In particular we also have∆ 2 e ≤ 8 γ 2 (1 -γ) 2 max s,a KL M |M ′ (s, a)MD e (s, a) 2 . Proof. The fact that Π ⋆ (M r ) ∩ Π ⋆ (M ′ e ) = ∅ implies that in all states we have 0 ≤ V ⋆ M ′ e (s) -V π M ′e (s), for all π ∈ Π ⋆ (M r ). Let s 0 be a state such that in M e there is a sub-optimal action. Henceforth, we have that ∆ e ≤ V ⋆ Me (s 0 ) -Q ⋆ Me (s 0 , a) for some a. Hence∆ e ≤ V ⋆ Me (s 0 ) -Q ⋆ Me (s 0 , a) + V ⋆ M ′ e (s 0 ) -V π M ′ e (s 0 ), ≤ ∥V ⋆ Me -V π M ′ e ∥ ∞ + ∥Q ⋆ M ′ e -Q ⋆ Me ∥ ∞ .Now we bound the two terms separately.1. For the first term, let π ′ ∈ Π ⋆ (M e ), and sinceQ ⋆ Me (s, π ′ (s)) ≥ Q ⋆ Me (s, π(s)) write [V π M ′ e -V ⋆ Me ](s) = Q π M ′ e (s, π(s)) -Q ⋆ Me (s, π ′ (s)), ≤ Q π M ′ e (s, π(s)) -Q ⋆ Me (s, π(s)), ≤ ∥Q π M ′ e -Q ⋆ Me ∥ ∞ . Therefore ∥V ⋆ Me -V π M ′ e ∥ ∞ ≤ ∥Q π M ′ e -Q ⋆ Me ∥ ∞ = ∥Q ⋆ Me -Q π M ′ e ∥ ∞ . Hence, since [Q ⋆ Me -Q π M ′ e ](s, a) = γ ∆P (s, a) ⊤ V ⋆ Me + P M ′ (s, a) ⊤ (V ⋆ Me -V π M ′ e ) , we obtain ∥Q ⋆ Me -Q π M ′ e ∥ ∞ ≤ γ 1 -γ ∥∆P (s, a) ⊤ V ⋆ Me ∥ ∞ , leading to ∥V ⋆ Me -V π M ′ e ∥ ∞ ≤ γ 1-γ ∥∆P (s, a) ⊤ V ⋆ Me ∥ ∞ .2. For the second term we have[Q ⋆ Me -Q ⋆ M ′ e ](s, a) = γ ∆P (s, a) ⊤ V ⋆ Me + P M ′ (s, a) ⊤ (V ⋆ Me -V ⋆ M ′ e ) ,hence, as for the first term, we have∥Q ⋆ M ′ e -Q ⋆ Me ∥ ∞ ≤ γ 1-γ ∥∆P (s, a) ⊤ V ⋆ Me ∥ ∞ .Therefore we have that ∆ e ≤ 2γ 1-γ ∥∆P (s, a) ⊤ V ⋆ Me ∥ ∞ . Finally, an application of Pinsker inequality leads to∆ 2 e ≤ 4 γ 2 (1 -γ) 2 max s,a |∆P (s, a) ⊤ V π Me | 2 ≤ 8 γ 2 (1 -γ) 2 max s,a KL M |M ′ (s, a)MD e (s, a) 2 .Lemma B.6. Consider two MDPs M, M ′ and two rewards r, e. If for all policies π ∈ Π ⋆ (M r ) there exists a state-action pair (s, a) such thatQ π M ′ e (s, a) > V π M ′ e (s), then Π ⋆ (M r ) ∩ Π ⋆ (M ′ e ) = ∅.Proof. The proof simply follows by the fact that for all policies π ∈ Π ⋆ (M r ) there exists a state s where the policy is improvable. Therefore, none of the policies in Π ⋆ (M r ) is optimal in M ′ e .In this section we describe the MR-NaS algorithm in detail. We prove its δ-PC property and its guarantees on the sample complexity.Notation. In addition to the notation introduction in sec. 2, in tab. 3 we provide a summary of the notation used in this section. Ergodicity constant such that P r (z ′ |z) > 0 for all r ≥ r 0 . σ u Constant, defined asσ u := min (z ′ ,z)∈Z 2 P r0(z ′ |z) u /ω u (z ′ ). σ(ϵ, π) Defined as σ(ϵ, π) := (1 -ϵ)A min s,a π(α|s) τ + ϵ r 0 (α+β) α t σ u . θ(ϵ, π) θ(ϵ, π) := 1 -σ(ϵ, π) C(ϵ, π) C(ϵ, π) := 2/θ(ϵ, π) ρ(ϵ, π) ρ(ϵ, π) := θ(ϵ, π) 1/r0 L(ϵ, π) L(ϵ, π) := (1 -ρ(ϵ, π)) -1 C(ϵ, π) σ t , θ t , C t ρ t , L tRespectively defined as σ t := σ(ϵ t , π t ), θ t := θ(ϵ t , π t ), etc. E Convergence of the MDP estimate and state-action visitation frequency eventE := (∀(s, a) ∈ Z, lim t→∞ N t (s, a)/t = ω ⋆ (s, a), lim t→∞ M t = M ). E cnt (λ)Count event, defined asE cnt (λ) := ∀t ≥ 1, ∀(s, a), N t (s, a) ≥ 1 2 ⌊ t m ⌋ k=1 ηm (km) α+β -log |S||A| λ . E 1 p,T (ξ) Concentration of the empirical MDP event E 1 p,T (ξ) = ∩ T t=hp(T ) (M t ∈ B ρ(ξ) (M )). E 2 T (ξ)Concentration of the state-action visitation frequency eventE 2 T (ξ) := ∩ T t=T 1-p | Nt t -ω ⋆ | ≤ K ξ ξ .Remark C.1 (Extension to the setting of continuous/stochastic rewards.). In this setting we consider the case with finite rewards. For the other two settings described in app. B (continuous and stochastic rewards), MR-NaS can be directly adapted by using the relaxed characteristic rate specified in app. B.3.2 for stochastic rewards and in app. B.4.2 for continuous rewards. The primary modification involves the computation of ω ⋆ , where the relaxed characteristic rate appropriate for the respective setting should be applied. Furthermor, for stochastic rewards, the algorithm also needs to account for an additional exploration threshold in the stopping rule similarly to [17, Prop. 5 ].Remark C.2 (Novelties with respect to previous works.). Our work is mostly inspired by [17] . With respect to previous works, we introduce a novel forcing policy that does not use an exploration factor ϵ t that depends MDP-specific quantities, such as the "connectedness" of the MDP, that we denote by m. In [17] they use ϵ t = t -1 2(m+1) , while we use ϵ t = 1/ max(1, N t (s t )) α . This change requires a slight modification of the proofs in [17] , since now ϵ t depends also on the number of visits of s t . Additionally, we improve on the high probability forced exploration [17, Lemma 11] ,where the authors have a scaling of N t (s, a)∼ ≥ tη 2 m m 2 log 2 (1+SA/λ) 1/4while we obtain a scalingN t (s, a) ∼ ≥ ηm m α+β H ⌊ t m ⌋,α+β -log(SA/λ), where H x,y is the x-th generalized harmonic number of order y and η m is the minimal probability of reaching a state-action pair in m steps under a uniform random 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 π f,t (•|s) = softmax (-β t (s)N t (s, •)), which is inspired by the classical Boltzmann distribution. Intuitively this forcing policy will choose actions that have been undersampled. We find the following lower bound on the probability of picking an action a at time t ≥ 1. EQUATION)Proof. Note that proving ( 23) is equivalent to showing that AN t (s) β e -βt(s)Nt(s,a) ≥ b e -βt(s)Nt(s,b) .We actually show the following stronger result:AN t (s) β e -βt(s)Nt(s,a) ≥ Ae -βt(s) min b Nt(s,b) ≥ b e -βt(s)Nt(s,b) .Therefore, taking the logarithm on both hand-sides, we obtainβ log(N t (s)) ≥ β t (s)(N t (s, a) -min b N t (s)) = β log(N t (s))(N t (s, a) -min b N t (s) max a |N t (s, a) -min b N t (s, b)| .Thus, we obtain the condition1 ≥ N t (s, a) -min b N t (s) max a |N t (s, a) -min b N t (s, b)| ,which is always true for all a ∈ A, proving the lemma.We now describe the forced exploration property of MR-NaS. We conclude by showing that N t (s, a)/t → ω ⋆ (s, a) a.s., and the almost sure sample complexity bound of MR-NaS.In the following lemma we adapt a result from [17] to our forcing policy π f,t . We also define the following quantitiesσ(ϵ, π) := [(1 -ϵ)A min s,a π(a|s)] r0 + ϵ r 0 (α+β) α t σ u , θ(ϵ, π) := 1 -σ(ϵ, π), C(ϵ, π) := 2/θ(ϵ, π), ρ(ϵ, π) := θ(ϵ, π) 1/r0 , L(ϵ, π) := (1 -ρ(ϵ, π)) -1 C(ϵ, π).where σ u := min z,z ′ P r0 u (z ′ |z)/ω u (z ′ ) and r 0 , α, β are as before. For the sake of brevity, we letσ t = σ(ϵ t , π ⋆ t ), θ t = θ(ϵ t , π ⋆ t ), and similarly for C t , ρ t , L t . Lemma C.2 (Geometric ergodicity of the sampling rule). For MR-NaS it holds thatEQUATION)Proof. For two state-action pairs z = (s, a), z ′ = (s ′ , a ′ ) denote by P r t (z ′ |z) the probability of reaching z ′ from z in r steps. Then, for all (z, z ′ ) we haveP r t ≥ (1 -ϵ t ) r0 P r0 π ⋆ t (z ′ |z) + ϵ r0 t P r0 π f ,t (z ′ |z), ≥ (1 -ϵ t ) r0 P r0 π ⋆ t (z ′ |z) + (1/N t (s) α+β ) r0 P r0 u (z ′ |z), ≥ (1 -ϵ t ) r0 P r0 π ⋆ t (z ′ |z) + ϵ r 0 (α+β) α t P r0 u (z ′ |z).Let c t = min s,a π ⋆ t (a|s) and note that P π ⋆ t (z ′ |z) ≥ Ac t P u (z ′ |z) for all (z, z ′ ). Recall the definitions for the stationary distribution under the uniform policy by ω u , and σ u = min z,z ′ P r0 u (z ′ |z)/ω u (z ′ ). Then, we can rewrite the previous inequality asP r t ≥ [(1 -ϵ t )Ac t ] r0 + ϵ r 0 (α+β) α t P r0 u (z ′ |z) ω u (z ′ ) ω u (z ′ ) , ≥ [(1 -ϵ t )Ac t ] r0 + ϵ r 0 (α+β) α t σ u ω u (z ′ ), ≥ [(1 -ϵ t )Ac t ] r0 + ϵ r 0 (α+β) α t σ u ω u (z ′ )ω t (z ′ ).Then using [17, Lemma 21] we conclude that for all n ≥ 1 it holds that:∥P n t -W t ∥ ∞ ≤ 2θ n r -1 t.Hence P t also satisfies ∥P n t -W t ∥ ∞ ≤ C t ρ n t .In the following lemma, we provide a novel result for the forced exploration property of MR-NaS, which relies on lem. C.7. Lemma C.3. For all λ ∈ (0, 1), m := m 0 + 1, define the eventE cnt (λ) =    ∀t ≥ 1, ∀(s, a) ∈ S × A, N t (s, a) ≥ 1 2 ⌊ t m ⌋ k=1 η m (km) α+β -log SA λ    .Then, for MR-NaS with α + β ≤ 1 we have that P E cnt (λ) ≤ λ.Proof. Fix a state-action pair z = (s, a) and let Y t = 1 zt=z andX k = 1 Y (k-1)m+1 +•••+Y km >0 for k = 1, . . . , ⌊ t m ⌋. Define N⌊ t m ⌋ (s, a) = ⌊ t m ⌋k=1 X k , and note that N t (s, a) ≥ N⌊ t m ⌋ (s, a) for allt ≥ 1. Let Q k = P(X k = 1|F k-1 ), where F k = σ(Y 1 , . . . , Y km ). Note that we can also write Q k as Q k = P(∃n ∈ {1, . . . , m} : Y (k-1)m+n = 1|F k-1 ). ThenQ k = E (πt)t P ∃n ∈ {1, . . . , m} : Y (k-1)m+n = 1|F k-1 , (π t ) t , ≥ E (πt)t max 1≤n≤m P Y (k-1)m+n = 1|F k-1 , (π t ) t , ≥ E (πt)t,z0 max 1≤n≤m P z (k-1)m+n = z|z (k-1)m = z 0 , F k-1 , (π t ) t , = E (πt)t,z0   max 1≤n≤m E (zi) n-1 i=1   n-1 j=0 P (k-1)m+j (z (k-1)m+j+1 = z j+1 |z (k-1)m+j = z j )|z 1 , . . . , z n-1 , z n = z   |z 0   , ≥ E (πt)t,z0   max 1≤n≤m E (zi) n-1 i=1   n-1 j=0 1 (km) α+β P u (z (k-1)m+j+1 = z j+1 |z (k-1)m+j = z j )|z 1 , . . . , z n-1 , z n = z   |z 0   , = E (πt)t,z0 max 1≤n≤m 1 (km) α+β P n u (z (k-1)m+n = z|z (k-1)m = z 0 )|z 0 , ≥ η m (km) α+β .Hence, for λ ′ ≥ 0 due to lem. C.7 we also haveP   ∃t : N t (s, a) ≤ 1 2 ⌊ t m ⌋ k=1 η m (km) α+β -λ ′   ≤ P   ∃t : N⌊ t m ⌋ (s, a) ≤ 1 2 ⌊ t m ⌋ k=1 Q k -λ ′   ≤ e -λ ′ .Consequently, choosing λ ′ = log(SA/λ), we get thatP E cnt (λ) ≤ s,a P   ∃t : N t (s, a) ≤ 1 2 ⌊ t m ⌋ k=1 Q k (s, a) -log SA λ   ≤ s,a λ SA = λ.The following result, automatically follows from the previous lemma.Corollary C.1. For all t ≥ 1, under E cnt (λ) we haveEQUATIONIn the following lemma we bound the probability that M t is not close to M . In order to do so, recall that π ⋆ (a|s) = ω ⋆ (a|s)/ b ω ⋆ (b|s) and π⋆ t (a|s) = ω ⋆ t (a|s)/ b ω ⋆ t (b|s). Then, observe that by continuity of M t → ω ⋆ t (due to Berge's theorem) we that for every ξ > 0 there exists ρ > 0 such that forM t ∈ B ρ (M ) we have ∥π ⋆ t -π ⋆ ∥ ∞ ≤ ξ. Lemma C.4. For ξ > 0, T ≥ 1 define the event E 1 p,T (ξ) = ∩ T t=hp(T ) (M t ∈ B ρ(ξ) (M ))where h p (T ) = T p with p ∈ (0, 0.5). Then, there exists a constant C > 0 that only depend on ξ and M such thatEQUATIONwhereg hp(T ) (λ) = 1 2 ⌊ hp(T ) m ⌋ k=1 ηm (km) α+β -log SA λ .Proof. Consider the event E cnt (λ) from lem. C.3 and let λ = 1/T 2 . Note thatP E 1 p,T (ξ) ≤ λ + P E 1 p,T (ξ) ∩ E cnt (λ) .For simplicity, we omit the dependence on λ and simply write E cnt . Then, we have6 P(E 1 p,T (ξ) ∩ E cnt ) ≤ T t=hp(T ) P(M t / ∈ B ρ (M ) ∩ E cnt ), = T t=hp(T ) P(max s,a ∥P t (•|s, a) -P (•|s, a)∥ 1 > ρ ∩ E cnt ), ≤ T t=hp(T ) s,a,s ′ P(|P t (s ′ |s, a) -P (s ′ |s, a)| > ρ/S ∩ E cnt ). Now, let g t (λ) = 1 2 t k=1 ηm (km) α+β -log SA λ .Then, we haveP(|P t (s ′ |s, a) -P (s ′ |s, a)| > ρ/S ∩ E cnt ) ≤ P(|P t (s ′ |s, a) -P (s ′ |s, a)| > ρ/S ∩ N t (s, a) ≥ g t (λ)), ≤ t k=gt(λ) P(|P t (s ′ |s, a) -P (s ′ |s, a)| > ρ/S ∩ N t (s, a) = k), ≤ t k=gt(λ) 2 exp(-2kρ 2 ), ≤ t-gt(λ) k=0 2 exp(-2(k + g t (λ)ρ 2 ), ≤ exp(-2g t (λ)ρ) t-gt(λ) k=0 2 exp(-2kρ 2 ), ≤ 2 exp(-2g t (λ)ρ) 1 -exp(-2ρ 2 ) .Hence, we findT t=hp(T ) s,a,s ′ 2 exp(-2g t (λ)ρ) 1 -exp(-2ρ 2 ) ≤ T t=hp(T ) 2S 2 A exp(-2g t (λ)ρ) 1 -exp(-2ρ 2 ) , ≤ 2S 2 AT exp(-2g hp(T ) (λ)ρ) 1 -exp(-2ρ 2 ) .Recall now that ω t is the stationary distribution induced by the exploration policy π t at time t. Further, recall thatπ t = (1 -ε t )π ⋆ t + ε t π f,t , ω ⋆ t = inf ω∈Ω(Mt) U (ω; M t ), ω⋆ t = (1/t) t n=1 ω ⋆ n and that π ⋆ t (a|s) = ω⋆ t (a|s)/ a ′ ω⋆ t (s, a ′ ).We have the following result. Corollary C.2. Let T ≥ 1, p ∈ (0, 1), ξ > 0, λ ∈ (0, 1). For t ≥ T p under E 1 p,T (ξ) we have that there exists ρ > 0 and κ t (λ) such thatEQUATION)As a consequence, under E 1 p,T (ξ) we also have that∥P t -P t-1 ∥ ∞ ≤ 2 T p t -1 + ξ + ϵ t-1 .Proof. Let π ⋆ (a|s) = ω ⋆ (a|s)/ b ω ⋆ (b|s) and π⋆ t (a|s) = ω ⋆ t (a|s)/ b ω ⋆ t (b|s). Under E 1 p,T (ξ) using [17, Lemma 23] there exists an MDP-specific constant κ M such that∥ω t -ω ⋆ ∥ 1 ≤ κ M ∥P t -P π ⋆ ∥ ∞ , ≤ κ M ∥π t -π ⋆ ∥ ∞ , ≤ κ M [∥π ⋆ t -π ⋆ ∥ ∞ + ϵ t ] , ≤ κ M [∥π ⋆ t -π ⋆ ∥ ∞ + ϵ t ] .Then, for t ≥ T p , we have∥π ⋆ t -π ⋆ ∥ ∞ ≤ 1 t t k=1 (π ⋆ t -π ⋆ ) ≤ T p t + ξ,which concludes the first part of the proof. For the second part, simply note thatEQUATIONT p t -1 + ξ + ϵ t-1 .From the previous lemma we remark the following important fact: under E 1 p,T (ξ) for k ≥ T q ≥ T p we have∥π ⋆ k -π ⋆ ∥ ∞ ≤ T p k + ξ ≤ 1 T q-p + ξ.In the following proof we provide a a reformulation of [17, Proposition 19] . We require t and T to be larger than some constants. Specifically, we require t ≥ T 1-p (note that p ∈ (0, 0.5)) andT ≥ max T q (ξ, λ), 1 ξ 1 q-p , 1 ξ 1 1-p-q, where q ∈ (0, 1) satisfies p < q, p + q < 1 and T q (ξ, λ) := inf{T ≥ 1 : ξ ≥ κ T q (λ) + 1 T (1-3p)/2 } with ξ > 0, λ ∈ (0, 1) and κ t defined in corollary C.1. Proposition C.3. Under MR-NaS there exists T (ξ, λ) such that for all T ≥ max T q (ξ, λ),1 ξ 1 q-p , 1 ξ 1 1-p-qand all t ≥ T 1-p . and all functions f : Z → [0, 1] we haveEQUATIONwhere ξ → K ξ is a mapping with values in (1, ∞) such that lim sup ξ→0 K ξ < ∞.Proof. Let ω ⋆ (f ) = E z∼ω ⋆ [f (z)] and ω t (f ) = E z∼ωt [f (z)]. Then D = t k=1 f (z k ) t -ω ⋆ (f ), = T q k=1 f (z k ) -ω ⋆ (f ) t + t k=T q +1 f (z k ) -ω ⋆ (f ) t , = T q k=1 f (z k ) -ω ⋆ (f ) t (a) + t k=T q +1 f (z k ) -ω k-1 (f ) t (b) + t k=T q +1 ω k-1 (f ) -ω ⋆ (f ) t (c).First term (a). For the first term (a) for t ≥ T 1-p and ξ ≥ 1/T 1-p-q we have(a) ≤ T q t ≤ 1 T 1-p-q ≤ ξ. Last term (c). The last term (c) under E 1 p,T (ξ) for t ≥ T 1-p is bounded as 7 (c) ≤ t-1 k=T q ∥ω k -ω ⋆ ∥ 1 t , ≤ t-1 k=T q κ M [T p /k + ξ + ϵ Tq ] t , ≤ κ M ξ + ϵ Tq + t-1 k=T q T p /k t , ≤ κ M ξ + ϵ Tq + T p log(t) t , ≤ κ M ξ + ϵ Tq + T p √ t , ≤ κ M ξ + ϵ Tq + 1 T (1-3p)/2 . Hence, under E 1 p,T (ξ) ∩ E cnt (λ), since ϵ k ≤ κ k (λ) we get that (c) ≤ κ M ξ + κ Tq (λ) + 1 T (1-3p)/2 . Let T q (ξ, λ) = inf{T ≥ 1 : ξ ≥ κ T q (λ) + 1 T (1-3p)/2 } where κ t is defined in corollary C.1. Then for T ≥ T q (ξ, λ) we have (c) ≤ 2κ M ξ.For the second term we use the function fk solution to the Poisson equationf (•) -ω k-1 (f ) = [ fk -P k fk ](•) [17, Lemma 23]. Hence (b) = (1/t) t k=T q +1 fk-1 (z k ) -P k-1 fk-1 (z k ) = M t + C t + R t ,whereM t := t k=T q +1 fk-1 (z k ) -P k-1 fk-1 (z k-1 ) t , C t := t k=T q +1 P k fk (z k ) -P k-1 fk-1 (z k ) t ,R t := P T q fT q (z T q ) -P t ft (z t ) t .Before proceeding, always under E 1 p,T (ξ) ∩ E cnt (λ) for T ≥ T q (ξ, λ) we have that|ϵ k | ≤ κ Tq (λ) ≤ ξ,and for k ≥ T q , ξ ≥ 1/T q-p ∥π ⋆ k -π ⋆ ∥ ∞ ≤ T p k + ξ ≤ T p T q-p + ξ ≤ 2ξ. Therefore L k ≤ L ξ , where L ξ = sup |ϵ|≤ξ,∥π-π ⋆ ∥∞≤2ξ L(ϵ, π).Bounding M t . As in [17] , tM t is a martingale satisfying|kM k -(k -1)M k-1 | ≤ 2L k-1, and hence for t ≥ T 1-p we bound using Azuma-Hoeffding inequalityP(|M t | ≥ 2L ξ ξ) ≤ 2 exp(-tξ 2 ).Bounding C t . Again, for t ≥ T 1-p we haveC t ≤ (1/t) t k=T q +1 L k [∥ω k -ω k-1 ∥ + L k-1 ∥P k -P k-1 ∥ ∞ ], ≤ (1/t) t k=T q +1 L k ∥ω k -ω k-1 ∥ + 2L k-1 T p t -1 + ξ + ϵ t-1 , ≤ (1/t) t k=T q +1 L k ∥ω k -ω ⋆ ∥ + ∥ω k-1 -ω ⋆ ∥ + 2L k-1 T p t -1 + ξ + ϵ t-1 , ≤ (1/t) t k=T q +1 2L k κ M T p k -1 + ξ + ϵ k-1 + L k-1 T p k -1 + ξ + ϵ k-1 , ≤ 2(1/t) t k=T q +1 L ξ (κ M + L ξ ) T p k -1 + ξ + ϵ k-1 , ≤ 2L ξ (κ M + L ξ ) T p √ t + ξ + κ Tq (λ) , ≤ 2L ξ (κ M + L ξ ) 1 T (1-3p)/2 + ξ + κ Tq (λ) , ≤ 4L ξ (κ M + L ξ )ξ.Bounding R t . Finally, for the last term we get for T ≥ T q (ξ, λ) we have|R t | ≤ 2L ξ /t ≤ 2L ξ /T 1-p ≤ 2L ξ /T (1-3p)/2 ≤ 2L ξ ξ.Last step. Summing up all terms yields that for t ≥ T 1-p , T ≥ max T q (ξ, λ),EQUATIONwhereκ ξ = 1 + 2κ M + 4L ξ (1 + κ M + L ξ ).As a corollary of the previous proposition, we find the following concentration result on N t (s, a)/t and the high probability eventEQUATIONandEQUATIONFinally, 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 N t (s, a)/t concentrates around ω ⋆ (s, a). To that aim, the concentration happens under some events E 1 p,T (ξ) (defined in lem. C.4) given that N t (s, a) is visited sufficiently often (see lem. C.3, or the alternative version in lem. C.5). As δ → 0, by the properties of β(N t , δ), one can show that that E[τ ]/ ln(1/δ) does not exceed sup M ′ ∈B ρ(ξ) (M ),∥ω ′ -ω ⋆ ∥∞≤K ξ ξ U (ω ′ , M ′ ) ln(1/δ), where B ρ(ξ) (M ) is a ball of a certain radius ρ(ξ) around M (see def. of ρ(ξ) in app. C.3.3) and K ξ > 0 for all ξ > 0. Hence, letting ξ → 0 concludes the proof.Theorem C.2 (Expected sample complexity). MR-NaS with the stopping rule in prop. 3.1 guarantees that E[τ ] < ∞ and lim sup δ→0E[τ ] log(1/δ) ≤ U ⋆ (M ). Proof. Define U ⋆ (ξ) = sup M ′ ∈B ρ(ξ) (M ),∥ω ′ -ω ⋆ ∥∞≤K ξ ξ U (ω ′ , M ′ ).Similarly to [17] , by prop. C.3 under E 1 p,T (ξ) (defined in lem. C.4) the event E 2 p,T (ξ) (defined in corollary C.3) holds with high probability, and there exists T 1 (ξ, λ) such that for T ≥ T (ξ, λ) we have U (N t /t, M t ) ≤ U ⋆ (ξ) for all t ≥ T 1-p . Further, by the properties of the threshold function β(N t , δ), there exists T 3 (ξ) such that for t ≥ T 2 (ξ) we haveEQUATIONT 2 + CT exp(-2g hp(T ) (λ)ρ) + 2SA exp(-T 1-p ξ 2 ) 1 -exp(-ξ 2 ) ,and thus E[τ ] is finite since g hp(T ) (λ) grows as T p for a fixed λ. Hencelim sup δ→0 E[τ ] log(1/δ) ≤ lim sup δ→0 max(T 1 (ξ, λ), T 2 (ξ), T 3 (ξ, δ)) log(1/δ) ≤ U ⋆ (ξ) 1 -ξ .Letting ξ → 0 concludes the proof.In this section we introduce an alternative result for the forced exploration property with high probability that follows the one proposed in [17] . In addition to the quantities defined in app. C.3, we also define η := η 1 η m and m := max m,.The following lemma is an alternative to lem. C.3, and it is adaptation of [17, Lemma 11] . Using this lemma, one can obtain a 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 λ ∈ (0, 1) we haveEQUATIONwhereEQUATION. Proof. Denote by τ k (z) the k-th time an agent visit a state-action pair z = (s, a), and define the event E = (∀z ∈ Z, ∀k ≥ 1, τ k (z) ≤ f (k)) for some increasing function f : N → N, satisfying f (0) = 0. One can find thatP(E) ≤ SA ∞ k=1 b k , b k := ⌊ f (k)-f (k-1)-1 m ⌋-1 j=0 1 -η m l=1 1 (f (k -1) + mj + l) α+β . For f (k) = λk 4 we have ⌊ f (k)-f (k-1)-1 m ⌋ ≥ λk 3 m and b k = ⌊ f (k)-f (k-1)-1 m ⌋-1 j=0 1 -η m l=1 1 (f (k -1) + mj + l) α+β , ≤ 1 -η m l=1 1 f (k) α+β ⌊ f (k)-f (k-1)-1 m ⌋ , ≤ 1 -η 1 f (k) m(α+β) ⌊ f (k)-f (k-1)-1 m ⌋ , ≤ 1 -η 1 f (k) m(α+β) λk 3 m , ≤ exp -η λk 3 mf (k) m(α+β) . Now, since 1 2(α+β) ≤ m, then we have that m(α + β) ≥ 1/2, thus b k ≤ exp -η λk 3 m√ f (k) = exp -ηk √ λ m . Hence ∞ k=1 b k ≤ 1 -exp -η √ λ m exp -η √ λ m .Finally, the conclusion follows similarly as in [17] .The previous result relies on the following close adaptation of [17, Lemma 20] . Again, we only show the main steps of the proof. Lemma C.6. Fix z 0 ∈ Z, and let P t be the transition induced by the sampling policy π t of MR-NaS. Define the sub-stochastic matrix Q t obtained by removing from P t the row and the column corresponding to z 0 :P t =     Q t [P t (z 0 |z)] z̸ =z0 [P t (z|z 0 )] ⊤ z̸ =z0 P t (z 0 |z 0 )    Then, we haveEQUATIONProof. Define r k (n 1 , n 2 ) := SA-1 j=1 n2 l=n1+1 Q l kj to be the sum of the k-th row of the product of matrices Q l for l ∈ {n 1 + 1, . . . , n 2 }, and observe thatn+m l=n+1 Q l ∞ = max i∈{1,...,SA-1} r i (n, n + m).Since the MDP is communicating, there exists z ∈ Z s.t. P u (z 0 |z) ≥ η 1 and let k * be the corresponding row of z in Q t . Then, using lem. C.1 and the fact that ϵ t = 1/ max(1, N t (s)) α , for n 1 ≥ 1 we have P t ≥ Pu Nt(s) α+β ≥ η 1 /t α+β , and thusr k * (n 1 , n 1 + 1) = SA-1 j=1 (Q n1+1 ) k * j = 1 -P n1+1 (z 0 |z) ≤ 1 -η 1 1 (n 1 + 1) α+β .For n 1 , n 2 ≥ 1, by recursion one can show thatr k * (n 1 , n 1 + n 2 ) = SA j=1 n1+n2 l=n1+1 Q l k * j ≤ r k * (n 1 , n 1 + 1) ≤ 1 -η 1 1 (n 1 + 1) α+β .Similarly, for any i ∈ {1, . . . , SA} \ {k * }, for all n 1 ∈ {1, . . . , m 0 } we haver i (n, n + m) = SA-1 j=1 n+n1 l=n+1 Q l ij r j (n + n 1 , n + m), ≤ 1 -η 1 1 (n + n 1 + 1) α+β n+n1 l=n+1 Q l ik * .To bound the last term, observe that forn i ≤ m n+ni l=n+1 Q l ik * ≥ n+ni l=n+1 ϵ l N l (s) β P u ik * ≥ η m n+ni l=n+1 1 l α+β . Therefore r i (n, n + m) ≤ 1 -η 1 η m n+m l=n+1 1 l α+β ,which concludes the proof.Next, we provide the proof of the δ-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 to have a unique optimal policy for every r ∈ R. Given this condition, we have the following proof of the stopping rule.Proof of prop. 3.1. Let C = {∃r ∈ R : πτ,r / ∈ Π ⋆ (M r)} be the event that at the stopping time there exists a reward such that the estimated optimal policy is not optimal.Let Alt(M ) = ∪ r Alt(M r ). Then, since M τ ∈ M, admitting a single optimal policy for all r ∈ R, we can say that C ⊂ {∃r ∈ R : M ∈ Alt(M t,r )} ⊂ ∪ r {M ∈ Alt(M t,r )} ⊂ {M ∈ Alt(M t )} , where M t,r = (M t , r). ThenP (τ δ < ∞, C) ≤ P ∃t ≥ 1 : tU (N t /t; M t ) -1 ≥ β(N t , δ), M ∈ Alt(M t ) , ≤ P ∃t ≥ 1 : tT (N t /t; M t ) -1 ≥ β(N t , δ), M ∈ Alt(M t ) , = P ∃t ≥ 1 : inf r inf M ′ r ∈Alt(Mt,r) s,a N t (s, a)KL Mt|M ′ r (s, a) ≥ β(N t , δ), M ∈ Alt(M t ) , = P ∃t ≥ 1 : inf M ′ ∈∪rAlt(Mt,r) s,a N t (s, a)KL Mt|M ′ (s, a) ≥ β(N t , δ), M ∈ Alt(M t ) , ≤ P ∃t ≥ 1 : s,a N t (s, a)KL Mt|M (s, a) ≥ β(N t , δ) , ≤ δ,where the conclusion follows from [84, Prop. 1].We have the following adaptation of [85, Lemma F.4 ]. Lemma C.7. Let Y 1 , . . . , Y t be a sequence of Bernoulli random variables. Let F i be a filtration, andEQUATIONFinally, we report the following proposition from [84, 17] that bounds the self-normalized KL process. Proposition C.4 (Prop. 1, [84] and Lemma 15 [17] ). Define the threshold β(N t , δ) := log(1/δ) + (S -1) s,a log e 1 + Nt(s,a) S-1. Then, for all δ ∈ (0, 1) we haveEQUATIONwith the convention that N t (s, a)KL Mt|M (s, a) = 0 whenever N t (s, a) = 0.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 on radio network control problems.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-PSRL, a 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.Here we provide a brief description of the environments.Riverswim. The RiverSwim environment is a classic reinforcement learning benchmark designed to test exploration [54] . It consists of a series of states arranged in a linear chain, where an agent can choose to swim right (downstream) or left (upstream). In the single-reward setting the agent can achieve a positive return by swimming right, but requires overcoming a strong current, making it a less probable event. Conversely, swimming left generally offers small to zero 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 to reach the final state.In figure fig. 3 is shown a depiction of the environment. There are n states, and two main parameters, p, p ′ ∈ (0, 1), and their sum p sum = 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 s 0 , and in every state can only take two actions {a 0 , a 1 }. For small values of p it becomes difficult for the agent to swim right (i.e., reach s n-1 ), and larger values of p ′ can also hinder the progress. On the other hand, swimming towards the left is easier, since the probability of P (s i-1 |s i , a 0 ) = 1. For the experiments, we used n = 10, p = 0.3, p ′ = 0.6.EQUATIONFigure 3 : Riverswim environment [54] . Each tuple (a, p) represents the action a that triggers the transition and the probability p of that event.Forked Riverswim. The Forked RiverSwim environment [53] is 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 a depiction of the environment. There are a total of 2n+1 states, and two parameters p, p ′ ∈ (0, 1), so that p sum = 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 s 0 , and in every state can chose between three actions {a 0 , a 1 , a 2 }. For small values of p 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 i-1 |s i , a 0 ) = 1. For the experiments, we used n = 4, p = 0.3, p ′ = 0.6.EQUATION(a1, p ′ ) (a1, p) (a0, 1) (a1, 1 -psum) (a2, 1) (a1, p ′ ) (a0, 1) (a1, 1 -psum) (a2, 1) (a1, p ′ ) (a2, 1) (a1, p) (a1, p), (a2, 1) (a0, 1), (a1, 1 -p)Figure 4 : Forked Riverswim environment [53] . Each tuple (a, p) represents the action a that triggers the transition and the probability p 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 is no parameter p ′ ).In fig. 5 is shown a depiction of the environment. There are a total of 2n+1 states, and one parameters p ∈ (0, 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 s 0 , and in every state can chose between two actions {a 0 , a 1 }. For small values of p it becomes difficult for the agent to move to the end of the chain in both chains. For the experiments, we used n = 6, p = 0.7.s 0 s 1 s n-1 s n s ′ 1 s ′ n-1 s ′ n ... ... (a 0 , 1) (a 1 , 1) (a 1 , p) (a 0 , 1) (a 1 , 1 -p) (a 1 , p) (a 0 , 1), (a 1 , 1 -p) (a 1 , p) (a 0 , 1), (a 1 , 1 -p) (a 1 , p) (a 0 , 1), (a 1 , 1 -p) (a 1 , p) (a 0 , 1) (a 1 , 1 -p) (a 1 , p) (a 0 , 1), (a 1 , 1 -p) (a 0 , 1), (a 1 , 1 -p) (a 1 , p) (a 1 , p) (a 0 , 1), (a 1 , 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.NArms. This environment is an adaptation to N arms of the original 6Arms environment from [54] . Differently from the previous environments, this is a bandit-like environment, where the agent is presented with n different actions (or arms) to choose from. The agent starts in a state s 0 and selects an arm a i . Upon selecting an arm, the agent may transition to corresponding state s i . 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 in a bandit problem.In fig. 6 is shown a depiction of the environment. There are a total of n + 1 states, and one parameters p 0 ∈ (0, 1). In the figure, each tuple (a, p) represents the action a that triggers the transition and the probability p of that event. The notation a n0:n0+n indicates all the actions in {a n0 , . . . , a n0+n }.The agent starts in state s 0 , and in every state she can select between n actions {a 0 , a 1 , . . . , a n-1 }.For small values of p 0 it becomes difficult for the agent to move to different states. Similarly, it is harder to navigate to states s i for large values of n. We used p 0 = 1 and n = 4. 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 a n0:n0+n indicates all the actions in {a n0 , . . . , a n0+n }. In state s 0 the probability to remain in s 0 for any action a i is P (s 0 |s 0 , a i ) = 1p 0 /(i + 1), with the exception that P (s 0 |s 0 , a 0 ) = 0.s 0 s 1 s 2 ...For the numerical results in the tabular case, we focus on 3 different aspects of the problem: (1) policy estimation error; (2) value estimation error; (3) exploration properties.For the first two aspects we also consider the capacity of MR-NaS to generalize over rewards that do not belong to R, specifically:• MR-NaS uses the canonical basis of rewards R canonical to compute the allocation ω ⋆ t and explore the environments. We also use α = 0.99, β = 0.01.• We also test the generalization capacity of MR-NaS over a continuous set of rewards. At each time step we collect 30 additional rewards from R rnd = {R 1 , . . . , R 30 }, which is a set of 30 reward vectors uniformly sampled from [0, 1] SA , different for each seed. Note that these vectors are not used by MR-NaS to drive its exploration 9 .We consider a discount factor of γ = 0.9, confidence δ = 10 -2 and run each algorithm for T = 5•10 5 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 is a simple adaptation of PSRL (posterior sampling for RL [35] ). PSRL is an episodic algorithm that draws an MDP estimate from a posterior distribution. We adapt PSRL by sampling at the beginning of an episode a random reward vector r in [0, 1] SA , and exploring according to M t,r for that episode. In our case, we simply draw r ∼ Dir(1) from a Dirichlet distribution, where 1 is a vector of ones of size SA. Since we do not consider a finite horizon setting, and both RF-UCRL and RF-PSRL are episodic algorithms, we set an horizon H = 1/(1γ).Policy estimation error. We report in fig. 7 the estimation error of the optimal policies. In the plots we depict the average value of e t,r = |Π ⋆ (Mr)△Π ⋆ (Mt,r)| |Π ⋆ (Mr)∪Π ⋆ (Mt,r)| for a reward r10 , where A△B is the symmetric difference between two sets A, B. Intuitively, e t accounts for both policies that are not accurately estimated and policies that are optimal in M t,r but not in M r . ,. In the first plot we combine together the results for the canonical basis R canonical and the random rewards R rnd . In the second plot we only consider the canonical basis of rewards R canonical , whilst in the third plot we only consider the random rewards R rnd . please, read the attached README file for instructions. In the code, we make use of some code from the Behavior suite [36] , which is licensed with the APACHE 2.0 license.Environment details. The cartpole swing-up problem is a well-known challenge in control theory and reinforcement learning [97] . The objective is to balance a pole attached to a cart by an unactuated joint, where the cart moves along a frictionless track. Control is exerted by applying force to the cart. Initially, the pole hangs downward, and the goal is to swing it up into an upright position and maintain its balance there. Unlike the traditional cartpole balancing problem, this task requires both swinging the pole up and keeping it balanced once upright. Numerical results: rewards chosen by DBMR-BPI . In fig. 14 we plot the value of ∆ t,r estimated from DBMR-BPI . We see that according to the algorithm the third reward, which corresponds to x 0 = 0, 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 a rate of O( √ n), where n is the number of episodes). Rewards corresponding to |x 0 | = 1.5 are harder to learn since the episode terminates if the agent exceeds the x boundary of the environment. Parameters and compute resources. For these simulations we used 1 G5.4XLARGE AWS instance with 16 vCPUs, 64 GiB of memory and 1 A10G GPU with 24 GiB of memory. To obtain all the results 3-4 days are needed. The entire research project needed roughly 21 days of computation time for this experiment.EQUATIONEnvironment details. The DeepSea problem is a hard-exploration reinforcement learning challenge set in an N × N grid. The agent starts in the top-left corner (state (0, 0)) and, in the classical version, aims to reach the bottom-right corner (state (N -1, N -1)) for a large reward. The state vector is an N 2 -dimensional vector that one-hot encodes the agent's position in the grid. The agent can move diagonally, left or right, and down when near the wall. Reaching the bottom-right corner yields a reward of 1. We also incorporate slipping, as described in [53] , so that when the agent selects an action a, there is a 5% probability that a different action a ′ ̸ = 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).s (0,0) s (0,1)s (1,1)EQUATIONs (0,3) s (1,3) s (2,3) s (3,3) Reward functions. We adapt the DeepSea environment to a multi-reward setting by introducing N different rewards, R base = {r 1 • • • , r N }, where r i assigns a positive reward whenever the agent reaches column i in the last row of the grid, that is:r i (s t , a t ) = 1 st=(N -1,i) .To evaluate the capability of DBMR-BPI in collecting unseen rewards, we sampled 20 reward functions R rnd = (r ′ i ) 20 i=1 for each seed. Each reward function is essentially a vector of dimension N (N +1)/2, corresponding to the possible positions in the grid, and is sampled from a Dirichlet distribution with parameter α = (α i ) i , whereα i = 1/(10N ) for all i = 1, • • • , N (N + 1)/2.When the agent is in state s, corresponding to row k, column j, it collects the corresponding reward (r i ) j,k from the reward function r ′ i . We then computed the rewards for these additional reward functions to 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 R base and R rnd for two sizes N ∈ {20, 30}. In tabs. 7 and 8 we report the values at the last time step T of the various metrics considered.In particular, we focus on the distribution of the following random variableX i = 1 T T t=1 r i (s t , a t ),where i is 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.In the figures, and in the tables, the quantity Avg R ({X i }) (sim. the others metrics) indicates the arithmetic mean of {X i } i over the rewards, while GM R ({X i }) indicates the geometric mean over the rewards. We average results across 30 seeds. T T t=1 r i (s t , a t ) (with r i ∈ R base ). Values are multipled by 100 and rounded to the first digit (except for the last plot). Shaded areas depict 95% confidence intervals. For the base case, we report the geometric mean over the rewards, since the arithmetic mean would be a constant for this specific setting (the number of visits in the last row, normalized by t, can be seen as a frequency, and sums up to 1). hence, for this setting the geometric mean is more appropriate [56] .EQUATIONWe also report the metric N i=1 1 Xi=0 , which indicates the number of cells in the last row of the grid that have yet to be visited at a certain time step. (∆ t,r 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 is actually the first one, corresponding to the one that yields positive reward in state (N -1, 0). This is indeed expected, since there are different paths in 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 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 a rate of O( √ n), 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. Parameters and compute resources. For these simulations we used 1 In this section we describe how the DBMR-BPI can be applied to the Downlink link adaptation problem [37] in radio networks.Overview. Link adaptation, or adaptive modulation and coding (AMC), is a technique used in wireless communication systems, such as the 3GPP HSDPA, LTE or NG-RAN, to dynamically adapt the transmission rate of a communication link to the time-and frequency-varying channel conditions [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 as 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 as each transmission time interval (e.g., on a sub-millisecond time-scale in the 3GPP NG-RAN system) wherein a communication is scheduled between a 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).Link adaptation algorithms attempt to optimally adapt the transmission data rate chosen for a 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. Problem Objective. In wireless communication systems, there is a fundamental trade-off between throughput and spectral efficiency, which can be understood in terms of resource elements. Resource elements are the smallest units of time-frequency resources allocated for transmission, encompassing a specific duration of time and a specific frequency bandwidth. Our objective is to explore the environment using DBMR-BPI to design policies that optimize this trade-off based on the desired intent.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 to various influencing factors, we consider Transport Block Size (TBS) as a 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 TBS does not necessarily result in higher throughput, as a larger TBS can lead to a higher Block Error Rate (BLER)-the percentage of transport blocks that fail to be decoded correctly-impacting the reliability of data transmission and reducing the actual amount of successfully received data.Environment, RL formulation and setup. We consider a Time-Division Duplexing (TDD) 5G system operating at a 3.5GHz carrier frequency, with PHY layer numerology µ = 0 of the 3GPP technical specifications 38.211 and single-user Multi-Input 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 a 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.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 a packet from a UE is modeled as an episodic MDP of at most 5 steps. At each time step t, the agent chooses an action a t (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 proprietary simulator 11 , the code for which cannot be disclosed. We evaluated the DBMR-BPI algorithm along with RND, APT and Disagreement.Reward design. We consider two rewards, that optimize for different intents. For each episode we let z t be a boolean value indicating if the packet was successfully transmitted (ACK) or not (NACK).We also let T BS n indicate the transport block size for the n-th transmission, and N re,n the number of resource elements for the n-th transmission.1. Transport block size: r 1,n = T BS n • 1 zn=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 of successfully transmitted packets. 2. Spectral efficiency: r 2,n = 0 if the transition is not terminal; otherwise, r 2,n = -k≤n N re,k , 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).E.1 DBMR-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 ⋆ (ω; M ).To circumvent these issues, we adapt the DBMF-BPI algorithm from [53] , where the authors propose DBMF-BPI, 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 ω∈∆(S×A) U ⋆ (ω; 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-BPI, 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 -function). More precisely, the extension of DBMF-BPI 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 DBMR-BPI (sim. the M -function) learns the value for multiple rewards. In the finite action setting this implies that there are AR values to estimate in every state. Alternatively, we also tried to feed the networks with a one-hot encoding of the chosen reward, but this resulted to be less effective in terms of model capacity.2. Reward exploration. We explore according to the difficulty of the reward function. For the sake of stability, at the beginning of each episode (or, for example, every ≈ 1/(1γ) steps) we sample a reward r ∼ R to explore, and apply DBMF-BPI on this reward. To estimate the exploration difficulty, we simply use the estimate at time t of the minimum sub-optimality gap ∆ t,r (see paragraph below), and explore a reward r with probability ∝ 1/∆ 2 t,r . In addition to the mechanism described above, we also introduce a random uniform exploration of the rewards and forced tracking of the rewards:• Random exploration: with probability p unif orm we choose a reward uniformly at random.• Forced tracking: this mechanis ensures that each reward is explored sufficiently often. We let U t = {r ∈ R : √ t -N r,t /2 < 0} be the set of under-sampled rewards at time t, where N r,t is the number of times the algorithm has chosen reward r in the previous t steps, and choose r = arg min r N r,t whenever U t is non-empty (otherwise, we sample it as in Alg. 2). This procedure guarantees that each reward is sampled at a rate of O( √ t) [20] .Algorithm 3 DBMR-BPI -Reward selection 3. Estimation of the sub-optimality gaps ∆ t,r . To estimate the minimum sub-optimality gap for a fixed reward r, we initially used the method described in DBMF-BPI. However, their estimates are often overly conservative. In DBMF-BPI, the minimum gap for each batch across all models in the ensemble is calculated and added to a rolling window. The smallest value in this window is then used as the target for stochastic approximation, employing a decreasing learning rate.We instead compute ∆ t,r as follows: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 ∆ t,r . This approach is less conservative than taking the minimum across both transitions and models in the ensemble. 2. We treat ∆ t,r as a learnable parameter and use the estimated gap ∆t,r as the target value.We compute the Huber loss between ∆ t,r and ∆t,r , and perform a gradient step to update ∆ t,r .3. To further stabilize the estimate of ∆ t,r , we can apply Polyak averaging over time steps.The main parameters for DBMR-BPI are as follows: SymbolFor APT, Disagreement and RND we used the open-source implementation from [24] . However, the implementation in [24] only works for continuous action spaces, therefore we adapted the implementation to discrete action spaces as described below. For all the algorithms we used the same architecture as in the original papers, and only did a slight tuning of the hyper-parameters. Learning rate of Adam Table 12 : DQN parameters.APT Agent. This agent uses a forward network F θ and a backward network B θ to learn a representation that is used to compute the intrinsic reward. The forward network predicts a representation of the next state ŝt+1 given the current state s t and action a t , while the backward network predicts the action that was taken ât given two consecutive state representations s t , s t+1 .The representation is N rep -dimensional, and is learnt by a trunk network M θ .The loss is computed by averaging over a batch B the forward and backward errors. The forward error is computed as in [24] e f orward (B) = 1 |B|(st,at,st+1)∈B ∥F θ (M θ (s t )) at -M θ (s t+1 )∥ 2 ,where F θ (•) a is the a-th predicted representation.We adapt the backward error to discrete action spaces by using the cross-entropy loss e backward (B) = -1 |B|(st,at,st+1)∈B a 1 (at=a) log(B θ (M θ (s t ), M θ (s t+1 )) a ),• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: Yes, the authors followed the NeurIPS Code of 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., if there is a special consideration due to laws or regulations in their jurisdiction).DBMF-BPI learns an ensemble of Q-values, as well as the k-th moment of the Q-values.Here we have different constants compared to[16]. In that work, we believe the authors may have miscomputed the constants by using the logarithm in base 10 instead of the natural logarithm.In this context, by a continuous set, we are not necessarily referring to a connected set in R n , but rather to a set with a non-countable number of elements.Alternatively one may consider the conic hull of R ′ , yielding a similar resultWe indicate by ei the i-th element of the canonical basis.For simplicity, and w.l.o.g., we consider hp(T ) as an integer in the summation.For simplicity, and w.l.o.g., we consider T q as an integer in the summation.For simplicity we consider max(T1(ξ, λ), T2(ξ), T3(ξ, δ)) as an integer.Since we use the canonical basis the second assumption (CH) in thm. B.3 is satisfied.In the expectation the reward r is a random variable.The environment design and MDP formulation come, or are inspired, from a forthcoming publication[99]. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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. 


3. The abstract would be better if providing a more impressive motivation for multi-reward RL, emphasizing its significance and potential impact.

4. 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.
questions: questions: Please address the issues mentioned in the weaknesses.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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,

1. 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.

2. 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. 

3. 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.

4. 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.

5. 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.

6. Some minor aspects:
    - Grammatical errors need to be addressed, e.g. Line 354, line 91.
    - 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.
questions: questions: 1. Do we treat MR-BPI as dedicated exploration strategies for multi-objective RL?

2. 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?

3. 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: limitations: There are no unaddressed ethical considerations in the studied context.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: questions: Here is a number of questions and comments.

- $\alpha$ should also be an input for the algorithm 1. Why is there no dependence on $\alpha$ in the theoretical results?
- 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?
- 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.
- 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.
- 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.
- 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".
- I cannot see a scaling in the number of rewards. Is there any theoretical understanding on how $\tau$ scales in the number of rewards?
- 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. 
- 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: 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.

There 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.

Comments: title: Thanks for the answers - I will keep my 7.
comment: Thank you for your time and feedback! We are glad our response was able to clarify the concerns you raised, and we appreciate you taking the time to reconsider and update the score accordingly.
Thank you for your rebuttal, I've revised my score to 6.
We appreciate the reviewer's feedback and understanding. 
 
However, we have already acknowledged the differences between our work and these other settings (see lines 33-42 and the discussion in Section 5), and we are committed to further clarify the distinction.

We have already extensively compared our approach with reward-free RL in both the tabular and deep settings (both in the main text and in the appendix), as it is the closest existing framework to ours in terms of exploration objective.

Regarding multi-objective RL,  we remark that our focus is on a different exploration objective, since we are not interested in identifying the Pareto frontier of non-dominated policies. Currently, there are  no best policy identification techniques available for multi-objective RL, making a direct comparison impractical (which would merit a separate, dedicated study).

We hope these clarifications address the reviewer's concerns and help in understanding the scope and contributions of our work.
I thank the authors for their detailed response.

As pointed out the authors, the studied multi-reward setting, reward-free RL and multi-objective RL does share similarities with different emphasis respectively. Hence, it would be important to provide a rigorous comparison between all these settings to clearly credit their own strengths and articulate the differences. It is essential to acknowledge such difference especially when it is not a fair comparison, so as to avoid misunderstanding for future studies. Effort should be made to provide a better understanding.

As such, I prefer maintaining my current score while not championing for a reject. I do think results of the multi-reward setting could be interesting, but more careful revision would be extremetly beneficial.
Thank you again for your support! We completely agree with you. In the revision, we will make sure to provide clearer explanations of the background and main ideas behind this family of techniques.
Thanks for your answers! I believe the article is really good and I would even consider an 8 if the article would be much better understandable for more than a handful of experts in the field. In your own interest in spreading your ideas to a wider group of researchers I would suggest to really use the revision for more explanations.