Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Authors: Alessio Russo
Aldo Pacchiano
Venue: ICML 2025 poster (2025)
Keywords: policy evaluation
multi-reward
multi-policy
adaptive exploration
pure exploration
reinforcement learning
Primary area: reinforcement_learning

Abstract: We study the policy evaluation problem in an online multi-reward multi-policy discounted setting, where multiple reward functions  must be evaluated simultaneously for different policies. We adopt an $(\epsilon,\delta)$-PAC perspective to achieve $\epsilon$-accurate estimates with high confidence over finite or convex sets of rewards, a setting that has not been systematically studied in the literature. Building on prior work on Multi-Reward Best Policy Identification, we adapt the MR-NaS exploration scheme  to jointly minimize sample complexity for evaluating different policies across different reward sets. Our approach leverages an instance-specific lower bound revealing how the sample complexity scales with a measure of value deviation, guiding the design of an efficient exploration policy. Although computing this bound entails a hard non-convex optimization, we propose an efficient convex approximation that holds for both finite and convex reward sets. Experiments in tabular domains demonstrate the effectiveness of  this adaptive exploration scheme. Code repository: https://github.com/rssalessio/multi-reward-multi-policy-eval.

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Alessio Russo Aldo Pacchiano
1.2
Abstract
There are several applications where one has multiple poli- cies to evaluate, e.g., multiple policies arising from using different hyperparameters (Dann et al.. 2023; Chen et al., 2024; Poddar et al., 2024). Similarly, multiple reward func- tions often arise in real-world decision decision-making problems, making it crucial to evaluate how policy performs across diverse objectives. As an example, large language models (Brown et al., 2020) are fine-tuned on human feedback that spans a wide range of user preferences and goals (Ziegler et al., 2019; Rafailov et al., 2024; Poddar et al., 2024), ef- fectively producing multiple distinct reward signals. Other applications, similarly, involve multiple rewards, such as: user-pref user-preference modeling, robotics tasks aiming to reach different goals, or based radio network optimization (Nahum et al., 2023; De Alwis et al., 2023; Russo & Van- nella, 2024; Poddar et al., 2024).
We study the policy evaluation problem in an online multi-reward multi-policy discounted set- ting, where multiple reward functions must be evaluated simultaneously for different policies. We adopt an (c, 6)-AC perspective to achieve c-accurate estimates with high confidence over finite or convex sets of rewards, a setting that has not been systematicllly studied the literature. Building on prior work on Multi-Reward Best Policy Identification, adapt the MR-NaS ex- ploration scheme (Russo & Vannella, 2024) to jointly minimize sample complexity for evalu- ating different policies across different reward sets. Our approach leverages an instance-specific lower bound revealing how the sample complex- ity scales with measure of value deviation, guid- ing the design of efficient exploration policy. Although computing this bound entails hard non-convex optimization, we propose an efficient convex approximation that holds for both finite and convex reward sets. Experiments in tabu- lar domains demonstrate the effectiveness of this adaptive exploration scheme. Code repository: https: : / httpttt.oooooo..ccooooootoot rssa ess /ssss/mumuuuu 1ti Iti-reward meweaarddmultii pottiiipooiy--vvaer
In general, is challenging to efficiently and accurately evaluate a policy over multiple objectives, potentially for multiple policies aimed at solving different tasks (Sutton et al., 2011; McLeod al., 2021; Jain al., 2024). In- deed, when multiple policies and distinct reward sets involved, it is not obvious how best to gather data in way that balances efficiency and accuracy.
Prior research approached this issue in different ways. One direction aims to minimize the mean squared error (MSE) of the value estimator (or the variance of the importance sam- pling estimator) to guide adaptive exploration. In (Hanna et al., 2017), this is done for single-reward policy evaluation. In (Mukherjee et al., 2022) they study single-reward pol- icy evaluation in tree MDPs, and propose variance-driven behavior policy that minimizes the MSE. Similarly, Jain et al. (2024) propose a variance for a finite collection of policy-reward pairs. However, these methods may not always guarantee sample-efficient exploration or provide (e, 6P- guarantees on the sample complexity. Weissmann et al. (2025) recently introduced a sample-efficient behavior-policy design for evaluating mul- tiple target policies and proved (c, 8) excess-risk guarantees; their results, however, apply only to single-reward stochastic bandit models (Lattimore & Szepesvári, 2020). In (Dann et al., 2023; Chen et al., 2024) the authors address multi- policy evaluation for single reward under the (c. 8P-A criteria in episodic MDPs. However, their sample com- plexity guarantces are instance-dependent in the transition
1. Introduction
This paper investigates methods for efficiently evaluating one or more policies across various reward functions in an online discounted Markov Decision Process (MDP) (Put- erman, 2014), key challenge in Reinforcement Learning (RL.) (Sutton& & Barto, 2018), where the aim is to compute the value of each policy. Accurate value estimation serves many purposes, from verifying a policy's 'sss effectiveness to providing insights for policy improvement.
exploration scheme
Faculty of Computing and Data Sciences, Boston Univer- sity, Boston (MA), USA. "Broad Institute of MIT and Har- vard, Boston (MA), USA. Correspondence to: Alessio Russo aauuss2@bb.cduu
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adaptive Exploration for Multi- Muwai- Multi-Policy Evaluation
dynamics (e.g., dependent on state-action visitation struc- ture) but not in the reward. Consequently, these bounds do (e (V7 similar to the variance of the value:
not characterize how the interaction between rewards and transitions- -ucch as sparse rewards under specific dynam- ifs-affects evaluation complexity.
o sup
1² (3, 5') (EE,,,ERR S, e² > (8, π (+))
max
where w" is the stationary distribution induced by the explo- ration policy" !
To investigate the problem of devising an exploration strat- egy for this setting, we study the sample complexity of multi- reward multi policy evaluation, and adopt an (e. 5)-PAC viewpoint to achieve e-accurate estimates with confidence 1-6 6 over finite or convex sets of rewards. Furthermore, while prior works focus on estimating the expected value of a policy under the initial state distribution, our work evaluates policies across all states (a value vector). This broader scope is critical for applications requiring reliable verification of policy behavior and enabling explainable RL (Puiutta & Veith, 2020; Ruggeri et al., 2025).
Finally, we adapt MR-NaR (Russo & Vannella, 2024), an ex- tension of Nas (Al Marjani et al., 2021). to our setting, and prove its asymptotic optimality for policy evaluation up to a constant factor. We further illustrate its practical efficiency through experiments in various tabular environments.
2. Related Work
Reinforcement Learning (RL) exploration techniques have typically focused only on the problem of learning the op- timal policy for a single objective (Sutton & Barto, 2018). This domain has generated a vast body of work, often inspired by the multi-armed bandit literature (Lattimore & Szepesvári, 2020), with approaches ranging from e- greedy and Boltzmann exploration (Watkins, 1989; Sutton & Barto, 2018) to more sophisticated methods based on Upper- Upper-Conf Bounds (UCB) (Auer, 2002), Bayesian procedures (Oshand et al., 2013; Russo et al., 2018) or Best Policy Identification techniques (Al Marjani et al., 2021; Wagenmaker al., 2022; Taupin et al., 2023).
Our approach optimizes the behavior policy to maximize the evidence gathered from the environment at each time-step, and builds on techniques from the Best Policy Identifica- tion (BPI) literature (Al Marjani et al., 2021), which itself draws inspiration from Best Arm Identification techniques in bandit problems (Garivier & Kaufmann, 2016; Kaufmann et al., 2016; Russo & Proutiere, 2023b; Russo et al., 2025). These methods cast the problem of finding the optimal pol- icy as a hypothesis testing problem. The core insight is to establish an instance-specific sample complexity lower bound- as an optimization problem-where its solution directly yields the optimal exploration distribution.
Despite these advances, the challenge of designing explo- ration strategies for online policy evaluation has received comparatively little attention. Early work in this direction examined multi-armer bandit problems (Antos et al., 2008) and function evaluation (Carpentier & Munos, 2012), show- ing that efficient exploration requires allocating more sam- ples where variance is higher. Linke et al. (2020) considered bandit setting with a finite number of tasks, and focused minimizing the mean squared error. Still within the bandit setting, Weissmann et al. (2025) recently proposed behavior-policy scheme for evaluating n target policies and established (c, 6) excess-risk guarantees. For o--sub Gaussian rewards, their sample-complexity bound scales as e
Building on insights from Multi-Reward BPI (Russo & Vannella, 2024), which extends the BPI framework to multi- ple rewards, we develop an instance-specific sample com- plexity lower bound for multi- reward multi-policy evaluation, dependent on the dynamics and the rewards. To our knowledge,
Reward sets Rr, Policies
T1
T
Optimal colaecollection strategy w'
this constitutes the first such bound even for the single- policy single-reward case. Furthermore, for convex reward sets, we present an alternative sample complexity characteri- zation compared to (Russo& & Vannella, 2024), which yields a closed-form solution when the set of rewards includes all possible rewards.
o"'" log(n/6)) where w* is the maximal importance-
sampling weight (upper-bounded by n))
For MDPs, Hanna et al. (2017) introduced the idea of op- timizing the behavior policy (i.e., the exploration strategy) by directly minimizing the variance of importance sam- pling-one of the earliest efforts to design an exploration strategy specifically for policy evaluation in MDPs. In (Mukherjee et al., 2022) the authors studied single-reward policy evaluation in tree MDPs, and proposed a variance- driven behavior policy that minimizes the MSE. Separately, (McLeod et al., 2021) proposed SF which uses the Suc-
Our result exhibits a sample complexity that scales with the worst-case policy-reward pair-rather than the sum capturing the inher-
over individual policy-reward ent difficulty of efficiently evaluating all combinations si- multancously. Particularly, the complexity scales accord- ing to a measure of value deviation p.. (8,8') s') == V." (6')
'In this work, use the terms "exploration policy" and "be- havior policy" interchangeably.
2

---

Adaptive Exploration for Multi- Multi-Policy Evaluation
cessor Representation framework (Dayan, 1993) guide exploration for value estimation over finite set of tasks. Additionally, in another line of research, Papini et al. (2024) analyzed the behavioral policy optimization problem for policy gradient methods. More closely related to our work is (Jain et al., 2024), where the authors tackled the evalu- ation of a finite set of policy-reward pairs and proposed GVFExplores foeer, an adaptive exploration method that op- timizes the behavior policy with the goal of minimizing the estimation MSE. Their resulting exploration policy is variance-driven, and resembles that derived by Mukherjee et al. (2022). However, these works do not provide PAC guarantees, nor directly provide a strategy that directly min- imizes the sample complexity.
Markovian policy т S - A(A) that maps states to distributions over actions (Puterman, 2014). For Marko- vian policy π we define the discounted value of in M, at state s as V,5 (s) = IET 1E 7" rrs,r,,s 0e) = s), where Se:
S1+11 ~ P(.|Se: (t) and dz ~ T(((+)) (if x is deterministic,
we write ae = (T;))) We also write V.T and omit the depen- dency on M when it is clear from the context. We also define (s) max, (s) to be the optimal value in over all Markovian policies. We further define the action- value fune- tion in M, as Q7 (s, a) == r(8, a) + - (V (s'))
Additional notation. For set U C R"," E N, we denote by U its closure, and we also define A(U) to be the set of distributions over U. We also denote by Ne(8, a) = Ex=1 1 ((saa)))=((aa)) the number of times an algorithm has visited a state-action pair (s,a) up to time (sim. we define Ne(s) = En NN((s, For two MDPs M, M'' with transition functions, respectively. P, P., we write KTpp (8, a) to indicate the KI--divergence be- tween the two transition functions in (s,a) E 8 A (we also write KL KL a)).)) We denote by kl(xr,) = x log(z/v) + (1 - I) log((1 - x)/(1 - y)) the Bernoulli KL--divergence between two parameters x. y E [0. 1].
In (Dann et al., 2023) they investigated the multi-police single-reward evaluation problem in a PAC framework. They proposed an on on-policy method that leverages the fact that the policies may overlap in significant way. In (Chen et al., 2024) the authors designed behavior policy that op- timizes the coverage of the target policy set. However, these works do not provide instance- mestance-dependent bounds in terms of the value of the target policies, nor study the multi-reward policy evaluation problem.
Assumptions. We consider the problem of evaluating a finite sel of deterministic target policies IT = {m.,..., .r) over finite, or possibly convex, reward sets (we discuss more on this in the next paragraph). On the MDP M, we impose the following assumption.
3. Problem Setting
In this section, we describe the MDP model considered and the policy evaluation setting.
3.1. Markov Decision Processes (MDPs)
Assumption 3.1. The MDP M is communicating and ape- riodic under uniform policy, and the learner has prior knowledge of P. The starting state is also arbitrary.
Markov Decision Processes (MDPs) are widely utilized to model sequential decision-making tasks (Puterman, 2014). In these tasks, each time-step t = 1,2.... an agent observes the current state of the MDP st and selects action 02 to achieve a desired objective. This objective is encapsulated in terms of a reward ra E [0, I]. observed after
As in (Al Marjani et al., 2021; Russo & Vannella, 2024), we assume that the MDP is communicating, which avoids the awkward case where the algorithm could enter a subclass of states from which there is no possible comeback, and thus it becomes impossible identify the value of a policy π to the desired accuracy. Lastly, the assumption of aperiodicity can be met by assuming that the exploration policy assigns positive probability to some state-action pair (s, a) satisfy- ing ((s a) > O. Such assumption is needed to ensure ergodicity of the chain induced by the exploration policy.
selecting the action. In RL, the primary goal of the agent is to determine a sequence of actions that maximizes the total reward collected from an unknown MDP.
Discounted MDPs We consider discounted MDP (Put- erman, 2014) of the type M- = (8, A, P,7), where: S is finite state space of size S = (S] A is a finite action space of size A = AA; P S A + A(S) is the transition function, which maps state-action pairs to distributions over states; lastly, 7 E (0, 1) is the discount factor. the follow- ing we consider also reward functions r : S X A - [0, 1] that are bounded and deterministic functions of state-action pairs, and write M, (M, to denote the MDP M with reward r. In classical RI., an agent is interested in max- imizing the total discounted reward collected from M,:: Ti + +y22 + 72ra +.... The problem of computing an optimal sequence of actions (i.c., that maximizes the to- tal discounted reward) can be reduced to that of finding
Set of Rewards. In the following, we consider sets of reward functions R that are either finite, or convex, and assume that these sets are known to the agent beforehand. For tabular MDPs (i.e., with finite state-action spaces), as- suming a natural labeling of the states S = ={31.-. {s.,.... (5)) we represent reward r, for policy π, as a vector in [0, 1| (for simplicity, we omit the dependency on т). The i-th ele- ment of r corresponds to the reward r(s;, π (s:)). For n, we indicate the canonical reward set by R = fei,...,es! est in RSS with e being the i-th vector of the canonical basis, defined as (et), = ((==)); j,j E 5). Lastly, we
3

---

Adaptive Exploration for Multi-Rewaa Multi-Policy Evaluation
denote the R [0, 1] case as reward-free since it encom- passes all possible rewards for n.
In the following section, we investigate the sample complex- ity of this problem and determine the minimal number of samples required to achieve the (e, 6) -PACC guarantees. Our analysis reveals that the problem can be more challenging under certain rewards. In fact, the sample complexity is gov- erned by the most difficult policy-reward pair in θ, rather than the sum of the individual complexities across pairs.
3.2. Online Multi-Reward Multi-Policy Evaluation
In an online single-reward Policy Evaluation (PE) set- ting, the objective is to learn the value vector of sin- gle policy-reward pair rT) In the multi-reward, multi- policy case, we aim instead to learn the value vectors for @ = ((T, Rz) : x E [T], meaning each policy и E IT is evaluated on every reward in its own reward set Rr, which can differ across policies.
4. Adaptive Exploration through Minimal Sample Complexity
We seek design a data collection strategy achieving mini- mal sample complexity. Building BPI techniques (Gariv- ier & Kaufmann, 2016; Al Marjani et al., 2021), we first derive an instance-specific sample complexity lower bound for any (c, 6)-P algorithm.
This setting is closely related to off- off-policy policy evaluation (OPE) (Thomas & Brunskill, 2016; Precup, 2000). However, OPE does not typically focus on the problem of optimizing the data collection policy. In this work, we study the prob- lem of devising an optimal data-collection policy that, by online interactions with the MDP M, permits the agent to learn the value of pairs (T, R₂) E θ as quickly as possible up to the desired accuracy.
This bound, which is posed as an optimization problem, specifies the optimal exploration policy, enabling the deriva- tion of an efficient algorithm. The key step lies bounding the expected log-likelihood ratio between the true model M and a carefully constructed "confusing" model M'.
Online Multi-Reward Multi-Policy Evaluation. We for- malize our objective using the (e, 6)-AAC (Probably Ap- proximately Correct) framework. In such framework, algorithm Alg interacts with M until sufficient data has been gathered to output the value of ı up to accuracy for any reward r E Rg for all π E II, with confidence 1 6.
4.1. Set of Alternative Models
Confusing models are alternative models that are "similar" to M, but differ in certain key properties. As we see later, the set of alternative models is crucial for establishing a lower bound on the sample complexity т. To prove the lower bound, we frame the sample complexity problem as goodness- test: does the observed data better align with the true model M an alternative model M'?
Formally, an online PE algorithm Alg consists of:
a sampling rule (0t)<21: upon observing a state St, Alg selects an action at. and then observes the next state St+1 ~ P(-|st, az).
We seek model M' that is confusing- that is, it is "sta- tistically" close M (in the KL sense), yet differs by at least 2e in the value of a policy under some reward r (we discuss later why we choose 2e and not c). To find M', we first construct the set of alternative models. Formally, for a policy E II, reward r E Rx, the set of alternative models in (T, r) is defined as
stopping rule т that dictates when to stop the data collection process. 7 a stopping rule w.r.t. the filtra- tion (Fi) where Fi o o($11,0, (1,......... 0t-1, 8t } is the o-algebra generated by the random observations made under Alg up to time t.
an estimated value V==: at the stopping time т, Alg returns the estimated value V7"T of the policy æ E in M for any chosen reward r E R,,
Alls, Gr (M) = {M, M < My IV - VV > 2
Denoting by M (resp. Ear) the probability law (resp. ex- pectation) the data observed under Alg M, we define an algorithm to be (c, 5)CPAC follows.
where M"- = AS r,, is an alternative MDP, and we index the transition function P. by the corresponding reward r for clarity. The notation M < M means that P(s, a) is absolutely continuous with respect to (, a) for all (s, a) (and P is the transition function of M). We also denote by Alt (M)) = Uren,rER, 5 the entire set of alternative models over R.
Definition 3.2 ((c, PAC algorithm). An algorithm Alg is said to be multi-reward multi-policy PPAC if, for any MDP M, rewieiss-rewards set Ô, E (0, 1/2) and E (0, ) ), we have P FM[TT= < xo] (the algorithm
From a sample complexity perspective, we can interpret this set follows: larger set of alternative models may lead to increased sample complexity since it becomes more likely that one of these models is statistically close to M as measured by their KL divergence. Hence, we should expect the learning complexity to be dominated by the "worst" among such models.
stops almost surely) and
PM 3 e 3r E R₂ II - 1o > 2
< (1)
In other words, with probability at least 1 1-8, the algorithm's estimate V.2T is within e of V for every r E RT, π E IT.
4

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Note that we require | Mr Ilee 2e, rather than just
2.. States with smaller values of ll (+)] so do not strongly affect the sample complexity. Additionally, Lemma B.3 (in the appendix) indicates that the maxi- mum max, I (s, s')l is typically attained at s' + Finally, if max [Ip. lo = 0, the set 2 is empty for any values of and 7, implying no confus- ing models exist under such conditions.
If the separation were only e, an estimator V/-T satisfying ||VTT- - VMr loe I could also be simultancously e-accurate for an alternative model M' satisfying IIVM. Var; Ix > making the models indistinguishable. Requiring 2e separa- tion prevents this ambiguity. While this choice potentially weakens the resulting lower bound, we believe the looseness at most a constant factor (see Theorem 5.2).
Regarding the last point, in the following proposition, proved in Appendix 1.1.3, we provide a sufficient and nec- essary condition for max, llp, (s)]lx = 0.
Lastly, consider the case where the set All (M) is empty
for some pair (IT, r). In this situation, any model p' sharing the same support / yields value that is 2e-close to the true value. Thus, the learning challenge for that reward is rather minimal. Therefore, characterizing when these sets are empty is crucial in the analysis. In the following, we denote by R = fr& E R₂ Alt (AT) * 0} the set of rewards for which the corresponding set of confusing models non-empty.
Proposition 4.2. The vectors for which max, [Ip (s) = 0 is precisely the set {al: : a [0. 1]. where 1 is the vector of ones.
While may seem obvious that the all-ones reward cannot produce an alternative model, is noteworthy that no other reward satisfies max, ll (s)ll = 0.
To analyze these confusing sets, and their implications for sample complexity, we define the following instance-dependen quantity, that we refer to as the one-step value deviation:
Value deviation.
We are now ready discuss the sample complexity, and we refer the reader Appendix 1.1.3 for further discussion on the set of alternative models, including characterization of when p. (s, s) is identically zero across all states.
(8, = (5) P(m (V, (9) Vs,8's E S.
4.2. Sample Complexity Lower Bound
This quantity measures how much the value at state s' deviates from the expected value under at As we see later, it is "easier" to construct alternative models if (s, )[ is large. We also define these quantities in vec- tor form p7 (s) = [p] (s, .1)
As a consequence of Proposition 4.1, the analysis of the sample complexity must necessarily take into account the reward sets. However, for clarity, we adopt the assump- tion that for every state there exists confusing model (see Prop. 4.1). While not strictly necessary (one could work with RS instead), this assumption simplifies our analysis. Assumption 4.3. For every state E S there exists π E 11, E R2 such that II (s) 25.
P. (s. s5]] so that |IeF(s) = max, lp (s. s') is the maximum one-step de- viation at The deviation p.. is closely related the span of the value function sp(V,7 == max.' (s" min, V (s).. but, is in general smaller than the span (see Lemma B.3).
Using this measure of value deviation p/, we are able to provide necessary and sufficient conditions under which A is empty or not (see proof in Appendix B.I.I).
To derive the sample complexity lower bound, define the characteristic time Te(w; M) of a stationary state-action distribution under M:
Te(w; M =
inf R,,T,,R
En (KLp)p a)l,
Proposition 4.1. Fix a policy E II and a re- ward RT We have the following condi- tions: (1; necessary) if (MM) # @ then 3s E S (s)]lo <(1-7), (2; sufficient) if 5, then A + 0.
(2)
where (s, ~ W. In this optimization problem, we seek an alternative model M' that is confusing, i.e., that minimizes the statistical difference from the true process M under some pair rT. Conversely, the sampling distribution w serves to gather evidence distinguishing M from any such alternative. Hence, the reciprocal T, (w(:;; M) can be interpreted as the cntermationngatherinnn rate under w in M.
3s S [1) > 2e
The proposition offers key insights into the challenges in- volved in learning the value function:
As increases or y decreases, the necessary condition in Proposition 4.1 is less likely to be satisfied, poten- tially leading to a decrease in the number of alternative models (which suggests a smaller sample complexity).
Consequently, an optimal exploration strategy chooses w to maximize this rate. From this perspective, one can show that, asymptotically, the sample-complexity lower bound for any (e, 6PPCC algorithm scales as
The proof highlights the concept of confusing states: a state 8 considered confusing if ||p; (s) >
T (M) inf (w M). WEΩ(M)
(3)
5

---

Adaptive Exploration for Melti-Reward Multi-Policy Evaluation
where denote by Wopt ((MM a solution to the optimization in Eq. (3), and ((M) is defined as the following set of stationary state-action distribu-
(0. Ps) 22 (0, 1)
01 (ri, ps)
a1 (rs, - pt)
tions: (2M) = { E ASS x A) : (E.((s, = Ex P(s)s',a'Jw(s a')(('','')) Vs) and a(s > O V.s
(0.ps)
81
82
We have the following asymptotic lower bound, and the proof of the theorem can be found in Appendix B.2.1.
a2 (0, P2)
02 (12, P2)
Theorem 4.4, Under Assumption 4.3,for any (c PAC algoritium we have
Figure I. In this MDP (v. Example 4.6), in each edge it indicated the action and the corresponding reward and transition probability.
E[r]
lim inf 8- log(1/5)
2 (M).
(4)
This result is general, and also applies to Linle-policy single-reward cases. Moreover, we understand that an op- timal exploration policy needs to frequently sample states with large deviation gaps II [s)). This intuition will be used to devise an exploration policy.
As discussed earlier, an exploration strategy matching the information gain T (M) maximizes the evidence collected per time-step required to distinguish between the true model M and a confusing one.
Scaling. Last, but not least, the lower bound expression does not clearly reveal its scaling behavior or its connection to the value deviation p. While we have briefly touched upon this relationship, these aspects are explored in greater depth in the next section, where a convexification of the problem provides further insights into these properties.
This problem can be framed conceptually as a zero-sum game: the explorer seeks to maximize (w M)- over w, while an adversary selects a confusing model for some policy-reward pair to minimize this value. Consequently, the sample complexity is determined by the most difficult volicy-reward pair to discriminate from the true model.
4.2.1. CONVEXITY OF THE LOWER BOUND
However, it may seem counterintuitive to use exploration strategy that depends on the true model itself M, since it is unknown. In practice, we use the empirical estimate of the MDP M, at time-step & to derive an exploration strategy. We defer this discussion to Section 5.
We find that it is hard to directly optimize T. (w;; M), since the optimization over the set of alternative models may be non-convex. Observe that the set Alt, sr (M) can be seen as the union of two sets {M' max, Vřr (s) VM (s) 2 2c] and {M' max, Mr (s) - VM, (s) 2 2c}. The convexity of these sets depends (л, r, P) and, even if convex, may be disjoint. The following example illustrates this aspect.
Optimality of behavior policies. A natural question is whether we can use this result to identify when an explo- ration policy is suboptimal. For instance, consider the MDP in Figure and the single target policy x-Iss) 02 Vs. For that MDP, it is in general sub-optimal sample according to such policy, since under state L becomes transient. In the following lemma we prove that necessary condition for an optimal exploration policy is to guarantee that states with large deviation gap are visited infinitely often.
Example 4.6. Consider the MDP in Figure I with the larget policy (51) a2 and ($22 01. The value functions
Vi (p
10P
Lemma 4.5. Let Th be the set of transient states (i.e., not recurrent) under a behavior policy ve- As- sume that T + 0. If there exists Se E T x E II E Rx such that lIPT (se)lloo > 22/7, then ne not optimal, in the sense that
PMN
10
2+
10-2
0.4
0.6
0.8
1.0
T.dd"s; M) O,
(5)
P2
for any stationary distribution d= (of the chain px.) induced by We.
Figure 2. Plot of V Vx for varying values of pa in M' (the other parameters are the same in both MDPs). The param- eters P2o 0.56 and pas 0.41 are both confusing parameters for e = 0.03 (above the red linc), but their average Pzm is not.
The proof for this lemma can be found in Appendix B.2.2.
6

---

Adaptive Exploration for Multi- Reward Multi-Policy Evaluation
7ps given by (*2)) OV*($1), (81), where 0 1- Ps) and 4.3.1. OPTIMIZATION OVER CONVEX SETS OF REWARDS AND REWARD-FRER POLICY EVALUATION
(=1))) = 1-)(p2+(1-p-))) Using parameters Y = 0.9, r2 2. Ps = 10-2, and p2 = } in the true model M, con- sider an alternative model M' with the same (,,. r2, r2, 7).
9252
For a convex reward set R,, the maximization over the rewards in Theorem 4.7 can be cast as mixed-integer linear program (MILP). In practice, as shown in Appendix B.2.5, the same optimum is obtained more efficiently by solving a finite collection of ordinary convex programs.
Varying P2 in M' shows that p2 0.56 and p2 0.41 are both confusing for e = 0.03, whereas their average is not. This phenomenon is illustrated in Figure 2.
In the next sub-section we explain how to circumvent this issue by considering a convex relaxation of the optimization problem in Eq. 2, denoted as the relaxed characteristic time.
In general, the solution is characterized by the matrix L (s) = (K*(s) las where
(*) - 1(ss
G -²
4.3. Relaxed Characteristic Time
We proceed with finding a convex relaxation of T. (w;; M) that holds for all distributions w E A(S x A). Such re- laxation not only upper bounds T. (wo; M) in terms of Rx (instead of R2),, but also allows to better understand the scaling of TV. The proof can be found in Appendix B.2.3.
[T (5) can be interpreted as the expected discounted num- ber of visits to state j starting from after subtracting the expected number of visits to j starting from s' ~ P(s, (s)). In other words, I (s) is the analogue of the deviation p in terms of discounted number of visits.
Then, for any convex reward set R₂ the quantity supreR, (s, is simply the larger of the optimal values of the two convex programs supreR. - r Consequently, one only needs to solve a finite collection of standard convex problems to compute U. (w; M). We refer the reader to Appendix B.2.5 for details on how to solve in(w) Ug U,(wr))
Theorem 4.7. For all A(S x A) we have T. (w; M) S Ue(w; M), where
7/2 (5)
U,(u; = sup max TE #ES 21 7) (()
(6)
is convex in W. Let (M) = Ue(w M) be the optimal rate, where w' E arg inf weD(ar) Uc Uc(w:; M) is an Upootimaal allocation.
Reward-free scenario. Lastly, in the reward-free sce- nario RS [0, 1]s, Vr E II, the optimization in admits a closed-form solution, which is determined by s', = Σ (0)>0 Dr [ (s), and I (s, s') = Egry (6) r (s))
I"
This theorem exhibits some of the characteristics we men- tioned before: as expected, the complexity is characterized by pairs (s, s') for which the deviation lp, (s, s')l is large, for some worst-case policy-reward pair. What this result sug- gests is that sampling should be roughly proportional to the value deviation (a quantity that is like measure, as explained also in (Russo & Proutiere, 2023a)). How- ever, quantifying the gap (w; M) (w: M) remains challenging, and we leave this analysis to future work.
Corollary 4.8. IfR= = [0, 1] VT E II, then
72 [max (1 (s, 5 L (5)
Ue(w; max 7,5,5' 2c - (w
See also Appendix B.2.4 for a proof and Appendix B.2.5 for an example showing the reward-free sample complexity in the Riverswim environment (Strehl & Littman, 2004) for single policy л. We are now ready to devise algorithm based on the relaxed characteristic rate.
Scaling. To better understand the scaling, for exam- ple, in the generative setting, choosing uniform distribution ((ssT(())
1/S yields a scaling of
O m 72 max, || 13) Since |1 (x) S
1/(1-7), we obtain minimax scaling of O ( 1911
5. MR-NaS for Policy Evaluation
22-(1->))
which is independent of the number of policies or rewards. Note that this scaling can be misleading: because the sample
In this section we show how to adapt the MR-NaS (Multi- Reward Navigate and Stop) algorithm (Russo & Vannella, 2024) for multi-reward multi-policy evaluation based on the results from the previous section. UR-NaS (Algorithm I) is a simple extension of Nas (Al Marjani et al., 2021), and is designed with 2 key components: (I) a sampling rule and (2) a stopping rule. We now discuss each of these.
complexity scales according to ()) small w does
[+)]
not necessarily increase sample complexity if (s) llz is also small. In Appendix B.2.5 we depict the scaling on a simple example for two types of reward sets: reward-fret free (i.e., the entire set of rewards) and the circle |||||| S
7

---

Adaptive Exploration for Multi- Reward Multi-Policy Evaluation
Sampling Rule. The key idea is sample according to the policy induced by w* E arg eMM U2/2(w; M). Indeed, sampling actions according to (7(a|s) = w' (8, /)/ E (s, b) guarantees optimality with respect to U2/22 as the solution w' matches the relaxed rate in Theo- rem 4.4. The factor e/2 arises from the lower bound analysis that requires Ze-separation. By tightening the accuracy to c/2, we ensure the (c, 6-PAA guarantee, which would other- wise be hard prove. This results in additional constant factor 4 in the sample complexity.
Algorithm 1 MR-NaS (Russo & Vannella, 2024)
1: while t < <e//2NN//t; (,N,, 6) do
2: Compute wi = arg inf w.(()))) Uepplu; Mc).
3: Set TT(a|(s)) = (1- =,)x;( + f.
where (a(ss) = (s, En' wt ws,
4: Play 0e ~ =T( (se) and observe 8141 ~ P(1)),
5: Update MDP estimate Mr and set f- ++11.
end while
However, w cannot be computed without knowledge of the MDP M. As in previous works (Garivier & Kaufmann, 2016; Al Marjani et al., 2021), we employ the certainty equivalence principle (CEP): plug in the current estimate at time t of the transition function and compute w/_ The allocation w rapidly eliminates models confusing for Mc, efficiently determining whether the true model M non- confusing-motivatinn our use of the CEP.
antees all actions are sampled infinitely often. The mixing factor can be chosen as e, 1 max (s.)). where (s) is the number of visits of state s up to time t. The resulting exploration policy, tr, is used to sample an action ag, which, together with the communicating assumption and foreing policy, yields an ergodic chain. Upon observing the next state, the transition function is updated using the empirical average.
To simplify the analysis, we make the following assumption: Assumption 5.1. The solution w* is unique and lies within the open set ((M)
Stopping rule. Lastly, the method stops whenever suf- ficient evidence has been gathered to obtain (c, 8c.C)- guarantees. This requires approximately ( log(1/6) samples (by inspecting Theorems 4.4 and 4.7).
Such assumption prevents: (1) the awkward case where a solution may belong to the boundary of S2( (M)) (2) multiple optimal solutions forming a convex set. This latter problem in (Jedra
This rule is defined by two quantities: (1) a threshold ((N,, 5) = (og(L/0)+(--1)E log (e [1
can be addressed using alternative techniques & Proutiere, 2020; Russo et al., 2025; Russo & Proutiere, 2023b), which use regularization or the idea of tracking convex combination of past solutions.
N(ta.a)
S-1
(2) the empirical characteristic time (Ne/:: M.). In both, (s, a) is the number of times action has been se- lected in state s up to time t, and N₂ (Nr a)),,a In con- clusion, we stop as soon as / 2 U2/2(N./15 M.) (N;; 8). Henee, we have the following guarantees (see proof in Ap- pendix C.
In summary, the algorithm proceeds as follows: at each time-step / the agent computes the optimal visitation dis- tribution w = arg inf WER[M. Ue/2(W:; M,) with respect to Me. the estimate of the MDP (which is. practically speaking, the estimate of the transition function). The policy mi (a]s) induced by wi is mixed with a forcing policy (-(s( (e.g., a uniform distribution over actions or a distribution that en- courages to select under-samp sample actions; see also (Russo & Vannella, 2024) Appendix C.3 for more details) that guar-
Theorem 5.2. MR-NaS guarantees PM Vv 11, E R2 : VVV VyJ oo) = 1 and lim sups
llx
S e] 2 1 8; PM <
Em [r] S (M).
log(1/8}
SF-NR
GVFExplorer
MR-NaS
Noisy Policy (unif.) DoubleChain
Noisy Policy (visit.) NArns
Riverswim
ForkedRiverswin
V
100
10-1
10-2
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
0.0
0.5 Time-steps
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x10
x x10"
x10
x
100
Figure 3. Multi-policy evaluation over finite set of rewards on different environments. Shaded curves represent 95% confidence intervals.
8

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
SF-NR
MR-NaS
Noisy Policy (unif.)
Noisy Policy (visit.) NArms
Riverswim
ForkedRiverswin
DoubleChain
10P
10-1
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x 10
Time-steps
x 10
Time-steps
x10
10
Figure 4. Reward-FFre multi-policy evaluation. Here we depict the average enror over the canonical basis Ranoo for each policy. Shaded curves represent 95% confidence intervals.
6. Numerical Results
Policy - Un form, a mixture of the target policies Tmix [m)x(a]s) = [[=EIl mixed with uniform policy Tu with a constant mixing factor & 0.3. The resulting behavior policy is л. (1 Ex) EyTu. Lastly, (4) Noisy Policy - Visitations computes the same behavior policy as in (3) with a non-constant mixing factor 4 = (s,) which is based on the number of visits.
In this section, we present the numerical results of MR-NaS, and other algorithms, various environments with different reward sets (results use 30 seeds).
Settings. We study MR-NaS in 4 different environ- ments: Riverswim (Strehl & Littman, 2004), Forked Riverswim (Russo & Proutiere, 2023a), DoubleChain (Kaufmann et al., 2021) and NArms (Strehl & Littman, 2004) (an adaptation of SixArms). For each environment we evaluated 3 scenarios: (1) multi-policy evaluation with fi- nite reward sets for each policy; (2) reward-free multi-policy evaluation; (3) reward-free single policy evaluation (results for this one can be found in Appendix C.4).
Discussion. The results for the first two settings are shown in Figures and 4 (policy evaluation was performed us- ing the MDP estimate M, at each time-step). MR-NaS achieves good accuracy on all environments. On the other hand, SF-NR and GVF Explores have mixed per- formance. While SF-NR is not designed to optimize a behavior policy, we note that the exploration strategy used by GVFExplores is similar to solving a problem akin to Equation (2), but neglects the forward equations when opti- mizing the behavior policy (see also Appendix C.3 for de- tails). As result, GVFExplores tends perform worse in environments where certain rewards are hard to obtain under a uniform policy. Lastly, we refer the reader to Ap- pendix C.4 for more details, and to the README. md file in the supplementary material to reproduce the results.
While framework supports various settings, we focus on what we consider to be the most important and novel scenarios. For multi-police evaluation, we sampled three random policies for each seed. These policies were sampled uniformly from the set of policies optimal for one-hot re- wards, where each reward equals at a single state-action pair and elsewhere. In the case of finite reward sets, each policy was evaluated using the corresponding rewards from these sets. In the reward-free scenario, evaluations were conducted across the canonical basis R for each π.
7. Conclusions
Algorithms. While our work is one of the first to study the reward-free evaluation problem. there are some prior works that study the multi-task policy evaluation. We con- sider (1) SF NNR (McLeod et al., 2021), an algorithm for task policy evaluation based on the Successor Rep- resentation, and we adapted it also consider the reward- free setting (see Appendix C for more details). Next, we consider (2) GVFExpl orer (Jain et al., 2024), variance- based exploration strategy for learning general value func- tions (Sutton et al., 201 based on minimizing the MSE. However, such exploration strategy is not applicable to the reward-free setting. We also evaluated (3) Noi sy
In this work, we studied the problem of devising an explo- ration strategy for online multi-reward multi-policy eval- uation, accommodating reward sets that are either finite or convex, potentially encompassing all possible rewards. Leveraging tools from Best Policy Identification, we derived instance-dependent sample complexity lower bound for the (e, 6)-PAC setting. Based on this bound, we extended MR-NaS (Russo & Vannella, 2024) to the evlicy-evaluation setting, and showed its asymptotic efficiency. Lastly, we compared MR-NaS against other adaptive exploration meth- ods across various domains, demonstrating its efficiency.

---

Adaptive Exploration for Multi-Rewart Multi-Policy Evaluation
Acknowledgments
Dann, C., Mansour, Y., and Mohri, M. Reinforcement
learning can be more efficient with multiple rewards. In International Conference on Machine Learning, 2023.
The authors are pleased to acknowiedge that the computa- tional work reported on in this paper was performed on the Shared Computing Cluster which is administered by Boston University's 's Research Computing Services.
Dayan, P. Improving generalization for temporal difference learning: The successor representation. Neural computa- tion, 5(4): 624, 1993.
The authors would also like to thank Yilei Chen for the insightful discussions and constructive feedback provided during the drafting of this manuseript.
De Alwis, C., Kumar, P., Pham, Q.-V., Dev, K., Kalla, A., Liyanage, M., and Hwang. W.-J. Towards 6g: Key tech- nological directions. ICT Express, 9(4):525-553 2023.
Impact Statement
Diamond, S. and Boyd, S. CVXPY: Python-embeddee modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
This paper presents work whose goal is to advance the field of Machine Learning and Reinforcement Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Efron, B. Bootstrap methods: another look at the jack-
knife. In Breakthroughs in statistics: Methodology and distribution, pp. 569-593, Springer, 1992.
References
Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained policy optimization. In International Conference on Ma- chine Learning, pp. 22-31. PMLR, 2017.
Garivier, A. and Kaufmann, E. Optimal best arm identifi- cation with fixed confidence. In Conference on Learning Theory, pp. 998 1027. PMLR, 2016.
AI Marjani, A. and Proutiere, A. Adaptive sampling for best policy identification in markov decision processes. In International Conference Machine Learning, pp. 7459-7468. PMLR, 2021.
Hanna, J. P., Thomas, P. S., Stone, P., and Niekum, S. Data- efficient policy evaluation through behavior policy search. International Conference on Machine Learning, pp. 1403. PMLR, 2017.
Al Marjani, A., Garivier, A., and Proutiere, A. Navigating to the best policy in markov decision processes. In Advances in Neural Information Processing Systems, volume 34, pp. 25852-25555 225844, 2021.
Jain, A., Hanna, J. P., and Precup, D. Adaptive exploration for data-efficient general value function evaluations. In Advances in Neural Information Processing Systems, vol- ume 37, pp. 65912-65944 2024.
Antos, A., Grover, V., and Szepesvári, C. Active learning in multi-armed bandits. In Algorithmic Learning Theory: 19th International Conference, ALT 2008, Budapest, Hun- gary, October 13-16, 2008, Proceedings 19, pp. 287-302. Springer, 2008
Jedra, Y. and Proutiere, A. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, volume 33, pp. 10007-10017, 2020.
Jonsson, A., Kaufmann, E., Ménard, P., Dar- wiche Domingues, O., Leurent, E., and Valko, M. Planning in markov decision processes with gap- dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253-1263: 1263, 2020.
Auer, P. Using confidence bounds for exploitation- exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397-422. 2002.
Kaufmann, E., Cappé, O., and Garivier, A. On the com- plexity of best arm identification in multi-armet bandit models. Journal of Machine Learning Research, 17:1-42, 2016. Kaufmann, E., Ménard, P., Darwiche Domingues, O., Jons- son, A., Leurent, E., and Valko, M. Adaptive reward- exploration. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, 2021.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Carpentier, A. and Munos, R. Adaptive stratified sampling for monte-carlo integration of differentiable functions. In Advances in Neural Information Processing Systems, volume 25, 2012.
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 1985.
Chen, Y., Pacchiano, A., and Paschalidis, C. Multiple- policy evaluation via density estimation, arXiv preprint arXiv:2404.00/9 00 2024.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
10

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Levin, D. A. and Peres, Y. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
In Advances in Neural Information Processing Systems, volume 36, 2024.
Linke, C., Ady, N. M., White, M., Degris, T., and White, A. Adapting behavior via intrinsic reward: A survey and empirical study. Journal of artificial intelligence research, 69:1287-1332, 2020.
Ruggeri, F. Russo, A., Inam, R., and Johansson, K. H. Explainable reinforcement learning via temporal policy decomposition. arXiv preprint arXiv:2501.0300 2025.
Russo, A. and Proutiere, A. Model-free active exploration in reinforcement learning, In Advances in Neural Informa- tion Processing Systems, volume 36, pp- 54740-54753, 2023a.
McLeod, M., Lo, C., Schlegel, M., Jacobsen, A., Ku- maraswamy, R., White, M., and White, A. Continual auxiliary task learning. In Advances in Neural Informa- tion Processing Systems, volume 34, pp. 12549-12562, 2021.
Russo, A. and Proutiere, A.
On the sample complexity of representation learning in multi-task bandits with global and local structure. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pp. 2023b.
Mukherjee, S., Hanna, P., and Nowak, R. D. Revar: Strengthening policy evaluation via reduced variance sam- pling. In Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, volume 180 of Pro- ceedings of Machine Learning Research, pp. 1413-1422. PMLR, 2022.
Russo, A. and Vannella, F. Multi-reward best policy identi- fication. In Advances in Neural Information Processing Systems, volume 37, pp. 105583-105662, 2024.
Nahum, C. V., Lopes, V. H., Dreifuerst, R. M., Batista, P., Correa, I., Cardoso, K. V., Klautau, A., and Heath, R. W. Intent-aware radio resource scheduling in ran slicing scenario using reinforcement learning. IEEE Transac- tions on Wireless Communications, 2023.
Russo, A., Song, Y., and Pacchiano, A. Pure exploration with feedback graphs. In Proceedings of The 28th Inter- national Conference Artificial Intelligence and Statis- tics, volume 258 of Proceedings of Machine Learning Research, pp. 1810-181 1810.1 PMLR, 2025.
Osband, I., Russo, D., and Van Roy, B. (more) efficient rein- forcement learning via posterior sampling. In Advances in Neural Information Processing Systems, volume 26, 2013.
Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z., al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
Papini, M., Manganini, G., Metelli, A. M., and Restelli, M. Policy gradient with active importance sampling. In Reinforcement Learning Conference, 2024.
Seneta, E. Non-negative matrices and Markov chains. Springer Science & Business Media, 2006.
Strehl, A. L. and Littman, M. L. An empirical evaluation of interval estimation for markov decision processes. In 16th IEEE International Conference on Tools with Artificial Intelligence, pp. 128-135. IEEF, 2004.
Poddar, S., Wan, Y., Ivison, H., Gupta, A., and Jaques, N. Personalizing reinforcement learning from human feed- back with variational preference learning. In Advances in Neural Information Processing Systems, volume 37, 2024.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Precup, D. Eligibility traces for off off-policy policy evalua- tion. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Sutton, R. S., Modayil, J., Delp, M., Degris, T., Pilarski, P. M., White, A., and Precup, D. Horde: A scalable real-time architecture for learning knowledge from unsu- pervised sensorimotor interaction. In The 10th Interna- tional Conference on Autonomous Agents and Multiagent Systems- Volume 2, pp. 761-768, 2011.
Puiutta, E. and Veith, F. M. Explainable reinforcement learning: A survey. In International cross- cross-domain confer- ence for machine learning and knowledge extraction, pp- 77-95. Springer, 2020.
Taupin, J., Jedra, Y., and Proutiere, A. Best policy identifi- cation in discounted linear mdps. In Sixteenth European Workshop on Reinforcement Learning, 2023.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Thomas, P. and Brunskill, E. Data-efficient off off-policy pol- icy evaluation for reinforcement learning. In Interna- tional Conference on Machine Learning, pp. PMLR, 2016
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D.,
Ermon, S., and Finn, C. Direct preference optimiza- tion: Your language model is secretly a reward model.

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Wagenmaker, A. J., Simchowitz, M., and Jamieson, K. Be- yond no regret: Instance-dependent pac reinforcement learning. In Conference on Learning Theory, pp. 358- 418. PMLR, 2022.
Watkins, C. Learning from delayed rewards. PhD thesis, Cambridge University, Cambridge, England, 1989.
Weissmann, S., Freihaut, T., Vernade, C., Ramponi, G., and Döring, L. Clustered kl-barycenter design for policy evaluation. arXiv preprini arXiv:2503.0277 02735, 2025.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. Fine-tuning language models from human preferences. arXiv preprint arXiv; 190.00999,, 2019.
12

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
(Appendix)
Adaptive Exploration for Multi-Reward Policy Evaluation
Table of Contents
1
Introduction
2 Related Work
3 Problem Setting
3
3.1 Markov Decision Processes (MDPs)
3.2 Online Multi-Reward Multi-Policy Evaluation
4
Adaptive Exploration through Minimal Sample Complexity
4
4.1
Set of Alternative Models
4
4.2
Sample Complexity Lower Bound
4.2.1
Convexity of the Lower Bound
4.3
Relaxed Characteristic Time
4.3.1
Optimization over Convex Sets of Rewards and Reward-Fres Freard-FFeeeaa Policy Evaluation
5
MR-NaS for Policy Evaluation
Numerical Results
7
Conclusions
9
Acknowledgments
10
Impact Statement
10
Appendix
14
A Additional Notation
15
Theoretical Results
16
B.1
Alternative Models and Value Deviation
16
B.1.1
Proof of Proposition 4.1 and an Additional Minimax Necessary Condition
16
B.1.2
Additional Results on the Value Deviation
19
B.1.3
Proof of Proposition 4.2 and Related Results
21
B.2
Sample Complexity Results
24
B.2.1
Proof of Theorem 4.4
24
13

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
B.2.2
Optimality of Behavior Policies
26
B.2.3
Proof of Theorem 4.7 (Relaxed Characteristic Rate)
29
B.2.4
Proof of Corollary 4.8
31
B.2.5
Computing the Optimal Relaxed Characteristic Rate U
31
C -aS and Numerical Results
33
C.1 MR-NaS Proof of Theorem 5.2
33
C.2 Environment Details
33
C,3 Algorithm Details
35
C.4 Additional Results and Experimental Details
37
14

---

Adaptive Exploration for Multi- Multi-Policy Evaluation
A. Additional Notation
In this appendix we introduce some additional notation that is used in the proofs.
Table I. Table of Notation
Symbol
Definition
Description
(M)
(M) = {M, M < My [V Virllo > 2
Set of alternative models in (T, r).
Rx
Rx S [0,
Reward space considered for policy æ.
R
R₁ = fr E Rs Alt (M) + 0}
The subset of rewards of R₂ for which the set of alternative models is not empty.
all-ones vector.
0
6,
i-th element of the canonical basis.
i-th position
diag(A)
diag( A)
A11
Ann
Diagonal square matrix Rax*.
a)
a) P(s1|8,0)
a)
Vector of transition probabilities in (s,
Pa
P (P(8')s 8, (())))
Vector of transition probabilities under æ in 8.
p
8.8' = P(s'1 88, o (8)), Pa E TRS
Matrix transition probabilities under m.
G
"APP")",G""" G. E RSSS (7 8') = (s" - (V (s) = V - (PT) V, (T)) E R
GT (1 - -11---->-1
Discounted fundamental matrix.
())
One-step value deviation s').
PT (s)
Vector of one-step value deviations in s.
PT
(8)) I(V
(P' of RSS
Matrix one-step value deviations.
(*)))
(*))) (Is 1P(s, n (8)) (*()) E RSSS
Deviation weighting matrix in 8.
sp(V)
max, V(s) min, (s)
Span of a value function.
(*)s)
(s) KJ (*)s))"
Matrix used to express pf (s, = (s)r.
KL(P(- 8, (' a))
KL between next-state kernels (s)
ll
blllll1
Total variation for signed vectors 4.
(s)
d= d= P E, (8)
Stationary state distribution under
d" (s) a)
d= (als)
Stationary state-action occupancy.
a)
E A(S A)
Stationary state- action allocation (design variable).
())
En ((enna))=((o)))
Visit count to (s, a) up to time l.
15

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
B. Theoretical Results
B.1. Alternative Models and Value Deviation
In this section we prove some of the results in Section 4, and provide additional properties on the set of alternative models.
We begin by proving Proposition 4.1 and additional necessary (minimax) condition for model M' be an alternative model.
B.I.1. PROOF OF PROPOSITION 4.1 AND AN ADDITIONAL MINIMAX NECESSARY CONDITION
Proof of Proposition 4.1. We first prove the sufficient condition, and then prove the necessary condition.
Sufticient condition. Let 90, E S, and fix a reward E R. In the following we omit the subscript r for simplicity, Define a transition function P so that
P(s
so: = so a # T(5));
(()'
P' a) =
8+ (1 (1-))((sss1 (s) x(s))
(s, a, s') = (su. π (80),
(1 (1- (1=')P(s'l1s) π (8o))
(8, = (so. ग (80)) A s # 81:
with (0, 1). Therefore P(s, a) < P' (s, a) for all (s, a). Let Vp be the value of æ P, and similarly define vp.. For $ + so the difference in value AVE = VB Vp satisfies
AV PPT AV",
where P*((s) = 1s
P( x+))] is the vector of transitions over the next state starting from (s, x (s)).
To analyse the case so we indicate by p (s) the vector of transitions in s for P under æ. We obtain the following sequence of equalities
AV" AV*(s)) = (50) - P (1)
-s7 TV, -7(1-))
6) Σ ((00 -8V7 - 7(1 8)P(s1150. (s)))
8'
>>P*(so) T V3 - -0(1 - 6) Σ P(s su, x -001)())))
(s0) T(V (() (1 8)13) (31),
y(P" ( - -11 8)13) SVp #P V (v))
>(P" (1-8)AV* + A "d (s,) + 8(P" TV: -V)ss(s)))
(P''(ss) (so) TAV= + 70(P" (so) V (s1)))
bbg
Hence, we can rewrite the expression of AV* in matrix form as
AV = b =b+
where b $ equal to 0 for s + so and bep 78
Vf((s)) -YdpF(50.
Hence, we find
AV 11(I -
-bbool (r'''=)ee
16

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Letting M = (7 observe that M0 = .M represents the (unnormalized) stationary discounted probability of
reaching so starting from 8a
M0
Σ
cap (P' c'0 E = sul sulso: TI, P') 2 Σ "''p'"ssulsu x(80))* - (00p'r T (so))
Therefore
y0 (su, s1)l
| 2 1- 11) P(50 so. (50))
Let P
Pos ((S))) Then, we seek value of (0, so that
p61p7 (so: s1)l
> 2e.
1 1 7(1 -5)p%
Some algebra gives that if 17 (1)1 - -2ep > 0 and (80, 81)1 >> 2e any value of in the range
2c(1 7P%.
8 E 1(p (So. s1) 2epT,)
leads to ||V* Ice > 2c, and thus the model is confusing. Since the above conditions can also be written as |p, (su. s1)l 2e max (px 1/7) 26/7, , and one optimize in 81, find that sufficient condition is that
2c 7
Esg II))
Necessary condition. As before, let V be the value of π in M with a reward r (we omit the subscript for simplicity), and similarly define Vr. If M' is confusing for some reward E R, then we have that there exists a state so such that 2c < (so),, with (V) = Vī (s) - (s). Note that the following inequalities hold for any s AV" (s) - P(s, n (s))
VM (((s T V
< AP(s, T (8)) VM + (s)) AV
> AP(s T VV +>VVV
Since the inequality holds for all 8, it implies that 2e < (AV* 2 ||VV 1l0 S max, 12 AP [V We also denote by Smax the state maximizing this last quantity.
Letting e be the vector of ones, and noting that: (1) (VM is a constant and (2) V ExsnP(s (V = (s). then
2e < AV (so)
< 1-7
AP (8 pr (
2- ||AP(s (maax: ( )lzv max (8')ll
1 1-7
Since ((s)(s < for any s, we find that a necessary condition for M' being a confusing model (for r)) is that
38 (8) > <(1 (117))
In the following proof we provide an alternative minimax necessary condition for the existence of an alternative model for (n, r). To derive the result, we use the following lemma.
Lemma B.1 (Lemma 3 (Achiam et al., 2017)). The divergence between discounted future state visitation distribu- tions, ||dd' d= [11, is bounded by an average divergence of the policies n¹ and π::
27 E, a- (1(=(s) [s))llz)
||a= d' 1/1 S
17

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Then, have the following result.
Lemma B.2 (A necessary minimax condition for M' to be confusing model). Consider a reward v and target policy n. If M' is confusing model, i.e.
[ V >> 2c, then there 3s such that
2(1 ---- [L plr a)]
E B (-1s)
72 e.
Proof. The proof relies on constructing alternative MDP and a policy म such that can transform the problem of evaluating two different transition functions into problem of comparing two different policies. For simplicity, we also assume deterministic policy æ, and explain at the end how extend the argument a general stochastic policy.
Imaginary MDP M. We begin by constructing an imaginary deterministic MDP M where the action space is À S. The transition function of this MDP is P(s'|s. [s, u) (u==')> i.e., taking the action u leads the agent to state s' with probability 1. The reward function instead is F(s) = r(s, (8)).
Define now the policy [(uls) P(u|s, (s)). With Mr convert the value of the policy under the original MDP and confusing models to the value of different policies under Mf. Specifically, the value of the policy (deterministic) under the MDP M, with transitions / is
(+) = V (s).
This follows from the fact that
V (8) Σ (1/s, + (M) E (())), + +7V,, (s))-
Then, by an appropriate application of the Bellman operator one can see that V (s) = Vir, (s)
Bounding using the difference lemma. Consider now confusing model Mr (Mt),,(MM with transition P', and define a policy म' (uls) (u(uss, (s)). Hence, have
Vs (s) - Viss (s)l = -V.. (s) V.A (s)
(7)
Based on Lemma B.1 and Equation (7), we have Vs
VV (s) Vir (s)l = V (8) V (M(())) (8)1:
(8)
Mr
< 1
| Mr (s) - diz (s)* 112,
(9)
1 q
2y
5 (1 7)2
E. Ex'nd (o) [Ts) #'(s)l
(10)
where d,, (s) denotes the visitation distribution induced by मे in Mr starting from s.
If Vs, we have [|s(s) #'(s) s (1-7)²- then |V (s) VM (s)) < 2e, Vs, i.c. Mt is not confusing model. Hence, there exists such that
7) e
- -
S (Lm
Extension to stochastic policy. The extension stochastic policy involves few more steps, and it is omitted for simplicity. It follows from defining an imaginary MDP M with P(s'|s ss. u) (ums')), F(s, u) E. r(s, a (a)(((sss) and (uls)) -. P(u]s, (al(s). The argument concludes by noting that if M is confusing then
1 (1 (1-7)* (1)))) +' 1 < KL((())) # (s)) < Eawn(-ls) [KLp))
72
2
by the datc-pnoess inequality.
18

---

Adaptive Exploration for Melti-Reward Multi-Policy Evaluation
1.1.2. ADDITIONAL RESULTS ON THE VALUE DEVIATION p
Value deviation. To analyze these confusing sets, and their implications for sample complexity, we define the following instance-dependent quantity, that we refer to as the one-step value deviation:
(3 = V, P(a (V (5)] Vs, 8 ES, (s, (s.
This quantity measures how much the value at s' differs from the expected value of the next state when starting at s.
We also define these quantities in vector form (5) = [e] $1) (s, ss) so that II) =
max, (s, s'] is the maximum one-step deviation at s (similarly, one defines (7 a)). The deviation o, is closely
related the span of the value function
sp(V,) max V," min V²*
(11)
but, is in general smaller. In the following lemma also show that it is unlikely that max,, P7 (s, s') is achieved for s 8, but rather for s' & 8. Depending on the characteristics of the MDP, it is more plausible that P3 (8, 8) Ro O.
Lemma B.3. For any reward vector r E [0, 1]s, states 8, s E S, we have: (1) (s. 8) s 1; (I) (1)( sp(V;") and (III)
(s, (s',s)) S | s'1 1 17, (V(())),
where (8, = ((8,7())) - r((',=(s')) and r 5, = P p(s', (sl))l....
Proof of Lemma B.3. First part. For the first part of the lemma, note that
(s(s (s) P(s, (s)) V. r(s, + - x(s)
1 Since ((s,T(s) n VV 2 0, and (0, then (7 - obtain of (s, 8) < 1.
Vi 0. Using that the reward is bounded in [o, 1], we
Then, using that (s) 1/(1 7) = -1 - 1 (s) also have p7 (f s) 2 r(s, (()) -1. Thus (e7 (8,8)) 1.
Second part. The second part is rather straightforward, and follows from the definition of span sp (V,7) max, V, min, V (s). Indeed we have
(x, = V. = ((s, < max (iT(s) - min V (s) = sp(V,")
and
(F 2 min (7* max ((s, VV)(
Third part. For the third and last part first note the rewriting
(8,8')) - () = (,())
Pss, V,"
-(())))))-((67))))))))))))-())(- P(s, (ss) vr
Then, define 2(s,8))== { P(2)s, ((2)s, and
PT(s,'') = Σ (())s, (s))))
Σ P(=)st,=s')) P(=ls,
xE2(),0))
2(,))(a,)))
19

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Also observe PI s') (8, s) and [P(s (())) - P(s', ((6))=())))))) Pf 6) 8), from which follows that PT( = 211 ( (s)))l Then, we have that
[P(s', - P(s, V.+ = Σ [P(zls P(s)s (*)
[P(z|s (P(z|s/.T(s')) (Ts))) P(2)s
=62(),8)
(P(2)s(,<('') P(2ls, (=))
=68)2(s,0))
S (8, max V
(T) (8)+
E
PP (8')) P(z|s, (s)) (2).
=ES(Z(s,"))
20
S ([( max (7) (8)
E
((2)s',<(8)) P(e|s, (s)) min (s),
=(S))(s.s))
s SPT(s max V (s) (s min (s),
s PT(s,'')sp((?)
$ 2 (P(s, - p(,.,((())))) (ss))))))))
By taking the absolute value one obtains the result.
Another useful metric the dispersion factor Xr, which defined as
min, V (s) X
max, (s)
from which we see its relationship with the span, i.e., sp(V max, (=
The parameter XB measures the spread of the value function across different states. Specifically, a smaller XØ indicates a greater dispersion of values among states.
Lemma B.4. The dispersion factor X satisfies:
1. V, 2 (,V,((s) (s) for any pair s, E S.
2. max, V (8) V (x') S (1 X²) max, V (s) for any state s'.
Proof. First, clearly XI E [0, 1]. Then, the first property is derived from the following inequalities that hold for any pair 8'):
XVV, < X max V (s) = min V (s) < (s').
The second statement stems from the simple fact that - (s² < - min, Vi7 for any Hence:
max V
(s) (s) V,7 (s') < max V (s) min V max V (s) X max (s).
Using this metric, we are able to provide the following result, providing a bound on p. (8, s') (note that one could rewrite the following result in terms of the span).
Lemma B.S. For any reward vector r E [0, 1|5, we have; (s, E Furthermore, for X; = "y we have that (p (s, s')l Z 2 for all 8,
[-
1-17z - max (1. ) for all s, S.
20

---

Adaptive Exploration for Relti-Reward Multi-Policy Evaluation
Proof. First part. For the first part of the lemma, note that
(r, s) = v (s) - P(s, (()) V, - ((8, +
Since P(s, 1 (8)) TV, V 2 0, and y (0,1). then (7 - 1)P((s) V. = 0. Using that the reward is bounded in [0, 1]. we
obtain (s.ss s) 1 1.
Then, using that < (s) 1/(1 -7) = -1 - (s) also have pł (8, 8) 2 r(s, (s)) 1 2 -1. Thus (s. S 1.
Second part. For the second part of the lemma let P = P(s, n (s)) be the vector of transition probabilities in under action (s)). We first prove that (s) 2 X,V,T = (P.) V, 2 (P3) VF The proof is simple, and follows from the following inequalities that hold for any pair (8,8) E S²:
(P.) V. 2 min V7 2 X max (s') 2 (PP))
We use this fact to prove the result. From the proof of Proposition 4.2 we know that
p = (V - ((P"V")1 = 1(r + ) - (P"V,)11"
where is the vector of rewards. Let W- Px V and note the two facts (1) W. (P,)) TV, and (2)0 W. s 11((1- 7)) Then, one can see that (p²)s,+ is
(p:) = == = r(s')
+ +W - W,,
We prove the statement in two steps:
1. We first prove p. (8, S max
1, - Using that for any pair (s, 8') we have X.W, S W, it follows that
r(s') + +WW
W. r(s)) W. = WoW
= =r(s'+ W; + X.W W
S <r(6) + (7 - X, '
0, 2- 2- Xo 1-7
$ 1 + max
1, 1- 1,
S max
2. We now prove lower bound on ps (s, The idea is seek value of 1) 0 such that W W. 2 (7 1)W,n,
which implies yW, - W. 2 17 (using that - W, 2 -1/(1 -)). Then, we find Wy 2 (ry- W.. Since Wy 2 W.W., s. we can set
(m n +1 = x n n x/7 - 7
9-1
(notably, if X y then 1 = S 2). Lastly, we obtain (s, r(8") + +WW, W, -1 concludes the proof.
1-1 which 1-y
Hence, if the value is similar across states, we can expect a smaller sample complexity.
1.3. PROOF OF PROPOSITION 4.2 AND RELATED RESULTS
In the following, we prove Proposition 4.2, which characterizes the set of rewards for which max, [1p7 0. In the proof we define the following deviation matrix
of = (s)(
([s))
(12)
that is used to prove the proposition.
21

---

Adaptive Exploration for Multi-Rewand Multi-Policy Evaluation
Proof of Proposition 4.2. First, note that
(8, VM, (8') R (e) (V)) = (eg' - -P)'
where e is the s-th element of the canonical basis, P. P(s, 1 (s)). Hence, we can write Pf (8) as
pf (.) V P. V
where 1 is the vector of ones. Therefore
P 1(V (P*V
where Pa is a S x S matrix satisfying (P*) (P*),,8' P( (and P
We consider the condition
p = O being identically 0, that is
1(V)) = (P=V
V = (PVV V.
Since (P.V = TV. letting Mr = 1(P)), then p.-- = + V MT for every E S, that is, V." right eigenvector of MM with eigenvalue for all s S. Since M. has rank for every s, then V." is the only right eigenvector for eigenvalue 1 for all states.
Now, one can easily see that M 1 (P:) 1, thus the right eigenvector of M associated to the eigenvalue 1 the vector 1 itself, for all states.
To translate this condition onto condition the rewards, we use the fact that V G with GT (P=) (which invertible). Therefore, we require r to satisfy
3e : G d1-
Conclusion.
Using that p 1, we conclude that
- + r 1.
The set of all vectors for which p 0 is precisely the set fal R}. Thus, must be scalar multiple of 1.
We conclude this subsection by characterizing what cases, pf (s, is identically zero across states. First, note the following result.
Lemma B.6. Let diag(o?) [ot (81, 81)
p (8s) We have that
diag(p,) = -I- pI - -pt
(13)
Proof. First, note that
(s, = (s', - (s (VM, (8)), =(e, TV...
VM..
= =(E,' - P.) GTr,
where e, is the s-th element of the canonical basis, P. P(s, (s)) and in the last step we used the fact that V G
with T (I 11--1 PP
Since for any a we can write of (8, 8) = (es - P.) rr follows that p7 = [[T p. -= and thus diag(p?) (I-PT)G"r
We now consider a result that permits us to understand when max, P. (s, s) = for any state s, which is the diagonal of p... In the result, we consider a partition of the set recurrent states p into m disjoint closed irreducible sets C1..... Om- Then, define 7; = [t 8 C2} the hitting time of C, that is, the earliest time C2 is reached, and define
22

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
(s) (n; < co(s) to be the probability of reaching C2 in finite time starting from state under x. We have then the following result.
Proposition B.7. Let m be the number of disjoint closed irreducible sets Cl..... Cmr in Pr, Define the vector hę E IR$ as (hT)s P" < oo(s). which is the probability of reaching C₁ finite time starting from under Then, for any non-zero reward vector RRS, we have that:
max p (s, =0 + r span [hi...., hm }
In other words, the reward r lies in the span of the m. vectors (h.)
In other words, the one-step value deviation at state is zero provided that the reward function constant on each irreducible closed of pn
Proof. From Lemma B.6, we know that
= d
Then, let æ = (I -Pp-~PP> and consider the solutions to (I - P')æ = O. In other words, we are interested in the
real-valued right eigenvectors of pa associated to the eigenvalue 1, that is, pa x = x. Then, for any such right eigenvector we obtain
(1-7)x=n
Hence, since is right eigenvector (P*x 2), r is also right-eigenveccto of pa associated to its eigenvalue 1 (note that we get p"r=r)
= r).
Therefore, finding the reward vectors satisfying ||dia(pp)) lloo = 0 amounts to finding the real-valued right eigenvectors of fx associated to its eigenvalue 1.
In general, for an irreducible stochastic transition matrix pa it is well-known (Seneta, 2006) that the only real-valued eigenvector associated to the eigenvalue is the all-ones vector, and thus r A1 is solution for any X E IR.
For generic p", the above argument can be extended by partitioning the set of recurrent states into m disjoint closed irreducible sets Ci,-.., Cm- Therefore, as shown (Puterman, 2014), the state space can be rewritten as S = C₁ U C2 U ... UT, T, where T is the set of transient states. After relabeling the states, we can express the transition matrix pr as
P
0
P2
0
0
pD
P
Q1
Q2
Qm
Qm-1_
where P; corresponds to the transition function in C., Qi to transitions from states in T' to states in C,, and Qm+ to transition between states in T (Puterman, 2014). Moreover, we also know from (Puterman, 2014, Theorem A.5) that the cigenvalue has multiplicity m.
Note that, since each P; is an irreducible stochastic matrix, there only one right eigenvector associated to 1, and it is the vectors of ones, of size [C&]. Then, if Q2 O, then one can conclude that (h;). = (seC,) is right eigenvector of pr, However, that is not generally the case. Therefore we now derive general way to find the right eigenvectors.
Define T, = inf s, E C,) be the hitting time of C, that is, the earliest time C, is reached, and define h7(s) = PT < co|s), that is, the probability of reaching C₁ in finite time starting from state s under л.
23

---

Adaptive Exploration for Multi- Multi-Policy Evaluation
Then, observe that hy (s) satisfies recursive relationship
(. = (T, < <0088 = =8,
Σ P' < <00,82 = =s'ss- =8), 8),
Σ (s (1sssssp(( 10'(( (T, < cools2 s'),
Σ (5'))))7()))
where we used the strong Markov property. Therefore h pT meaning that h is a right eigenvector of p associated to the eigenvalue 1. Now, observe that h (s) for all s E C, and hs()s = for all E Cj. * i. Because of that, these vectors are distinct eigenvectors of the eigenvalue 1, Since the eigenvalue has algebraic (and geometric) multiplicity m by Theorem A.5 in (Puterman, 2014), hence the independent vectors (h. (hg)m form basis of the eigenspace and therefore span it.
In conclusion, we have that {hi..... ....,... h are linearly independent eigenvectors of pa associated to the eigenvalue 1. Thus, any (hT ...., h yields [[diag(p))]ls O.
B.2. Sample Complexity Results
Now we provide proofs for the sample complexity lower bound, and related results.
B.2.1. PROOF OF THEOREM 4.4
Proof Theorem 4.4. The overall proof strategy is to derive set of constraints the number of visits N₂(s,a) state-action pair (s, a) that any (c, 5)-PAC strategy must guarantee. Dividing Ea (s, by [M([T] yields a quantity w(8, a) that is distribution over the state-action space, and as 5 - 0, w converges to stationary distribution. In the last part of the proof we discuss the ergodicity of the chain induced by this stationary distribution.
Em=1 ((s.a)
Part 1: set of constraints through change of measure. The initial part of the proof follows the same technique as in (Al Marjani et al., 2021; Russo & Proutiere, 2023a), and leverages change of measure arguments (Lai & Robbins, 1985; Garivier & Kaufmann, 2016).
Consider rewiey-reward pair π E I1 E Rg. For a confusing model M E Alt,, (M) consider the log-likelihone ratio up to time t of a sequence of observations (21, ..,. with 2; = (8s, 0z), under the original MDP M, and an alternative model Ma,r E Alt
L Σ log P(en+1|Zn)
P (Sn+
Then, as in (AI Marjani & Proutiere, 2021), one can show that for all E N the following equality holds
Em [L, Σ 20
PM (N. 2 u uKKLp|p, (s)
8,a
EM(NN KLPpp, (s.a).
8,0
Now we proceed to lower bound the expected log- likelihoooo ratio the stopping time We indicate by PMr, the measure induced by My,, Applying the information processing inequality in (Kaufmann et al., 2016), we lower bound the expected log-likelin log-likelihood at the stopping time as
EM 2 kl KI) (8))
for some event & that is F, meaauuuuael Then, define the event È = (3x E II, E RS IVV, - V. > c). By definition of (c, 8PC algorithm we have (E) < 8. If we can show that PM; 1M,,, kI As (E), Pa (E)) 2 kl - 6) by the monotonicity properties of the Kl.-divergence.
(8) 211 11-66 8, then we can lower bound
24

---

Adaptive Exploration for Melti-Reward Multi-Policy Evaluation
To show P Mar (8)
6, few steps needed:
PMg (8)
F,g (IVV, Villoo c)2
max
=EIT,
1V3
max PMG, (1IV -Vis 100 -1V5s; -Vello E),
EE
M (I VM 1lo -IVisT 12llo0 > >(),
Vo <)); EE,
P Pag (1I MM;
min
PMg, (1IV - -Vrlloo <c),
P Mc. (VT (VIT E 11, R₂ IIV - Vr <)
1 - PM, (3x E El, I| Voe 2 e) 2 1
where (a) and (d) follow from the Fréchet inequalities; (b) is an application of the triangle inequality; (c) follows from the fact that M Rrr confusing for (I, r) and the last inequality from the definition of (c, PPCCC algorithm. Henceforth, for a (e, 6)CAC algorithm one can conclude that Ex Er..) 2 kl -) 6).
As the inequality above holds for all π E II, E R7, we obtain the following set of constraints:
inf TE, (M)
[e. 2 kl(6, - 5).
Part 2: optimizing the stationary distribution. Now, let n(ss a) = EN, a)] and w(s a) = (N, We rewrite the constraints above as follows
Ex
inf R,, (M)
Σ (() 2 kl(ō, 1 -)..
8,a
Hence, the optimization problem revolves around optimizing in inf M, E. w(s, pjp (s. By Lemma 1 in (Al Marjani al., 2021) we also know that an algorithm that navigates the MDP needs to satisfy the constraints
Σ n(ssa) - P(sss - d') $ Vs E S.
s'aa
After normalizing n(s, a) by n(x, a)/ log(11)0 and using that kl 5) _ lower bound
log(1/6), as + we find the following
EM[T] 1og(1/5)
ii 8-2
H:
where H formulates the optimization problem over follows
(T) == sup A) M,T
inf
Σ w(s (sLP)p((ss)) 8.a
subject to Vs E S, a) = Σ P(sss' d')w(s',a').
staa
Part 3: irreducibility of the stationary distribution. Let lo(M) = fw E A(S x A) E. as) = Er P(s]s', a' (') a') Vs E S}. We note that a solution w E Ro(M) to the above problem that characterizes (M) may not necessarily induce an irreducible chain, i.e. under the induced transition Pa- (s'(s) Σ. P(d'ls, (s.a) E. (x.b) some states may not be accessible (s' is accessible from s there exists N. such that IP M (Sttn 8'1 = 8, w >
25

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
for all under w (Puterman, 2014)). Consider arbitrary starting state so (by Assumption 3.1). If state se is not accessible from so under w", then the number of visits that state is bounded, i.e., supp21 E. Ras (Na a)] co.
Under Assumption 4.3 there exists π E 11, E R₂ such that we can build a confusing model M, In particular, we can build confusing model Mr as in the proof of Proposition 4.1 (see the "sufficient" part of the proof), satisfying
kI(1 6,6) -
Σ
Eas (8, (KKKppIppp
8,0
(MM[N((ss: 1 (8c) (p: (8c));
1
EM(Nr(se क Plsil x ((c))) log
P(si|Ser (Tc))
(e a(sc)) )
+ P(si|se: ((s)) log
A (1 (1-))) ()
< x0.
where $1 E arg m 1p_ (se, {)s and X is a fixed value in (0, 1), independent of ò, taken in the proof of Proposition 4. (in that proof we use instead of X, not to be confused with the confidence parameter). The boundedness of the right-hand side comes from the boundedness of Σ. E5, (Ne a)] < oo for all / 2 I and that À is fixed value in (0. 1). However, as 5 -> 0 the left-hand side scales log(1/5) - oo, which violates the constraint (and the constraint should hold for all E 11, E R. Since this holds for any pair (so, se), and so is arbitrary, an optimal solution wn must induce an irreducible chain over S.
Remark: in general, note that the set of confusing models puls constraints on pairs (8, π (6))) but not necessarily on other state-action pairs. Hence, without further assumptions, we do not have guarantees that an optimal solution yields an irreducible chain. This is in contrast to previous work (Al Marjani et al., 2021; Russo & Proutiere, 2023a; Russo & Vannella, 2024), where constraints also affect pairs s, a + (s).
Last step: ergodicity. This last step, while not necessary, shows that any optimal irreducible allocation can be well approximated by solution w satisfying w[s, a) 0 for all as,a). We show that any w satisfying this latter property forms a dense set in (MM (and, since such (ss, a) is also irreducible over S, it's also dense in the set (o(M) n {w Pa is irreducible over S)).
Consider any wt E (M). Let 10 and w' E E(M).. Define then w> (1 A)w* + Aws.
Then, for any convergent sequence (Ae)s such that lime d = 0, we have that
||* - wxell >x - w'l +. Since for every i we have that wx R(M), and limit points are in (M(M), it follows that (2M) is dense in (M))
B.2.2. OPTIMALITY OF BEHAVIOR POLICIES
An interesting question is to understand in which cases policy is optimal for exploration. For instance, consider the MDP in Figure 1 and the single target policy T(-1s) 02 Vs. For that MDP, it is in general sub-optimal to sample according to such policy, since under state becomes transient. In the following lemma we prove that necessary condition for an optimal exploration policy is to guarantee that states with large deviation gap are visited infinitely often.
Lemma B.8. Let T be the set of transient states under an exploration policy Te- Assume that T + O. If there exists Se T , 11, E R2 such that llp (so))l oo 22/7, then we is not optimal, in the sense that
T,(d"=; -.
(14)
for any stationary distribution dh (of the chain prc) induced by we.
Proof of Lemma 4.5. Since sc. by assumption, is transient under Te, the expected number of returns of the Markov chain to state 8e is bounded, i.e., sup E. E3 (e(,,, a)] < co. In other words, we have that dd (x.) = O.
26

---

Adaptive Exploration for Melti-Reward Multi-Policy Evaluation
Now, the condition || loc 2e/3 guarantees that there exists confusing model by Proposition 4.1. Let 81
arg max, lo (Se, 81)1. Then, can define alternative model P' in the proof of Proposition 4.1:
()
8 + Scs
P(s'|s (s,
Se a + T((c):
P (s)
8+ (1 (1,((11s,,TT8))
(s, a, 80) = (Sc, (So); 81),
61'') (se))
(s,0) (sc. A s' +
Then, from the proof of Proposition 4.1 we know that there exists d E (0, 1) such that P' is an alternative model. Hence, for any stationary distribution d induced by nh obtain
Σ s,
dd (s, (P) P'(, ("(,
Σ
(me aaaaa))KKLP.... a)) P' a)).
where (s a) = d= (T) (als) (and (s) = Ea (s, a)). But - (s = En (Be a). Which, by non- negativity of d==,, implies that o= (Se, a) = for every a. Hence
d= (sa P' O.
Since P' is an alternative confusing model, we have that
inf M'EAll,,,.MM (s.))) =0,
and thus
(To(w"e; (T)( for any stationary wn (s, d= (s)
Therefore, one concludes that necessary condition for an optimal exploration strategy is to guarantee that states with large deviation gap visited infinitely often.
We conclude this section with sufficient condition on the optimality of general behavior policy иg, when used to evaluate single policy æ on single reward. What the proposition points out is that Ty needs to induce sampling distribution a with large sampling rates where (s) is sufficiently large. The extension to multi-reward follows naturally.
Proposition B.9, Consider a behavior policy as and target policy n. Assume that лæ induces an irreducible class over S (i.e., there are no transient states). Denote by d the stationary distribution induced by kg and assume that ng satisfies a (s, T (s) > for all
Then, let Senf {s S lp (s) 0 3</r} be the set of confusing states and assume that Seuf + 0. Define gx,a8(8) (8) == ma supwen(M) w(s) (s, (+))) and A=, d= (s, πT T())) ming d (8', T(s')) Then, under the assumption that 2 7/(1 - 7) we have that the behavioral policy Ty is 2x -ptiimal in the following sense
inf MrAAlt, (M) Σ [e..laaa)))))))p(...)
sup inf wEL(M)) , s.a
Σ Eu(s, (s, a) 22
5.a
where A7.50 min
(5) (65
(s))
Proof. First, note that the first assumption Sent A 0 implies that the set of alternative models Alt not empty by Proposition 4.1.
Let So E Sout- Consider an alternative model p' similar the one used in the proof of Proposition 4.1: ('(s'[s,a) P(s'ls, (s, a) for all * so, a, s', and P'((o|so, a) 8 + ((sal so, a)(1 8), P (s'|8o, 8/|88,, a) (1 P ((s'' (s, a) for s' + Sn-
with 8 E (0, 1). From the same proposition we also know that if d E (0, 1) satisfies
7011p, (8o)
> 2c,
1 1- 1-7(1 5)p%
27

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
then the model is confusing (where PTo guarantee that Pl is an alternative model is to choose satisfying ō > (>00)(= Setting 5 = 2/3, we find
P(sp So. =(so))). Since 18l122(s0))
1-7(1-8ppp 2 (8))l simpler way to
2c
3x
| (80) 1l00
?
which is true by assumption. Hence, for = 2/3 the model is confusing. We now proceed with upper bound of the KL divergence between P and P' in Su:
P(o'(so, a)
PT a) = Σ P(s' P(s'|80, a) log (''(s')su,ai
x log( 8
8
1-6" 8'
< 2.
The first inequality holds by plugging in the definition of P' and noticing log( (08(3+1-8)P P Ro.a) S log( a(
P(solep.a)
((ol))(s
the second incquality holds due to log(z) I x - 1; the last inequality uses that s 2/3 implies 5/(1 6) S Define (s) = max(0, SuPWER(M)) w(s) - d (s))) Then
inf [u(s,a)Klippp (s, S M'AAlS, (M) 8,0
Σ w(s (s,))))
3,
Σ w(so, a (sK a).
< 2w(ss)
$ 2w(so) 2d (80: 7 (s0)),
< 2d (so, (s0)) 2|sup ((0) (so (80)))
went
s 2d (so, क (80))
+ 2. n. (80)-
where we used (s)) = En wss a). On the other hand, we have shown above that for model to be confusing model, the necessary condition is 3s such that K KLppp (8, 2 2[1-2)* 2 (see Lemma B.2). Hence, defining A *x d (s,,((s)) min d ((s)), we have,
inf Σ
inf MeAlt, (M)
Ea de (e, (B)m)))))
M'EAlE, (M)
2 MeAle, (M)
inf
d= (30(
inf MeAl,, (M)
d (3 (B)
2(1 - 7)1
2 (3, T
722
2 2 (8)) + d ( T ((u)))
2 20 ( x(5)) + 2(d (s, (8) d= ((8))),.
2 20 (so, (s0)) 2/min a (s', (ss))) d (so. ((s)))).
2 2 (50, (88)) - 24 (so).
where we used the first equality that (s, 3 (8) (als). and the third inequality that (1-1)* 2 2
28

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Conclusively, have shown that for all R(M), 80 Sent
inf M'EAlE,
inf M'EAlt, (M))
[u(psa)Kloppp(ssa) 2(Ax.=0(00) + =
Therefore
inf M'EAlt,, (M)
Σ (s)
inf M'EAll, (M) 5,8
-22 2A Vo E ((M).
5,a
The previous results, with the following one, useful when studying how mixing target policy with uniform policy affects sample complexity. In the following lemma we study the rate of visits at stationarity when the target policy is mixed with a uniform distribution. Let Pa be the transition function induced by the uniform policy, i.e., Pa(s'l) E. P(s'|s, 1s, 4)/A, and let Pa be the k-th step transition matrix induced by the uniform policy. From the ergodicity of Pa there exists an integer ko such that P= (s'[s) > 0 for all ko and all (s', 8) E S (the existence of ko is guaranteed by Levin & Peres (2017, Proposition 1.7)).
Hence, that end, define
min
min
be the minimal probability of reaching s' from in steps, and let ho min N: me 0). We then have the following result.
Lemma B.10. Let (1 Megt eTa be mixture policy defined the mixture between target policy Tegt and uniform policy Tw. with mixing coefficient E (0, 1]. Let d= (s) denote the average number of visits to state under policy at stationarity. Then, for all stales we have
d 2 Tko
(15)
Proof. In vector form, we can write the stationary equation dPa. Then, we also know that dP2, and therefore 2 edP2 holds element-wise.
d(s) = Σ
Σ
² [(ss) mm.
One also easily show that this property holds for any k-step, thus proving that d(s) 2 en
The previous result is important: for environments where ko is small, and the uniform policy is enough to guarantee high visitation rates (i.e., Tik is not small), then all states are visited regularly.
B.2.3. PROOF OF THEOREM 4.7 (RELAXED CHARACTERISTIC RATE)
Proof of Theorem 4.7. We prove the theorem considering the following general characteristic time
inf M) =Ell,ERR; METTRRM,,EEN M,EAK,
E [K[prr (s,a)),
and we also consider the single-policy case, since the extension to multi-policy follows immediately.
29

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Start by noting that for all r E R we have {MA : IIV Vir, bloo > 2e} CUAM, IV (6) (x((6)) > 2e). Using this decomposition, can show that
Te Tw(w; 2 inf min rER; 60 M. (co) V (00)1>2
inf
E (a (s
inf rER; 50 M (0o) me (so)
inf min
Σ
L(s'sa))te (KKKp))p)pppp(
8'a
inf FER: MAV (se) Me (20)
inf min
Σ
t (otep())))pppppppp70 ((8
where we used the fact that the problem is unconstrained for state-action pairs (s)) In fact, letting (s) VM, (s) Vi: (s) we have (s) >/AP(s, a(s) VM, +
((s) AVF], which only involves pairs of the type
(s, (s)). Alternatively, note that one can always claim
inf Mr. 2.
inf (d((,)) (r0) Mc (00)1>2
Ew(s, (s,
M.IVE, (fo)
s'.0
due to the non-negativity of the terms involved.
Then, observe the following inequality:
(s)] = (() (()) VV
=>/AP(s, T (s)) VM. + P,(s IT ( AV.
<> <>/AP(s; (8)) VM. + AV 1000
Since the inequality holds for all we derive |,,, S | cc I max -2B AP(s' ((')) V J. and thus
72
I max (1 71- 4 AV (50)) <
((s) TVM.
Now, note the following equality
AP(s (s)) VM, = =s)
Therefore, using Holder's inequality, that |p||] S 2|lp||TVv for distribution p, and Pinsker's inequality, we obtain
4-2
2e < max (1 71-
IAP ( क. (1))
272
< max (1 71
KL KLP (s' T(s (s))
2-2
KT (s', w0s' (ss))
max (1 71-
w(s w(s' (s')) |l (x4(((')) (s')l
< max (1 (1-7)² 7)2 Kbplpd (5) (s (s5)) max lIp 123 w(s, ग (s))
27²
Therefore )1- (s), < max KT.plP: (s), ( (s')), and thus [>)
7² ming
(u(o (s)) 2 max KLpppp (s', ( (())) 26 - 7)²
w(s, - (())
Σ
min
22
Tp: (s)
Using this inequality in the initial lower bound of (ww M) we find
() > inf min 2c (1 - (1-7)2w W) (s))
rR
7²llp;(()) (s)
which concludes the proof.
30

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
B.2.4. PROOF OF COROLLARY 4.8
Proof of Corollar 4.8. We begin by rewriting the following optimization problem of (we M). Note that sup max |pp (s)ll = max sup max (s, ss) rER+
FER+
2
sup (s,
max max o'
FER
sup Pf (8, sup -p%(s,8)) PER,
mIXX 118X max
EER,
From the proof of Lemma B.6 we can derive the following expression (T = = where (T(() K" (s) (* (T P ()))
=-
and est is the s'-th element of the canonical basis in R.S. Hence, the optimization problem supreR PJ (') is linear program.
In the last part of the proof we consider the where R, [0, 1] We exploit the following fact that holds for any vector y E R" =0. y" Eimoo Y4. Then, let 17) (s) = (K (s)G"); and define
(T,
Σ
(8))
and, similarly, 1 (8, 8')= ===== -Eirz, (0)c0 1 (8). Hence, we have
( (8) max (s, r (8, (8, rE(0,1]
max
B.2.5. COMPUTING THE OPTIMAL RELAXED CHARACTERISTIC RATE U
For a general polytope of rewards, defined by (A, one can write the following program to solve us (8, suPrER PT s')
Ux (x( = max t rE(0,3)5,IER
subject to (s)r Ar
(16)
This formulation is a linear program since the objective and all constraints are linear in the decision variables. The polytope can represent various convex sets, including hypercubes, simplices, or other polyhedral shapes, depending on the specific application. In contrast, the optimization for the reward-free case is straightforward, which follows from the result in Corollary 4.8.
Therefore, given a collection of deterministic target policies { and reward sets [R, J (finite, or a convex set), we precompute, for every policy and state s,
sup eT (s)r, sup -e]I" -e)
As = max max
rER:
rER;
The inner sup is solved twice in the general case. For a finite reward set is a direct maximum, and one can directly compute (s(s) = max,' max,eR; p. (s, s2 For the reward free case we can use the result from Corollary 4.8 to obtain (s)s) = max,' max (I (s, 1"
Stacking the rows A, yields a matrix A E R Nx(S) For a stationary occupancy measure w E ((M) we define f((w)
72 2c 7)2 (s)) The optimal relaxed rate is obtained from the convex optimisation problem
max A((s) SES
U = min max fi(w) s.t. [ss,,a= Σ w(s'sa d') s',a') vs.
WEA (Sx.) i=
8'
31

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Riverswim complexity
106
$
$ = 20
10a
10c
SUp max, la
104
10
10a
10
R = [0, 1]
10a
{r: ||r|| 1)
0.25
0.50
0.75
10
20
30
Probability p
State size
S
Figure 5. Complexity of Riverswim for varying reward sets and state space sizes for single policy л(-) = 02 that moves towards the river's 's end. Left: complexity for different p values (prob. of moving toward the river's end). Right: complexity for porp- = 0.3 with varying state space sizes. Solid curves evaluate on R [0, 1] dashed curves on R {r E [0. 1] |rlla s 1).
We solve this minimax programme with CVXPY, initialising from the previous run warm-start the solver (Diamond & Boyd, 2016).
As an example, in Figure 5 we show the policy evaluation sample complexity in the Riverswim environment (Strehl & Littman, 2004) for single policy æ. In this environment the agent swims towards the river's s end, while the river's current opposes the movement of the agent. The policy tries move the agent toward the river's end, and, p (the probability of moving toward the river's end) decreases, the reward-free sample complexity increases.
Scaling of Reward-free Sample Complexity An Example
32

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
C. MR-NaS and Numerical Results
C.1. MR-NaS Proof of Theorem 5.2 Proof of Theorem 5.2. Let Ca.r {IIV;= 1oo 1oo0 > e) be the event that at the stopping time the value estimate is not (-accurate in π, r E Rx Hence, we have that M E (M+) Therefore, we can say that
C (3r II, Rx ||V," lo e) {3r E II, E R₂ : M E AM,))(M))
Then, we obtain the following chain of inequalities:
PM (Ts C),C)
M (3I 1: UU (NN
$ M
3 1: N1 (N,1; M,) ((N,,)).
PM
3 2215 1:
inf
Σ M(ssa)KLM S(N,,
x x E..R. M s.a
< PM
3t 2212 1: Σ
M(ssc)KLM,, B(N..))
8
where the conclusion follows from Jonsson et al. (2020, Prop. 1).
For the sample complexity, we use the following facts:
1. The forcing policy is chosen as (T(s(-ss)
softmax (- with Br(s) max(I_max, (s,a) minn (s(s,b])) 3 E [o, 1] and (softmax(x)): e E, e* for vector x. This choice encourages to select sameres actions for B > while for 3 we obtain a uniform forcing policy T (a)(a 1/A. We then mix W/ with f,t using mixing factor e = 1// max(1, (s::)) with Ne(s) Σ. (i,s, a). The values a, need to guarantee + B <
B (o))
(Russo & Vannella, 2024). Under this choice the chain induced by is ergodic.
2. We also note that the optimal solution w* satisfies w (s, a) 0 for all (s, a). Then, such solution induces ergodic (irreducible and aperiodic) chain by Assumption 3.1 and Assumption 5.1.
3. We note that the solution w² is unique by Assumption 5.1.
4. Then, the sample complexity results follow from noting that (2/ M) (U:(w; M) and applying the same methods as in Russo & Vannella (2024, Theorem 3.3) mutatis mutandis (which follows the proof technique of (Al Marjani et al., 2021)).
C.2. Environment Details
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 (Strehl & Littman, 2004), Forked Riverswim (Russo & Proutiere, 2023a), DoubleChail (Kaufmann et al., 2021) and NArms (Strehl & Littman, 2004) (an adaptation of SixArms to N arms). Here we provide brief description of the environments.
Riverswim. The RiverSwim environment is classic reinforcement learning benchmark designed to test exploration (Strehl & Littman, 2004). It consists of 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 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 Figure 6 is shown a depiction of the environment. There are n states, and two main parameters, p. p' E (0, 1), and their sum Psum = p + p' 1. In the figure, each tuple (a, p) represents the action a that triggers the transition and the
33

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
probability p of that event. The agent starts in state Sy, and in every state can only take two actions ( d1). For small values of p it becomes difficult for the agent to swim right (i.e., reach 8n-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;-1|8;, ao) 1. For the experiments, we used n E {15, 20, 30), p 0.7, p' = 6(1 - pp/77.
(4o, 1), (a1,
(aI.p') p')
(a1.p")
(0o, 1), (a1.p)
(01.p)
(01.p)
(aI.p)
(aI.P)
80
$2
8n-2
8n-1
(ag, 1). (01, poum)
(ags 1); (ai, Poum) (ag: 1); (a1,
Poum)
(oo, 1), (a1. p)
Figure 6. Riverswim environment (Strehl & Littman, 2004). Each tuple (a,p) represents the action that triggers the transition and the probability of that event.
The Forked RiverSwim environment (Russo & Proutiere, 2023a) 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 generalize across different paths within the environment.
Forked Riverswim.
In Figure 7 is shown a depiction of the environment. There are a total of 2n + states, and two parameters p. E (0. 1), so that Psum p + p' < 1. In the figure, each tuple (a,p) represents the action that triggers the transition and the probability p of that event. The agent starts in state So, and in every state chose between three actions {as, 01 42 J. 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; 1822, ao) = 1. For the experiments, we used n E {8, 10, 15}.p- = 0.7. p' = 6(1 p)/7.
(eo, 1). (a,, 1 p). (cz.) 1)
(a1.p')
(as.
(01.1/)
(ar p). (az.
(1))p)
(ap.p)
8D
$1
Sn-1
8p.
(oo: 1). (m,,
(ao, 13, (a1,1 Poum
(oo, 1), (as, 1
(va.1)
(az. 1)
(oz, 1)
(os, 1)
(az. 1)
(02, 1)
(Rg. 1) (0), )
(a).p)
(ai.p)
s
8/2
(ao, (a..1 Poum)
(no. 1), (ai,
(a1.p")
(aI.p')
(a1.p")
(as. [az.
Figure 7. Forked Ri Riverswim environment (Russo & Proutiere, 2023a). Each tuple (a.p) p) represents the action that triggers the transition and the probability of that event.
Double Chain. The Double Chain environment (Kaufmann et al., 2021) 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 Figure& 8 is shown a depiction of the environment. There are a total of 2n + 1 states, and one parameters E 10, 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 sg. and in every state can chose between two actions (ag, a1). 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 E (8. 10, 15), p = 0.7.
34

---

Adaptive Exploration for Multi-Policy Evaluation
(01
(01.p)
(01.p)
(wx
$1
Sn-1
Spp
(ap. 11
Lo.
(4o. 1). (ar.1 p)
(eo. 1). (ar,1 p)
(ao. (a1. 1 p)
(a1: - p)
50
(as. 1)
(01.p)
(aI.P)
(a1.p)
(do. 17
(a1:1 p)
$1
8n-1
(no: 1), (a1,)
(ao, (a1. p)
(ou, 1), (01, - p)
(#1.P)
Figure Double Chain environment (Kauffann et al., 2021). Each tuple (a.p) and the prohability p of that event.
p) represents the action a that triggers the transition
NArms. This environment an adaptation to N arms of the original 6Arms environment from (Strehl & Littman, 2004). Differently from the previous environments, this is bandit-like environment, where the agent presented with n different actions (or arms) to choose from. The agent starts in state 8q and selects an 0z- Upon selecting an arm, the agent may transition to corresponding state s,. 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 Figure 9 is shown depiction of the environment. There are total of n + 1 states, and one parameters Po E (0, 1). In the figure, each tuple (a, p) represents the action a that triggers the transition and the probability of that event. The notation anozng indicates all the actions in (angs.. ano+n) The agent starts in state 50, and in every state she can select between n actions {ao, ai,..., an- 1 J. For small values of Pu it becomes difficult for the agent to move to different states. Similarly, is harder to navigate to states s; for large values of n. We used po 0.7 and (10, 20,30).
(00mn 2.1) 1)
(Bo. 1)
8n
(an 1.P0/M)
(aim 1)
81
[a:,1 - po/(1 + 1))
(on-1.1)
(0a,
(an 2: Po/(12 1))
si
(a2m 1)
$n-1
(Bn-2in: 1)
(at.po/3) 22)
(doin-a,1)
(Gpa1 1)
Figure 9. NArms environment. Each tuple (a, p) represents the action that triggers the transition and the probability of that event. In the figure the notation ungimott indicates all the actions [Amg..... ann++... J. In state so the probability to remain in so for any action is (( (so a;) = 1 Po/( + 1), with the exception that P(so an) = 0.
C.3. Algorithm Details
In this section we briefly explain the mechanisms of each algorithm used in the experiments, and, in case, their adaptation. Note that for all algorithms we evaluated the policies by using the MDP estimate M, through policy evaluation.
35

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
Noisy Policy (Uniform). This method simply computes a mixture of the target policies Tmix Tmix (als) which is then mixed with uniform policy Tu with a constant mixing factor Et = 0.3. The resulting behavior policy is Ex) Tmix + Ex
[||]
T
Noisy Policy (Visitation).
This method similar to the previous one, but the mixing factor is not constant anymore. We take a mixing factor that is = 1/Ne(s+). which based on the number of visits to state 8t. The resulting behavior policy is T =
E1 Tmix + ET
SF-NR (Mcleeo et al., 2021). This is an algorithm for multi-task policy evaluation based on the Successor Representation. The pseudo-steps of the algorithm can be found in Algorithm 2. The method maintains a successor representation t'x,4 for each policy æ, as well as behavior policy иg. These are learned using TD-learning, and the behavior policy uses the variation between 8/8,++1 and Va,r as a reward. In our experiment we used temperature T 2 and a discount factor for the successor representation % 0.99.
Algorithm 2 SF-NNE
Require: Discount factor 7; Temperature T; Successor discount factor 7/5 policy II. .., AA) for states s. 2: Set 1),, a) = for all as
I: Set (-(sss)
3: while not done do
4: Compute +-(+ Sof (<s)
5: Sample a, from (1 (1)8)) + Es/ and observe 8c+11 Pt))
6: for E IT
7: Compute 6R = + the ( (84+1, T ((8411)) - (F1, (81, as)
8: Set (e,,41((1, a.) = Vi (5,, ar) + andi, where 1/ (st.
9:
end for
10:
Compute de.t 1/|1 Even [Vee(W)e.)1) - Vec(va.e)
11:
Update (a) + (s.))) ) + (8p.1 + yuax. Ta(a(s441) (T((a))))), where = 1/Ne(st,,.)
12: Update MDP estimate M: and set L <- 1+1.
13:
end while
GVFExplorer (Jain et al., 2024). This method considers variance-based exploration strategy for learning general value functions (Sutton et al., 2011) based on minimizing the MSE. The pseudo-steps of the algorithm can be found in Algorithm 3. Given the current estimate of the MDP Mr, the method estimates Var (t), (t), the variance of the return G ri + 7r2 + 72rg + +... under n staring from (s, a). Vo II, (s, a) E S A. Then, behavior policy is computed as (als) = v / (ar.,)
E. v E.en ((h (") Lastly, we mix this policy with a uniform policy. For this method we used a fixed
mixing factor = 0.3 (we did not use visitation based mixing factor because performance deteriorated).
Algorithm 3 CVFExplcrer
Require: Mixing factor policy set TT.
I: Set Var (1) = 1 for all (s,a) E SSX A
2: while not done do
3: Set (T((s))) = V saals)
Σ. / (Ma)Var 4: Sample a, from (1 E)TT( + s/A and observe 8141 ~ P(-ls,, a.).
5: Update MDP estimate Ms, variance estimates [Var" (t))xen and set / <- t 1.
6: end while
Note that σy similar to the generative solution in Equation (2) (i.e., n(M) A(S A)). In fact, GVFExp lorer neglects the forward equations when deriving Tg. The resulting solution does not take into account the dynamics induced by the behavior policy, effectively making it generative method (compare with the generative solution proved in (Al Marjani & Proutiere, 2021; Russo & Proutiere, 2023a)). We believe this is due to a term being omitted in the proof of Jain et al. (2024, Theorem 4.1) that accounts for how changes in the state distribution induced by the behavior policy impact the variance.
MR-NaS. For MR-NaS we computed the exploration strategy w every 500 steps in the environment, to avoid excessive computational burden. The policy is then mixed with forcing policy that is (-)s) = softmax (s), with
(.(s) max, (N.( N.(a,T]
0 Olog( (+)) 8 E [0, 1] and (sof (oofmaax())). = e. Σ, eaa for a vector æ. This choice encourages to
36

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
select under-sampled actions for 3 >> O, while for 3 0 we obtain uniform forcing policy ( 1/A. We then mix wi with ftt using mixing factor 6 1/ max(1, (s:)), with N&(s) Ea Ne(s,a). a). The values a, B need to guarantee + B < 1 (Russo & Vannella, 2024), hence we chose 0.99 and 3 = 0.01.
C.4. Additional Results and Experimental Details
In this sub-section we report additional results. To run reproduce the results, we refer the reader to the README md file in the supplementary material. In Figure 10 are reported the results for the multi-reward multi-policy case with various sizes of the state space. Similarly, in Figure 11 are reported the reward- frree results for the multi-policy case, and in Figure 12 the results for the single-poliey reward-free case. Experiments were run over 10 time-steps, with 30 seeds. Confidence intervals were computed using bootstrap (Efron, 1992).
Experimental Details: target policies. In all experiments we fix a discount factor y and run each simulation for T time steps. In the multi-policy scenario, for each random seed, we choose m target policies as follows:
1. Draw without replacement three state-action pairs (s) az )== uniformly from S x A.
2. Define the one-hot reward r; a) = 1((s, a) = (s a and compute the target policy ne is computed via policy iteration on (M, r;).
On the other hand, in the single-policy scenario we use a default target policy policy adef that is different for each environment. Concretely, solve policy iteration a fixed onc-hot reward 7def where Taet a) 1 ((s.a)=(staa))) for some state "²,a"). Then, the target policy is computed via policy iteration on (M,
In particular, for Ri riverswim have (a)) ) (s,-1, 01); for Forked Riverswim we have (s*,a") a²) (8 a1); for Double chain we have (s",a*) a²) = (5 a1); for NArms we have (s* a²) (8n, an-1). See also Appendix C.2 for more details on the environments.
Experimental Details: reward sets. We the following reward sets: finite rewards and the reward-free scenario.
In the finite reward-set scenario, we restrict Reanon (sampled without replacement).
{ri}; to a uniformly chosen subset of size 3 from the canonical basis
In the reward-free scenario, we use MR-NaS with the result in Corollary 4.8 and evaluate the collected data over the entire basis Reanon for each m;
Experimental Details: evaluation protocol. During each run of T' steps, the agent collects transitions and updates its empirical model P.. Every F steps, we perform batched evaluation:
1. For each reward set (finite reward-free) and each policy и, compute the true value VM, offline via value iteration on the known dynamics. For the reward free case we use Reanon to perform evaluation.
2. Compute the estimated value V.2 (t) by performing policy evaluation on P. over the reward sets.
37

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
SF-NR
GVTExplorer
MR-NaS
Noisy Policy (umif.) DoubleChain
Noisy Policy (visit.) NArms
Riverswim
ForsedRiverswin
100
10-1
Elmaxx,1
10-2
0.0
0.5 Time-steps x10
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 Time-steps
Time-steps
x x10
Tine-steps
x x10
x x10
SF-NR
GVFExplorer
MR-NaS
Noisy Policy (unif.) DoubleChain
Noisy Policy (visit.) NArms
Riverswim
Riversin
Elmaxz, [V V
10
10
10-2
0.5
1.0
0.0
0.5
1.0
0.0
1.0
0.0
0.5 Time-steps
Time-steps
x x10
Time-steps
x x106
Time-steps
x10
x x10
SF-NR
GVFExplorer
MR-NaS
Noisy Policy (unif.) DoubleChain
Noisy Policy (visit.) NArms
Riverswim
FoveedRiverswin
V Vl oc
100
10-1
Elmax
10-2
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x10%
Time-steps
x 108
Time-steps
x
x10%
Figure Multi-reward polliippolcy evaluation for different sizes the MDPs: from top bottom state space size is 15, 20, 30. Shaded curves represent 95% confidence intervals.
38

---

Adaptive Exploration for Multi-Rewart Multi-Policy Evaluation
SE-NR
MR-NaS
Noisy Policy (unif.) DoubleChain
Noisy Policy (visit.) NArms
V [1oo
Riverswim
ForkedRiverswin
100
E/max V
10
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x x10
x x10
Time-steps
x x10
10
SF-NR
MR-NaS ForkedRiverswin
Noisy Policy (unif.)
Noisy Policy (visit.)
Riverswim
DoubleChain
NArms
V 1looo
100
V
E mäx
10-1
0.0
0.5
1.
0.0
0.5 simessteps
1.0
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x10
x10
Time-steps
x10
x10%
SF-NR
MR-NaS Riverswinn
Noisy Policy (unif. DoubleChain
Noisy Policy (visit.)
Riverswim
NArms
Va V. ooo
V
100
E
10-1
0.0
0.5
1.0
0.0
0.5
1.0 x 10
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x10
Time-steps
Time-steps
10
x10%
Figure 11. Reward-FFFr Free multi-pplic evaluation for different sizes of the MDPs: from top bottom the state space size is 15, 20, 30. Here we depict the average error over the canonical basis Reanonical- Shaded curves represent 95% confidence intervals.
39

---

Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
MR-NaS
Noisy Policy (umif.)
Noisy Policy (visit.)
Riverswim
ForkedRiverswim
DoubleChain
NArms
V
10"
E/maxxy V
10-1
0.0
0.5 Time-steps
1.0
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
0.0
0.5 Time-steps
1.0
x10
Time-steps
x x106
x10%
10
MR-NaS
Noisy Policy (unif.)
Noisy Policy (visit.)
Riverswim
ForkedRiverswin
DoubleChain
NArms
V. ool
100
V
E m
10-1
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5 Time-step
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x10
Time-steps
x x106
x10
x10%
MR-NaS
Noisy Policy (umil.)
Noisy Policy (visit.)
Riverswim
FivsedRiv
DoubleChain
NArms
Va Voallo ooo
100
V
Elmax
10-1
0.0
0.5
1.0
0.0
1.0 Time-steps x 10
0.5
0.0
0.5
1.0
0.0
0.5 Time-steps
1.0
Time-steps
x x10
Time-steps
100
x10%
Figure 12. Reward-FFrre Free single-pole policy evaluation for different sizes of the MDPs: from top bottom the state space size is 15, 20, 30. Here we depict the average error over the canonical basis Reanonieal- Shaded curves represent 95% confidence intervals.
40


Reviews:
[{"review_id": "PEFV7xPqy9", "reviewer": "Reviewer_kVSU", "summary": "This paper studies the problem of devising an optimal data-collection policy that can evaluated policies in multi-reward and multi-policy setting. The paper adopted a PAC sample complexity perspective over finite or convex set of rewards. The analysis of the problem revolves around the set of alternative set and constructing lower bounds for related concepts. The proposed algorithm for the problem is adopted from (Russo & Vannella, 2024). Empirical results on 4 benchmark shows promising performances compared with some existing approaches.\n_______________________________________\n### Update after rebuttal: I appreciate the authors’ effort in rebuttal. Most of my concerns have been addressed. However, considering the manuscript would benefit from clearer exposition, in particular, with that of (Russo & Vannella, 2024), I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s  feedback and the time they dedicated to evaluating our paper. Below, we provide detailed responses to each of their concerns.\n\n> It is quite important to distinguish the work described in this work and that of (Russo \\& Vannella, 2024). [...] With clear distinctions, it will position the current paper better.\n\nWe thank the reviewer for the comment. Prior work has focused on the Best Policy Identification (BPI) problem, but the technique is far more general and can be applied to other problems. Our contribution is to show how the same broad approach can be applied to the multi-reward, multi-policy evaluation setting.  \n\nThe overall technique is inspired by approaches in Best Arm Identification (Garivier \\& Kaufmann, 2016), where the problem is cast as a hypothesis-testing framework to distinguish the true model from the \"worst'' confusing model (see also Degenne \\& Koolen, 2019; Al Marjani et al., 2021). This perspective permits to compute an exploration strategy $w_t^*$ at each time step that maximizes the evidence gathered from the model (depending on the set of possible alternative models).\n\nWhile the general algorithmic structure is similar in all these works, the specific optimization problem in computing $w_t^*$ differs because of the way the lower bound is derived here (i.e., how the reward set and its geometry affect sample complexity). In BPI, the complexity depends on value gaps $\\Delta_r^\\pi(s,a)=V_r^\\pi(s)-Q_r^\\pi(s,a)$, whereas our analysis involves $\\rho_r^\\pi(s,s')=V_r^\\pi(s')-\\mathbb{E}_{s''\\sim P(s,\\pi(s))}[V_r^\\pi(s'')]$. Hence, in BPI a different analysis is needed to derive the optimization problem.\nWe will clarify these distinctions more explicitly in the final version of the paper.\n\n\n> Around line 145, the paper mentioned the considered target policies are deterministic policies. Will analysis for stochastic policy be significantly different?\n\nThe analysis can be carried out with stochastic policies in a similar way (in the appendix we also have results for stochastic policies), and we will point this out in the paper. We chose to mainly work with deterministic policies to avoid overly cumbersome notation.\n\n> In Line 211, it says confusing set will be close to $M$ (in the KL sense). However, in the definition of the set of alternative models, only shows distant way by $2\\epsilon$ in infinite norm sense. Please clarify these concepts.\n\nWe thank the reviewer for the question and the opportunity to clarify this point. The set of alternative models $Alt_{\\pi,r}^\\epsilon$ contains all models $M'$ satisfying $\\|V_{M_r}^\\pi - V_{M_r'}^\\pi\\|_\\infty > 2\\epsilon$. The sample complexity is characterized by the ``worst'' model in this set, i.e., the one that maximizes the sample complexity. This is exactly what we do in Eq. (2): we solve an optimization problem that tries to find an alternative model that minimizes the KL-divergence between the transition function $P$ of $M$ and the transition function $P_r'$ of an alternative model $M_r'$. We will make sure to clarify this point in the paper.\n\n> In Line 219, it’s unclear on what does it mean that $P(s,a)$ is continuous w.r.t. $P'(s,a)$ as $P(s,a)$ is not a function of  $P'(s,a)$. Please elaborate.\n\nWhat we mean is that $P(s,a)$ is an absolutely continuous measure with respect to $P'(s,a)$. In other words, for all $s'$ such that $P'(s'|s,a) = 0$, we have $P(s'|s,a)=0$. We will clarify this in the paper.\n\n> The definition for $P_r'(s,a)$ is unclear.\n\nWe understand that this definition may seem odd. For an alternative model $M_r'$, we denote by $P_r'$ its transition function(the subscript $r$ is only added to highlight for which reward $r$ the transition function induces an alternative model). We will explicitly explain this notation in the paper.\n> Typo: Line 22 right column, different task $\\to$ different tasks.  Typo: Line 69, a period is left out.\n\nWe appreciate the reviewer pointing out these typos. We will correct them in the paper.", "claims_and_evidence": "Largely yes, but some details can be provided for clarity. See comment sections for details.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "The reviewer didn’t implement the pseudo code in the local machine to redo the experimental studies, but went over the simulation results.", "relation_to_broader_scientific_literature": "The paper studied policy evaluation reinforcement learning in the setting of multi-reward and multi-policy setting. It poses an interesting question of finding an efficient sampling strategy under such setting. The problem seems to be general and contains traditional RL as a special case.", "essential_references_not_discussed": "The reviewer believes essential related works are there.", "other_strengths_and_weaknesses": "Strength: The paper poses an interesting question of finding an efficient sampling strategy in the setting of multi-reward and multi-policy. The empirical results show promising results over existing algorithms.\n\nWeakness: See the comment section below.", "other_comments_or_suggestions": "1.\tIt is quite important to distinguish the work described in this work and that of (Russo & Vannella, 2024). This is because the algorithms are exactly the same, and in (Russo & Vannella, 2024), the problem is also about to identify a policy identification problem. With clear distinctions, it will position the current paper better.\n2.\tAround line 145, the paper mentioned the considered target policies are deterministic policies. Will analysis for stochastic policy be significantly different?\n3.\tIn Line 211, it says confusing set will be close to M (in the KL sense). However, in the definition of the set of alternative models, only shows distant way by 2$\\epsilon$ in infinite norm sense. Please clarify these concepts.\n4.\tIn Line 219, it’s unclear on what does it mean that $P(s,a)$ is continuous w.r.t. $P’(s,a)$ as $P(s,a)$ is not a function of $P’(s,a)$. Please elaborate.\n5.\tThe definition for $P’_r(s,a)$ is unclear.\n6.\tTypo: Line 22 right column, different task -> different tasks\n7.\tTypo: Line 69, a period is left out.", "questions_for_authors": "Please see the comment section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VVqyM5m7tE", "reviewer": "Reviewer_QAVi", "summary": "This paper addresses the problem of online multi-reward multi-policy evaluation in reinforcement learning, aiming to estimate the value functions of multiple policies across diverse reward sets with (ε, δ)-PAC guarantees. The authors derive an instance-dependent sample complexity lower bound that scales with a value deviation measure, capturing the interaction between rewards and transitions. They propose MR-NaS, an adaptive exploration algorithm that leverages this bound to guide efficient data collection. The algorithm extends prior work on Multi-Reward Best Policy Identification (BPI) and is shown to be asymptotically optimal. Experiments in tabular environments demonstrate MR-NaS's effectiveness compared to baseline methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for evaluating our work and acknowledging the novelty of our paper. \n\nBelow, we address your concerns in detail.\n\n\n>The communicating MDP assumption may restrict applicability to environments with transient states.\n\nWe note that our focus on communicating MDPs is a standard assumptions in Best Policy Identification (see Russo \\& Vannella, 2024 and Al Marjani et al., 2021). For weakly communicating MDPs, as $\\delta \\to 0$, transient states have negligible impact on the sample complexity asymptotically. Our main goal here is to illuminate how MDP-dependent quantities shape sample complexity for multi-reward multi-policy evaluation.\n\n> Experiments are limited to tabular domains; extensions to high-dimensional or continuous spaces are not discussed. Practical aspects (e.g., handling model estimation errors in non-tabular settings) are underdeveloped.\n\nExtending our theoretical framework and algorithms to non-tabular settings is indeed an exciting future direction. As this is the first work on multi-reward multi-policy evaluation with instance-dependent PAC guarantees, we prioritized a rigorous treatment in the tabular setting (e.g., characterizing confusing models, establishing a reward-free sample-complexity bound). Furthermore, many theoretical investigations often do not include empirical evaluations; we believe our  experiments in the tabular setting offer valuable insights into the practicality of our approach and can inspire  future lines of research involving function approximation.\n\n> How does sample complexity scale with the number of policies/rewards? A scalability analysis would help assess broader utility.\n\n\n\n\nThe result in Theorem 4.5 shows that the sample complexity depends on the _worst_ reward-policy pairs in the sets of rewards and policies considered. These “worst” pairs can differ from one MDP to another—what is easy in one MDP could be difficult in another. This captures the inherent difficulty of the reward-policy sets and is not just a sum over individual pairs.\n\nFor example, in the generative setting, choosing a uniform distribution $\\omega(s,\\pi(s)) = \\frac{1}{|S|}$ yields a bound on the order of \n$\nO\\left(\\max_{\\pi,r}  \\frac{\\gamma^2 |S|  \\max_s ||\\rho_r^\\pi(s)||^2}{4 \\epsilon^2 (1-\\gamma)^2}\\right),\n$\nand we have $\\|\\rho_r^\\pi(s)\\|_\\infty = O\\left(\\frac{1}{1-\\gamma}\\right)$. Consequently, this yields a worst-case scaling of\n$\nO\\left(\\frac{\\gamma^2|S|}{4\\epsilon^2 (1-\\gamma)^4}\\right),\n$\nwhich is independent of the number of policies/rewards. We will ensure to clarify these points further in the final manuscript.", "claims_and_evidence": "See the comments below", "methods_and_evaluation_criteria": "See the comments below", "theoretical_claims": "See the comments below", "experimental_designs_or_analyses": "See the comments below", "relation_to_broader_scientific_literature": "See the comments below", "essential_references_not_discussed": "See the comments below", "other_strengths_and_weaknesses": "Strengths:\n\n- The work is the first to provide instance-dependent sample complexity bounds for multi-reward policy evaluation, addressing a gap in PAC guarantees for this setting.\n- The analysis introduces a novel value deviation measure and connects it to sample complexity, offering insights into how reward structure impacts evaluation difficulty.\n- Applications in areas like language model fine-tuning and robotics motivate the problem, highlighting real-world significance.\n\nWeaknesses:\n\n- The communicating MDP assumption may restrict applicability to environments with transient states.\n- Experiments are limited to tabular domains; extensions to high-dimensional or continuous spaces are not discussed. Practical aspects (e.g., handling model estimation errors in non-tabular settings) are underdeveloped.", "other_comments_or_suggestions": "NA", "questions_for_authors": "- How does sample complexity scale with the number of policies/rewards? A scalability analysis would help assess broader utility.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CplyhwJ9zr", "reviewer": "Reviewer_Xa3p", "summary": "This paper investigates the problem of efficiently evaluating multiple policies across multiple reward functions in an online discounted setting. The authors provide an instance-specific lower bound on sample complexity and leverages it to design an efficient exploration strategy, adapting the MR-NaS exploration scheme. The paper provides theoretical guarantees on sample complexity and demonstrates the effectiveness of the approach through experiments in tabular environments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their evaluation of our work and their positive remarks.\n\n\n> The key contribution is of this paper is that this is the first work for multi-reward multi-policy evaluation. [...] However, a limitation is that the discussion is only restricted in the tabular setting. With function approximation, computing $w^*_t$ can be very hard and inefficient. \n\nIndeed, we plan to extend our framework to include function approximation. However, as this is the first work specifically focused on multi-reward multi-policy evaluation, we focused on having solid theoretical results in the tabular regime  (e.g., characterizing the set of confusing models and deriving a reward-free sample-complexity bound). Furthermore, many theoretical investigations  often do not include empirical evaluations; we believe our experiments in the tabular setting offer valuable insights into the practicality of our approach and can inspire  future lines of research involving function approximation.\n\n\n> I wonder the relationship of this work with reward-free RL. It seems that reward-free RL can potentially solve this problem, since reward-free RL can collect an informative dataset without the knowledge of reward and guarantee accurate estimation of the value functions given any reward.\n\nWe thank the reviewer for the opportunity to clarify this point. Note that our setting encompasses reward-free RL but not vice versa, since our problem formulation can handle both finite and convex reward sets (thus covering the entire set of rewards, as in reward-free RL). Furthermore, the instance-dependent perspective directly accounts for the complexity of the reward set, whereas reward-free RL typically does not.\n\nMoreover, while reward-free RL can indeed collect an informative dataset without knowledge of the reward, for problems with a small number of rewards, using reward-free RL may unnecessarily increase the sample complexity.\n\nLastly, in Corollary 4.6, we provide an instance-dependent sample-complexity result for the entire set of rewards (as in reward-free RL). This result is novel, and we emphasize that such instance-dependent analyses are not common in the reward-free setting.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I checked all the theorems, and they looked good to me.", "experimental_designs_or_analyses": "Yes, the experiments look good to me.", "relation_to_broader_scientific_literature": "The key contribution is of this paper is that this is the first work for multi-reward multi-policy evaluation. It provides a lower bound for the sample complexity and proposes a provably sample-efficient algorithm, which lays solid theoretical foundation for this topic. However, a limitation is that the discussion is only restricted in the tabular setting. With function approximation, computing $w^*_t$ can be very hard and inefficient. I would suggest the authors try finding an efficient surrogate of this step and implementing their algorithms in more complexed environments, which would make a greater impact.", "essential_references_not_discussed": "I wonder the relationship of this work with reward-free RL. It seems that reward-free RL can potentially solve this problem, since reward-free RL can collect an informative dataset without the knowledge of reward and guarantee accurate estimation of the value functions given any reward.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "34s766yzfc", "reviewer": "Reviewer_pv4R", "summary": "This paper studies sample-efficient exploration for the multi-reward multi-policy evaluation problem, which aims to simultaneously evaluate all target policy-reward pairs. The authors use an instance-specific lower bound to guide the design of their proposed efficient exploration method. Furthermore, they propose a convex approximation for bound computation and present numerical simulations to demonstrate the effectiveness of their method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thanks the reviewer evaluating our work and their positive appreciation of our paper. Below, we address your  questions:\n\n> In my understanding, the first bullet below Proposition 4.1 suggests that if the condition is satisfied, then Alt is empty, leading to a no-confusing scenario. Is my understanding correct, or am I missing something?\n\n The reviewer's understanding is correct: as $\\epsilon$ increases or $\\gamma$ decreases, the condition is more likely to hold, which leads to a no-confusing scenario. In the text, we mistakenly wrote the opposite due to a last-minute change in the direction of the inequality in Proposition 4.1. We will correct this in the final version of the paper.\n\n> I would appreciate a clarification on how the authors' algorithm differs from the prior work MR-NaS [...] If there are no algorithmic differences, should I understand the contribution as providing a theoretical sample complexity bound for applying MR-NaS to the Multi-Reward Multi-Policy Evaluation problem?\n\n\nWe thank the reviewer for the opportunity to clarify this point.  \n\nThis algorithmic structure is actually inspired by approaches in Best Arm Identification in Bandit problems (Garivier \\& Kaufmann, 2016), where it is common to apply a Track-and-Stop procedure. This procedure computes   an exploration strategy $w_t^*$ at each time step and sample the next action from it (for more examples, see also Degenne \\& Koolen, 2019; Al Marjani et al., 2021).\n\n\nWhile the general algorithmic structure is similar in all these works, the specific optimization problem in computing $w_t^*$ differs because of the way the lower bound is derived here (i.e., how the reward set and its geometry affect sample complexity). In Russo \\& Vannella (2024), the complexity depends on value gaps $\\Delta_r^\\pi(s,a)=V_r^\\pi(s)-Q_r^\\pi(s,a)$ since it is a Best Policy Identification problem, whereas our analysis for Policy Evaluation involves $\\rho_r^\\pi(s,s')=V_r^\\pi(s')-\\mathbb{E}_{s''\\sim P(s,\\pi(s))}[V_r^\\pi(s'')]$. Hence, in BPI a different analysis is needed to derive the optimization problem.\nConceptually, our work shows how this overall strategy is more general than just identifying the best policy, and can be applied to other problems (such as policy evaluation). We will highlight this distinction more clearly in the revised version of our manuscript.\n\n\n\n>  - Could this be a potential typo?: In the line 176 second column, $\\mathrm{ Alt}=\\emptyset$ is empty $\\to$ ${\\rm Alt}$ is empty?\n> - Could this be a potential typo?: In the line 2 in Algorithm 1, $\\inf \\to \\arg\\inf$?\n \n\nYes, both of these are indeed typos. We appreciate the reviewer for catching them and will correct them in the final version of the paper.", "claims_and_evidence": "It seems that the claims are supported by sufficient evidence and interpretation.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria seem reasonable for the problem and application at hand.", "theoretical_claims": "I did not check the proofs in detail but reviewed the insights behind the claims.", "experimental_designs_or_analyses": "The experimental designs and analyses seem sound and valid.", "relation_to_broader_scientific_literature": "Efficient multi-policy evaluation is useful for conducting ablations or tuning various algorithm hyperparameters, while efficient multi-reward evaluation can serve as a subroutine in MORL algorithms.", "essential_references_not_discussed": "There are no essential related works that are missing from the citations or discussion in the paper.", "other_strengths_and_weaknesses": "Strength\n\n    1. This paper provides an instance-specific sample complexity lower bound that separately considers P and r. Furthermore, based on this lower bound, the authors identify the main factor that influences the scaling of the sample complexity lower bound.\n\n    2. To address the non-convexity of the lower bound, the authors propose an appropriate convex envelope.\n\nWeakness\n\n    1. It would be helpful if the difference or relationship between this work and the main prior work, MR-NaS, were explained more clearly.", "other_comments_or_suggestions": "1. Could this be a potential typo?: \nIn the line 176 second column, Alt=\\empty is empty -> Alt is empty?\n\n2. Could this be a potential typo?:\nIn the line 2 in Algorithm 1, inf -> arginf?", "questions_for_authors": "1. In my understanding, the first bullet below Proposition 4.1 suggests that if the condition is satisfied, then Alt is empty, leading to a no-confusing scenario. Is my understanding correct, or am I missing something?\n    2. I would appreciate a clarification on how the authors' algorithm differs from the prior work MR-NaS in terms of algorithmic aspects, as I had difficulty understanding this distinction.\n    3. If there are no algorithmic differences, should I understand the contribution as providing a theoretical sample complexity bound for applying MR-NaS to the Multi-Reward Multi-Policy Evaluation problem?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies a policy evaluation problem where we wish to evaluate multiple policies under multiple rewards simultaneously, and give a sample complexity bound for simultaneous evaluation which depends on the policy and reward sets, capturing improvements over the naive baseline of independent evaluation. All the reviewers are positive about the work, and I agree with their assessment. I encourage the authors to surface the key reviewer questions and the ensuing discussions in the final revision of the paper.
Decision: Accept (poster)