betaFeedback

WorksMathematics

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models

Abstract

In multi-objective reinforcement learning, preferences may be specified only after data collection, requiring one dataset to support a continuum of reward trade-offs. We study finite discounted Markov decision processes with unknown transitions, SS states, AA actions, and mm known reward functions taking values in [0,1][0,1], given access to a generative model. The learner must provide an ε\varepsilon-optimal policy for every convex combination of these rewards without further sampling, with a guarantee that holds simultaneously over all preferences and initial states. Writing H=(1−γ)−1H=(1-γ)^{-1}, we establish the constant-confidence minimax sample complexity Θ~ ⁣(SAH3ε2min⁡{S,log⁡(em)})\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right), where the suppressed factors are logarithmic in S,A,H,ε−1S,A,H,\varepsilon^{-1} and the dependence on mm is explicit. Thus, up to these logarithmic factors, the worst-case statistical cost of supporting all preferences grows logarithmically with the number of objectives and saturates at the number of states. The upper bound uses uniform state–action sampling and empirical planning, with reward rounding in the logarithmic-objective regime. Its analysis chains optimal-value increments over covers of the reward hull. A one-sided Bellman variance bound controls signed value differences under a second transition kernel, preserving the H3ε−2H^3\varepsilon^{-2} dependence. A complementary uniform guarantee for all bounded rewards yields the state-dimension saturation. We establish lower bounds matching up to logarithmic factors through a rare-exit construction with subset rewards and action encoding. These bounds apply to adaptive simulator queries and arbitrary randomized history-dependent output policies, while the upper bounds are attained by deterministic stationary policies.

Introduction

Many sequential decision problems involve trade-offs among competing objectives. A robot may balance task completion, energy consumption, and wear, and a language model may be evaluated for both helpfulness and safety. Multi-objective reinforcement learning (MORL) represents such criteria as separate reward signals and studies how the resulting decisions depend on the user’s preferences [1, 2]. We consider linear scalarization. The learner knows mm rewards r1,…,rmr_1,\ldots,r_m, which we call the coordinate rewards; together they form the reward dictionary {r1,…,rm}\{r_1,\ldots,r_m\}. A preference vector w∈Δmw\in\Delta_m assigns them nonnegative weights summing to one and induces the scalar reward rw=∑i=1mwirir_w=\sum_{i=1}^{m}w_i r_i. The dynamics are shared across preferences, but the optimal policy can change with the weights.

Preferences are often specified only after data collection. Different users may weigh the same objectives differently, and a designer may inspect the available trade-offs before fixing a reward. Preference-conditioned value functions [3] and interpolation between models fine-tuned on different rewards [4] address this need for adaptation. The statistical question is what a single dataset can guarantee. For one fixed scalar reward, the dataset must support one near-optimal policy. For a finite list of rewards, it must support a near-optimal policy for each listed reward. Uniform MORL asks for a policy-selection rule that is simultaneously accurate for every convex combination of the coordinate rewards. This requirement covers a continuum of rewards, including preferences for which no policy that is optimal for a single coordinate reward is optimal.

We study this uniform target in finite discounted Markov decision processes (MDPs) with unknown transitions and access to a generative model, that is, a simulator that returns a next state for any queried state–action pair. Write SS and AA for the numbers of states and actions, γ∈[0,1)\gamma\in[0,1) for the discount factor, and H=(1−γ)−1H=(1-\gamma)^{-1} for the effective horizon. For one fixed bounded reward, the minimax sample complexity is Θ~(SAH3/ε2)\widetilde{\Theta}(SAH^{3}/\varepsilon^{2}) in the standard nontrivial parameter regime [5, 6, 7]. The closest discounted MORL analysis gives an O~(mSAH3/ε2)\widetilde{O}(mSAH^{3}/\varepsilon^{2}) bound for estimating scalarized QQ-functions uniformly over preferences [8]. A direct reduction through a net of preferences also gives linear dependence on mm for uniform policy learning. For a finite list of known rewards, recent online episodic results instead depend logarithmically on the list size [9]. These results motivate the following question.

How many simulator queries are needed to support a near-optimal policy for every reward in the convex hull of a known reward dictionary?

Our learner collects one dataset and then answers every preference query without further simulator calls. Its guarantee holds on a single high-probability event, simultaneously for all preferences and all initial states (§ 2.3). Specifically, our contributions are summerized as follows.

A near-minimax characterization of the objective dependence. For S≥3S \ge3, A≥2A \ge2, H≥2H \ge2, and ε≤H/4096\varepsilon\le H/4096, we show that the minimax sample complexity is

Θ~(SAH3ε2min⁡{S,log⁡(em)}),H≜(1−γ)−1.\widetilde{\Theta}\left(\frac{SAH^{3}}{\varepsilon^{2}}\min\{S,\log(em)\}\right), \qquad H \triangleq(1-\gamma)^{-1}.

where the suppressed factors are logarithmic in SS, AA, HH, ε−1\varepsilon^{-1} and the dependence on mm is retained explicitly (Theorem 3.1). Supporting every convex combination of the known rewards thus costs only a logarithmic factor in the number of objectives, and this factor never exceeds the number of states. The upper bound combines two procedures. Empirical planning for a rounded reward gives the log⁡(em)\log(em) factor (Theorem 4.1). Direct empirical planning for the requested reward gives the factor SS, since its guarantee holds for every reward in [0,1]SA[0,1]^{SA} (Theorem 5.1). The learner uses whichever procedure needs fewer samples. Each procedure samples every state–action pair equally once, and returns deterministic stationary policies without further simulator queries.

A chaining analysis for uniform policy learning. Nearby preferences have nearby optimal values, so the data needed to serve them overlap; the difficulty is to exploit this overlap without losing accuracy. The upper bound rests on finite covers of the convex reward hull. At resolution η\eta, their logarithmic size is of order η−2log⁡(SA)log⁡(em)\eta^{-2}\log(SA)\log(em). A single union bound over the cover at the final resolution ε/H\varepsilon/H would add a factor of order H2/ε2H^{2}/\varepsilon^{2}. We instead write each optimal value as a sum of increments across successively finer reward approximations, and the variance of each increment shrinks with its resolution. The central technical step is a one-sided Bellman variance bound for signed differences of optimal values, with variances taken under a second transition kernel (Lemmas 4.4 and 4.5). The bound uses only an upper bound on the one-step drift. It therefore applies even though the policy that is optimal for the target reward need not be optimal for its approximants. Increments of empirical optimal values depend on the data used to compute them. An adaptation of the absorbing-state construction of [6] supplies concentration for these increments. The variance bound then turns the row-wise concentration into bounds on policy values, in both directions of the comparison between the true and empirical models. Across levels, the growth of the cover sizes is balanced by the decay of the increment variances, which preserves both the H3H^{3} and the ε−2\varepsilon^{-2} dependence.

Lower bounds with bounded rewards and simplex preferences. We construct stationary discounted MDPs in which answering every preference query accurately identifies many unknown exit distributions. Rare exits produce the H3/ε2H^{3}/\varepsilon^{2} dependence. Subset rewards distinguish distributions over dd shared absorbing outcomes using 2d2^{d} coordinate rewards, which yields a factor of order log⁡m\log m, capped by SS. An additional action code of length O(log⁡(A+1))O(\log(A+1)) lets a simplex preference single out one pair of actions while keeping every reward in [0,1][0,1] (Theorem 6.4). The lower bounds allow adaptive simulator queries and randomized history-dependent output policies. For any fixed output policy, its normalized pre-exit action weights do not depend on the unknown exit distributions. This identity lets the learned policy-selection rule serve as a decoder. A scalar construction covers the remaining parameter regimes (Theorem C.1).

Related work

MORL targets and Pareto geometry. Surveys distinguish MORL problems by their utility functions, policy classes, and the information available about preferences [1, 2]. For linear utilities, a convex coverage set contains an optimal policy for every preference, whereas Pareto-front recovery describes the attainable nondominated value vectors. Lu et al. [10] study convexity and the relations among Pareto notions for stationary policies. Li et al. [11] exploit geometric locality to recover the exact Pareto front in a known model. Other learning targets include approachability of a target set in average-reward problems [12] and convergence to Pareto-stationary policies [13]. Our target is uniform scalarized policy accuracy in an unknown model, delivered by a policy-selection rule. § 2.3 explains how this rule acts as an implicit approximate convex coverage set.

Preference-conditioned and offline methods. Abels et al. [14] develop deep MORL methods for changing weights, and Yang et al. [3] use an envelope Bellman update to share one value representation across preferences. Zhu et al. [15] learn preference-adaptive policies from offline demonstrations, and Ramé et al. [4] interpolate models fine-tuned on different rewards. These works study representations and algorithms for preference adaptation. We instead quantify the worst-case number of transition samples needed for a simultaneous policy guarantee in a tabular discounted model.

Generative-model sample complexity. For a single reward, variance-sensitive arguments and empirical planning give sharp sample bounds [5, 6, 7]. Zhou et al. [8] extend model-based envelope value iteration to MORL and obtain a bound linear in mm for a preference-weighted QQ-function error. This value-estimation target differs from the policy loss in the true model studied here. A preference net combined with scalar empirical-planning guarantees yields a uniform policy bound with the same linear dependence on mm. Our analysis instead uses multiscale covers of the reward hull to obtain the logarithmic factor. In a related simulator setting, Vaswani et al. [16] characterize the cost of relaxed and strict feasibility in constrained MDPs. Their objective is a constrained scalar optimum, whereas ours is a family of unconstrained scalar rewards.

Online multi-objective learning. Wu et al. [17] study adversarial preferences and preference-free exploration in finite-horizon MDPs. With HepH_{\mathrm{ep}} denoting the episode length, their exploration upper bound is O~(min⁡{m,S}SAHep3/ε2)\widetilde{O}(\min\{m,S\}SAH_{\mathrm{ep}}^{3}/\varepsilon^{2}) episodes. Qiu et al. [18] develop online and preference-free algorithms for Tchebycheff and smooth Tchebycheff scalarizations. Hu and Yu [19] study near-minimax learning under predictable adversarial preferences and preference-free exploration in linear MDPs. These works differ from ours in the interaction protocol, the scalarization, or the model class. We study linear scalarization in a stationary discounted tabular model with direct state–action sampling.

Finite reward lists and reward-free exploration. Reward-free exploration collects data before any reward is specified and must support arbitrary bounded rewards afterward [20]. Task-agnostic exploration instead considers a finite collection of tasks whose rewards are unavailable during exploration [21]. Later work sharpens these guarantees [22, 23, 24]. In particular, Li et al. [23] separate reward-agnostic learning for a finite reward class from the all-rewards requirement. Ridel and Cohen [24] reduce the lower-order term that restricts the accuracy range of the reward-agnostic bound. They also prove a reward-free lower bound of order S2AHep3/ε2S^{2}AH_{\mathrm{ep}}^{3}/\varepsilon^{2} for time-inhomogeneous MDPs, which matches the reward-free upper bound up to logarithmic factors. For rewards known before exploration, Chen and Zhang [9] give an online episodic upper bound of O~(SAHep3log⁡m/ε2)\widetilde{O}(SAH_{\mathrm{ep}}^{3}\log m/\varepsilon^{2}) episodes for a list of mm rewards. Under the parameter conditions of their Corollary 1, they also prove a lower bound of order SAHep3min⁡{S,log⁡m}/ε2SAH_{\mathrm{ep}}^{3}\min\{S,\log m\}/\varepsilon^{2}. Our upper bound covers the entire convex hull of the given rewards, not only the list. Our lower bounds use a stationary discounted kernel and count individual simulator observations. Episodic bounds count trajectories, so their horizon factors cannot be compared directly with H=(1−γ)−1H=(1-\gamma)^{-1}. Theorem 5.1 supplies the complementary all-rewards guarantee under our sampling model. Table 1 collects these rates.

WorkAccessRewards servedUpper bound ×ε2\times\varepsilon^{2}Lower bound ×ε2\times\varepsilon^{2}
Zhou et al. [8]generative, discountedQQ-values for all ww with ∥w∥1≤1\lVert w\rVert_{1} \le1mSAH3mSAH^{3}single objective only
Net + planning [6, 7]generative, discountedΔm\Delta_{m}mSAH3mSAH^{3}–
Wu et al. [17]online, episodicΔm\Delta_{m}, preferences revealed latermin⁡{m,S}SAHep3\min\{m,S\}SAH_{\mathrm{ep}}^{3}min⁡{m,S}SAHep2\min\{m,S\}SAH_{\mathrm{ep}}^{2} 1
Jin et al. [20]online, episodicall rewards, revealed laterS2AHep5S^{2}AH_{\mathrm{ep}}^{5}S2AHep2S^{2}AH_{\mathrm{ep}}^{2}
Zhang et al. [21]online, episodicmm tasks, unknown during explorationSAHep5log⁡mSAH_{\mathrm{ep}}^{5}\log mSAHep2log⁡mSAH_{\mathrm{ep}}^{2}\log m
Li et al. [23]online, episodicpoly⁡(S,A,Hep)\operatorname{poly}(S,A,H_{\mathrm{ep}}) given rewards; all rewardsSAHep3SAH_{\mathrm{ep}}^{3}; S2AHep3S^{2}AH_{\mathrm{ep}}^{3} 2–
Ridel and Cohen [24]online, episodicpoly⁡(S,A,Hep)\operatorname{poly}(S,A,H_{\mathrm{ep}}) given rewards; all rewardsSAHep3SAH_{\mathrm{ep}}^{3}; S2AHep3S^{2}AH_{\mathrm{ep}}^{3}–; S2AHep3S^{2}AH_{\mathrm{ep}}^{3} 3
Chen and Zhang [9]online, episodicmm known rewardsSAHep3log⁡mSAH_{\mathrm{ep}}^{3}\log mSAHep3min⁡{S,log⁡m}SAH_{\mathrm{ep}}^{3}\min\{S,\log m\} 3
This workgenerative, discountedR\mathcal{R} (equivalently Δm\Delta_{m})SAH3min⁡{S,log⁡(em)}SAH^{3}\min\{S,\log(em)\}SAH3min⁡{S,log⁡(em)}SAH^{3}\min\{S,\log(em)\}

Table 1. Sample-complexity results for learning near-optimal policies for many rewards in tabular MDPs. Each entry is the leading term of the bound multiplied by ε2\varepsilon^{2}; constants and logarithmic factors other than those shown are omitted, and mm is the number of rewards or objectives. Online episodic rows count episodes of length HepH_{\mathrm{ep}} with per-step rewards in [0,1][0,1]. Generative rows count simulator queries in discounted MDPs with H=(1−γ)−1H=(1-\gamma)^{-1}. Rows with different access models use different units and are not directly comparable. The row “Net + planning” combines a preference net with the cited scalar guarantees. Linear-MDP results [19] and non-linear scalarizations [18] are not listed. 1Stated in [17], Theorem 4. Its proof uses [17], Appendix D, Lemma 12, which is stated for preferences on the unit ℓ1\ell_{1} sphere; under that normalization, all actions in its construction are within 2ε/m2\varepsilon/m of each other in scalarized value, so the lemma does not hold as stated. 2A lower-order term of order S4A4Hep6/εS^{4}A^{4}H_{\mathrm{ep}}^{6}/\varepsilon dominates unless ε\varepsilon is small; [24] reduces it to S2AHep4/εS^{2}AH_{\mathrm{ep}}^{4}/\varepsilon. 3Time-inhomogeneous constructions; the bound of [9] holds under the parameter conditions of its Corollary 1.

Problem formulation

Model and reward class

Let S\mathcal{S} and A\mathcal{A} be finite sets with cardinalities SS and AA. The stationary transition kernel P(⋅∣s,a)P(\cdot\mid s,a) is unknown. The discount factor γ∈[0,1)\gamma\in[0,1) is known, and H≜(1−γ)−1H \triangleq(1-\gamma)^{-1}. The learner is given the complete tables of the deterministic coordinate rewards ri:S×A→[0,1]r_i:\mathcal{S}\times\mathcal{A}\to[0,1], i∈[m]i \in[m], which form the reward dictionary {r1,…,rm}\{r_1,\ldots,r_m\}. We identify each reward with its table in [0,1]SA[0,1]^{SA}. Define

Δm≜{w∈Rm:wi≥0, ∑i=1mwi=1},rw≜∑i=1mwiri,R≜conv⁡{r1,…,rm}.\Delta_m \triangleq\left\{w \in\mathbb{R}^{m}: w_i \ge0,\ \sum_{i=1}^{m} w_i=1\right\}, \qquad r_w \triangleq\sum_{i=1}^{m} w_i r_i,\qquad\mathcal{R} \triangleq\operatorname{conv}\{r_1,\ldots,r_m\}.

We call w∈Δmw \in\Delta_m a preference and R\mathcal{R} the reward hull. Since R={rw:w∈Δm}\mathcal{R}=\{r_w:w \in\Delta_m\}, every scalarized reward lies in [0,1]SA[0,1]^{SA}, whatever the value of mm.

A policy π\pi may be randomized and history-dependent. For a reward r∈[0,1]SAr \in[0,1]^{SA}, we use unnormalized discounted values,

Vrπ(s)≜EsP,π[∑t=0∞γtr(st,at)],Vr∗(s)≜sup⁡πVrπ(s),V_{r}^{\pi}(s) \triangleq\mathbb{E}_{s}^{P,\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\right], \qquad V_{r}^{*}(s) \triangleq\sup_{\pi} V_{r}^{\pi}(s),

where EsP,π\mathbb{E}_{s}^{P,\pi} denotes expectation over trajectories with s0=ss_{0}=s, actions drawn from π\pi, and transitions drawn from PP. Both values lie in [0,H][0,H]. For a preference ww, we abbreviate Vwπ≜VrwπV_{w}^{\pi} \triangleq V_{r_{w}}^{\pi} and Vw∗≜Vrw∗V_{w}^{*} \triangleq V_{r_{w}}^{*}. Every guarantee below holds at each initial state, not only on average over a prescribed initial state distribution.

Which rewards must one dataset support?

We further distinguish different learning targets, determined by two features: the reward information available during sampling, and the query class, that is, the set of rewards for which the learner must later return a near-optimal policy. Table 2 compares four targets under a common discounted simulator model.

Learning targetReward information during samplingQuery class
Fixed rewardOne scalar reward rw0r_{w_0} is knownThe singleton {rw0}\{r_{w_0}\}
Finite known tasksThe rewards r1,…,rmr_1,\ldots,r_m are knownThe finite set {r1,…,rm}\{r_1,\ldots,r_m\}
Uniform MORL (this work)The rewards r1,…,rmr_1,\ldots,r_m are known; the query preference is notThe reward hull R\mathcal{R}
Reward-free learningNo reward is knownEvery reward in [0,1]SA[0,1]^{SA}

Table 2. Learning targets, distinguished by the reward information available during sampling and by the query class. The last three rows require simultaneous accuracy over the whole query class from one dataset. All rows assume the discounted simulator model of § 2.3; Table 1 also lists results for trajectory-based interaction.

A fixed reward versus a finite list. If w0w_{0} is fixed and known before sampling, optimizing rw0r_{w_{0}} is an ordinary single-reward learning problem, and the sampling procedure may be tailored to that reward. For the finite list {r1,…,rm}\{r_{1},\ldots,r_{m}\}, one dataset must support policies π^1,…,π^m\hat{\pi}_{1},\ldots,\hat{\pi}_{m} that are simultaneously near-optimal for their respective rewards. This joint guarantee on the listed rewards says nothing about other preferences.

A finite list versus its convex hull. Uniform MORL also covers every mixed preference, and policies that are optimal for individual coordinate rewards need not suffice. Consider a single-state problem with three actions whose reward vectors (r1(s,a),r2(s,a))(r_{1}(s,a),r_{2}(s,a)) are (1,0)(1,0), (0,1)(0,1), and (0.6,0.6)(0.6,0.6). The first two actions are optimal for r1r_{1} and r2r_{2}, respectively. The third is optimal for w=(1/2,1/2)w=(1/2,1/2), and no randomization between the first two attains its value. This distinction concerns the required outputs. By itself, it does not imply a larger minimax sample complexity for the hull than for the finite list.

A known reward hull versus arbitrary rewards. In our setting, the reward dictionary is available before sampling, although no query preference is specified. Reward-free learning must instead cover the entire bounded reward class, without this prior restriction [20]. The inclusions

{r1,…,rm}⊆R⊆[0,1]SA\{r_1,\ldots,r_m\} \subseteq\mathcal{R} \subseteq[0,1]^{SA}

order the query classes of finite-task learning, uniform MORL, and reward-free learning. Reward knowledge during sampling and the requirement to serve every query afterward are separate features of a target. Our upper-bound procedures do not use the reward values during sampling: they sample every state–action pair equally often. The known dictionary enters through the sample size, which depends on mm, and through the policy selection after sampling.

Simulator access and the simultaneous guarantee

Each generative-model query selects a state–action pair (s,a)(s,a) and returns a fresh draw from P(⋅∣s,a)P(\cdot\mid s,a), conditionally independent of earlier observations given the queried pair. Query choices may depend on the preceding transcript. The sample complexity counts these next-state observations, so we use “sample” and “simulator query” interchangeably. The reward tables are known and require no sampling.

After training, the learner returns a policy-selection rule w↦π^ww \mapsto\widehat{\pi}_w. Answering a query may use the stored data and additional computation, but makes no further simulator calls. Let D\mathcal{D} denote the training transcript together with the learner’s internal random seed, so that the selection rule is fixed once D\mathcal{D} is fixed. Define the loss of the rule at preference ww by

ED(w)≜max⁡s∈S(Vw∗(s)−Vwπ^w(s)).\mathcal{E}_{\mathcal{D}}(w) \triangleq\max_{s\in\mathcal{S}}\left(V_w^*(s)-V_w^{\widehat{\pi}_w}(s)\right).

For every transition kernel and every reward dictionary, we require the event

sup⁡w∈ΔmED(w)=sup⁡w∈Δmmax⁡s∈S(Vw∗(s)−Vwπ^w(s))≤ε(1)\sup_{w\in\Delta_m}\mathcal{E}_{\mathcal{D}}(w) = \sup_{w\in\Delta_m}\max_{s\in\mathcal{S}}\left(V_w^*(s)-V_w^{\widehat{\pi}_w}(s)\right) \leq\varepsilon \tag*{(1)}

to hold with probability at least 1−δ1-\delta:

PD(sup⁡w∈ΔmED(w)≤ε)≥1−δ.(2)\mathbb{P}_{\mathcal{D}}\left(\sup_{w\in\Delta_m}\mathcal{E}_{\mathcal{D}}(w)\leq\varepsilon\right)\geq1-\delta. \tag*{(2)}

The probability is over the training observations and the algorithmic randomness. Randomness during deployment, when present, is already averaged into the policy values. We refer to (1)–(2) as the uniform MORL guarantee.

A pointwise guarantee for the same sampling procedure would instead require

PD(ED(w)≤ε)≥1−δ\mathbb{P}_{\mathcal{D}}\left(\mathcal{E}_{\mathcal{D}}(w)\leq\varepsilon\right)\geq1-\delta

for every fixed w∈Δmw\in\Delta_m. Its exceptional datasets may depend on ww. Our requirement places the supremum over ww inside one probability event, so a successful dataset supports all preferences at once, including preferences chosen after inspecting the training output. The rule may select different policies for different preferences; no single policy is required to be optimal for every reward.

The rule acts as an implicit ε\varepsilon-approximate convex coverage set, with accuracy required at every initial state: rather than listing policies, it returns an ε\varepsilon-optimal policy for any queried preference. Exact enumeration of the Pareto front, or of all policies attaining a Pareto-optimal value, is a different output requirement. The upper bounds return deterministic stationary policies, whereas the lower bounds allow arbitrary randomized history-dependent output policies. The minimax quantity counts simulator queries only; we do not analyze the computational cost of storing or evaluating the policy-selection rule.

Notation and standard planning facts

A transition kernel KK assigns a distribution K(⋅∣s,a)K(\cdot\mid s,a) on SS to each state–action pair; the two kernels used below are the true kernel PP and the empirical kernel P^\widehat{P} of § 4. For a reward rr, let vr(K)∈RSv_r(K) \in\mathbb{R}^{S} be the optimal value vector in KK, and let Vrπ(K)V_r^\pi(K) be the value vector of a policy π\pi in KK. An omitted kernel is PP, so vr=vr(P)=Vr∗v_r = v_r(P) = V_r^* and Vrπ=Vrπ(P)V_r^\pi= V_r^\pi(P). For a deterministic stationary policy π\pi, write rπ(s)≜r(s,π(s))r_\pi(s) \triangleq r(s,\pi(s)), and let KπK_\pi be the S×SS \times S stochastic matrix whose row ss is K(⋅∣s,π(s))K(\cdot\mid s,\pi(s)). For f∈RSf \in\mathbb{R}^{S}, write

Kf(s,a)≜∑s′∈SK(s′∣s,a)f(s′),σK(f)(s,a)≜K(f2)(s,a)−(Kf(s,a))2.Kf(s,a) \triangleq\sum_{s' \in S} K(s' \mid s,a)f(s'), \qquad\sigma_K(f)(s,a) \triangleq\sqrt{K(f^2)(s,a) - (Kf(s,a))^2}.

For KπK_\pi, the same notation is indexed by states. Thus Kπf(s)=Kf(s,π(s))K_\pi f(s) = Kf(s,\pi(s)), and similarly σKπ(f)(s)=σK(f)(s,π(s))\sigma_{K_\pi}(f)(s) = \sigma_K(f)(s,\pi(s)). Vector inequalities are coordinatewise. Squares, absolute values, and products of vectors are also coordinatewise, 1\mathbf{1} is the all-ones vector, and ∥f∥∞\|f\|_\infty is the largest absolute entry of a vector or array.

Finite discounted MDPs admit deterministic stationary policies that are optimal at every state, even when the comparison class contains all randomized history-dependent policies [25 Theorem 6.2.10]. For every kernel KK, every policy π\pi, and all r,q∈[0,1]SAr,q \in[0,1]^{SA}, Bellman contraction and the discounted reward sum give

0≤vr(K)≤H1,0 \leq v_r(K) \leq H\mathbf{1},
∥vr(K)−vq(K)∥∞≤H∥r−q∥∞,∥Vrπ(K)−Vqπ(K)∥∞≤H∥r−q∥∞.(3)\begin{aligned} \|v_r(K)-v_q(K)\|_\infty&\leq H\|r-q\|_\infty,\\ \|V_r^\pi(K)-V_q^\pi(K)\|_\infty&\leq H\|r-q\|_\infty. \tag*{(3)} \end{aligned}

In particular, ∥rw−rw′∥∞≤∥w−w′∥1\|r_w-r_{w'}\|_\infty\leq\|w-w'\|_1 implies that optimal values are HH-Lipschitz in the preference with respect to ∥⋅∥1\|\cdot\|_1, although an optimal policy need not vary continuously with the preference.

Main result: Near Minimax Sample Complexity

Let N∗(S,A,m,H,ε)N^*(S,A,m,H,\varepsilon) be the smallest worst-case maximum number of simulator queries sufficient for (1) with success probability at least 3/43/4, uniformly over all known reward functions r1,…,rm:S×A→[0,1]r_1,\ldots,r_m:S \times A \to[0,1] and all transition kernels. Computational cost is not included in this definition. Set

κ(S,m)≜min⁡{S,log⁡(em)},L≜log⁡eSAH2ε,LA≜1+log⁡log⁡(eeA).\kappa(S,m) \triangleq\min\{S,\log(em)\}, \qquad L \triangleq\log\frac{eSAH^2}{\varepsilon}, \qquad L_A \triangleq1+\log\log(e^e A).

Natural logarithms are used unless a base is displayed.

Theorem 3.1 (Joint near-minimax characterization). There are universal constants c,C>0c,C>0 such that, for S≥3S \geq3, A≥2A \geq2, m≥1m \geq1, H≥2H \geq2, and 0<ε≤H/40960<\varepsilon\leq H/4096,

cSAH3κ(S,m)ε2LA≤N∗(S,A,m,H,ε)≤CSAH3ε2κ(S,m)L3.(4)c\frac{SAH^3\kappa(S,m)}{\varepsilon^2 L_A} \leq N^*(S,A,m,H,\varepsilon) \leq C\frac{SAH^3}{\varepsilon^2}\kappa(S,m)L^3. \tag*{(4)}

If mm is at least a sufficiently large constant times log⁡(A+1)\log(A+1), the denominator LAL_A can be removed from the lower bound, after adjusting the universal constant. The upper bound has a high-probability version for every δ∈(0,1)\delta\in(0,1), with logarithmic dependence on δ−1\delta^{-1} specified in Theorems 4.1 and 5.1.

The proof of this theorem is assembled in § 7 after the explicit upper and lower bounds. The logarithmic factors in (4) depend on SS, AA, HH, ε−1\varepsilon^{-1}, not on an unspecified polynomial in mm. In particular, if a tilde hides only logarithms in these other parameters, the joint rate is

N∗=Θ~(SAH3ε2min⁡{S,log⁡(em)}).N^* = \widetilde{\Theta}\left(\frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\}\right).

This statement retains the objective dependence explicitly. When mm is exponentially large in SS, the logarithmic objective cost can itself be of order SS. For fixed mm, the bound has the same polynomial dependence as single-objective generative-model planning. The result is minimax optimal up to logarithmic factors, not a constant-factor characterization of every logarithm or of the full confidence dependence.

Algorithm. The learner samples every state–action pair equally and forms P^\widehat{P}. In the reward-hull regime, it rounds a query rwr_w to a finite reward cover and returns an optimal policy for the rounded reward in P^\widehat{P}. Fixing an order on the cover and on the actions makes both selections deterministic. In the state-saturation regime, it plans directly for rwr_w. The two sufficient sample counts are known before sampling, so the learner chooses the smaller one.

Proof structure. Section 4 proves the logarithmic-objective upper bound in four steps: construct reward covers, concentrate their value increments, control these increments through a one-sided variance estimate, and compare true and empirical policies. Section 5 states the complementary bound for all bounded rewards. Section 6 proves the action-code lower bound, using a common occupancy identity and an adaptive information bound. Section 7 combines the parameter regimes. Supporting upper and lower arguments appear in the appendices.

At reward scale η\eta, the cover entropy is of order η−2log⁡(4SA)log⁡(em)\eta^{-2}\log(4SA)\log(em). Its square root contributes a factor η−1\eta^{-1} to Bernstein’s inequality. The variance comparison supplies a matching factor H3/2/ηH^{3/2}/\eta, together with a term depending on the comparison error. Lemma 4.5 absorbs that remaining term and sums over the logarithmic number of scales.

The reward-hull upper bound

Let H=(1−γ)−1H=(1-\gamma)^{-1}, and let R=conv⁡{r1,…,rm}⊂[0,1]SA\mathcal{R}=\operatorname{conv}\{r_1,\ldots,r_m\}\subset[0,1]^{SA}. Rewards are known. All samples below concern transitions. Fix ε∈(0,H]\varepsilon\in(0,H] and δ∈(0,1)\delta\in(0,1), and define

J≜⌈log⁡216Hε⌉,ηj≜2−j(0≤j≤J),h≜ε1000HJ,G≜{min⁡{ℓh,H}:0≤ℓ≤⌈H/h⌉},J\triangleq\left\lceil\log_2\frac{16H}{\varepsilon}\right\rceil,\qquad\eta_j\triangleq2^{-j}\quad(0\le j\le J),\qquad h\triangleq\frac{\varepsilon}{1000HJ},\qquad\mathcal{G}\triangleq\{\min\{\ell h,H\}:0\le\ell\le\lceil H/h\rceil\},

and

Λ≜log⁡20SAJ∣G∣2δ+3log⁡(4SA)log⁡(em).\Lambda\triangleq\log\frac{20SAJ|\mathcal{G}|^2}{\delta}+3\log(4SA)\log(em).

Then ε/(32H)<ηJ≤ε/(16H)\varepsilon/(32H)<\eta_J\le\varepsilon/(16H), J≥4J\ge4, and ∣G∣≤1000H2J/ε+2|\mathcal{G}|\le1000H^2J/\varepsilon+2.

Theorem 4.1 (Reward-hull chaining upper bound). Draw nn independent next states at each state–action pair, form the empirical kernel P^\widehat{P}, and suppose

n≥220H3ΛJ2ε2.n\ge\frac{2^{20}H^3\Lambda J^2}{\varepsilon^2}.

Then there is a finite ηJ\eta_J-cover NJ⊂R\mathcal{N}_J\subset\mathcal{R} in the supremum norm, depending only on the known rewards, with the following property. With probability at least 1−δ1-\delta, simultaneously for every r∈Rr\in\mathcal{R}, every q∈NJq\in\mathcal{N}_J with ∥r−q∥∞≤ηJ\lVert r-q\rVert_\infty\le\eta_J, and every deterministic stationary policy π^\widehat{\pi} that is optimal for reward qq in the empirical kernel P^\widehat{P} (ties broken arbitrarily),

Vr∗(s)−Vrπ^(s)≤εfor all s∈S.V_r^*(s)-V_r^{\widehat{\pi}}(s)\le\varepsilon\qquad\text{for all }s\in\mathcal{S}.

In particular, the algorithm that chooses any such qq and returns any such π^\widehat{\pi} is simultaneously ε\varepsilon-optimal for all r∈Rr\in\mathcal{R}. The total sample complexity is at most

SA⌈220H3ΛJ2ε2⌉.SA\left\lceil\frac{2^{20}H^3\Lambda J^2}{\varepsilon^2}\right\rceil.

In particular, the dependence on the number of reward coordinates is logarithmic, and the polynomial dependence is SAH3ε−2SAH^3\varepsilon^{-2}.

Finite reward covers

For j≥1j\ge1, define

kj≜⌈log⁡(4SA)2ηj2⌉,Nj≜{1kj∑ℓ=1kjriℓ:(i1,…,ikj)∈[m]kj}⊂[0,1]SA,k_j\triangleq\left\lceil\frac{\log(4SA)}{2\eta_j^2}\right\rceil,\qquad\mathcal{N}_j\triangleq\left\{\frac{1}{k_j}\sum_{\ell=1}^{k_j}r_{i_\ell}:(i_1,\ldots,i_{k_j})\in[m]^{k_j}\right\}\subset[0,1]^{SA},

and set N0≜{0}\mathcal{N}_0\triangleq\{0\} and Mj≜∣Nj∣M_j\triangleq|\mathcal{N}_j|. Clearly Mj≤mkjM_j\le m^{k_j}. We then claim that Nj\mathcal{N}_j is an ηj\eta_j-cover of R\mathcal{R}. To verify this, consider a fixed reward r=∑iwiri∈Rr=\sum_i w_i r_i\in\mathcal{R}. We can sample kjk_j independent coordinate rewards with index distribution ww. At each of the SASA state-action entries, their average differs from its mean by more than ηj\eta_j with probability at most 2e−2kjηj22e^{-2k_j\eta_j^2}. Specifically, Hoeffding’s inequality [26 Theorem 2] applied to a kjk_j-sample average with index distribution ww implies

P(∥kj−1∑ℓ=1kjrIℓ−rw∥∞>ηj)≤2SAe−2kjηj2,\mathbb{P}\left(\left\Vert k_j^{-1}\sum_{\ell=1}^{k_j}r_{I_\ell}-r_w\right\Vert_\infty>\eta_j\right)\le2SAe^{-2k_j\eta_j^2},

and a union bound implies total probability at most 1/21/2. Therefore, at least one deterministic average in Nj\mathcal{N}_j is consequently within ηj\eta_j of rr in the supremum norm.

Now for every target r∈NJr \in\mathcal{N}_J, fix an approximant qj(r)∈Njq_j(r) \in\mathcal{N}_j with ∥r−qj(r)∥∞≤ηj\|r-q_j(r)\|_\infty\le\eta_j for 1≤j<J1 \le j < J; set q0(r)=0q_0(r)=0 and qJ(r)=rq_J(r)=r. These choices depend only on the rewards. For every j≥1j \ge1, we claim

∥qj(r)−qj−1(r)∥∞≤3ηj.\|q_j(r)-q_{j-1}(r)\|_\infty\le3\eta_j.

To prove it, note that for j=1j=1, the bound holds as ∥q1(r)∥∞≤1≤3/2\|q_1(r)\|_\infty\le1 \le3/2; for j≥2j \ge2, it uses the fact that ηj−1=2ηj\eta_{j-1}=2\eta_j and triangle inequality. Therefore, these approximants form a subset of all adjacent pairs (q,q′)∈Nj×Nj−1(q,q') \in\mathcal{N}_j \times\mathcal{N}_{j-1} with ∥q−q′∥∞≤3ηj\|q-q'\|_\infty\le3\eta_j (we will use them later in § 4.2). There are at most MjMj−1M_jM_{j-1} of them, and the union bound at level jj runs over these pairs. Define

Lj≜log⁡20SAJMjMj−1∣G∣2δ,tj≜Lj/n.L_j \triangleq\log\frac{20SAJM_jM_{j-1}|\mathcal{G}|^2}{\delta}, \qquad t_j \triangleq L_j/n.

For j≥2j \ge2, we have log⁡(MjMj−1)≤(kj+kj−1)log⁡m\log(M_jM_{j-1}) \le(k_j+k_{j-1})\log m, with kj≤log⁡(4SA)/(2ηj2)+1k_j \le\log(4SA)/(2\eta_j^2)+1 and kj−1≤log⁡(4SA)/(8ηj2)+1k_{j-1} \le\log(4SA)/(8\eta_j^2)+1. Because ηj≤1/2\eta_j \le1/2 and log⁡(4SA)>1\log(4SA)>1, the additive constant 22 is at most 12ηj2log⁡(4SA)\frac{1}{2\eta_j^2}\log(4SA). Hence

log⁡(MjMj−1)≤3ηj−2log⁡(4SA)log⁡(em).\log(M_jM_{j-1}) \le3\eta_j^{-2}\log(4SA)\log(em).

The same bound holds for j=1j=1 because M0=1M_0=1. Since ηj−2≥1\eta_j^{-2}\ge1 and log⁡(20SAJ∣G∣2/δ)≥0\log(20SAJ|\mathcal{G}|^2/\delta)\ge0, it follows that

Lj≤Λ/ηj2.(5)L_j \le\Lambda/\eta_j^2. \tag*{(5)}

The sample-size condition implies tj≤Λ/(nηj2)<1t_j \le\Lambda/(n\eta_j^2)<1 for every jj.

Uniform concentration of the value increments

We first present the concentration result used in both upper bounds. The following inequalities are standard in literature.

Lemma 4.2 (Bernstein bounds in two variance conventions). Let X1,…,XnX_1,\ldots,X_n be i.i.d. copies of XX supported in an interval of length BB, with n≥3n\ge3. Write μ=EX\mu=\mathbb{E}X, σ2=Var⁡(X)\sigma^2=\operatorname{Var}(X), μ^=n−1∑iXi\widehat{\mu}=n^{-1}\sum_i X_i, and σ^2=n−1∑i(Xi−μ^)2\widehat{\sigma}^2=n^{-1}\sum_i(X_i-\widehat{\mu})^2. For L>0L>0, the following bounds have failure probabilities at most 2e−L2e^{-L} and 4e−L4e^{-L}, respectively:

∣μ^−μ∣≤2σ2L/n+2BL/(3n),(6)|\widehat{\mu}-\mu| \le\sqrt{2\sigma^2L/n}+2BL/(3n), \tag*{(6)}
∣μ^−μ∣≤2L/nσ^+4BL/n.(7)|\widehat{\mu}-\mu| \le2\sqrt{L/n}\widehat{\sigma}+4BL/n. \tag*{(7)}

They hold jointly with failure probability at most 6e−L6e^{-L}.

The first inequality is Bernstein’s inequality. The second follows from Maurer and Pontil [27 Theorem 4], applied to both tails after translating and rescaling the interval. Their unbiased variance is nσ^2/(n−1)n\widehat{\sigma}^2/(n-1); These bounds require n≥3n\ge3 and 7n/[3(n−1)]≤47n/[3(n-1)]\le4, and every sample-size condition below ensures them.

Lemma 4.3 (Simultaneous concentration of adjacent value increments). With probability at least 1−δ1-\delta, the following inequalities hold simultaneously for all jj, all adjacent reward pairs (q,q′)∈Nj×Nj−1(q,q')\in\mathcal{N}_j\times\mathcal{N}_{j-1} satisfying ∥q−q′∥∞≤3ηj\|q-q'\|_\infty\le3\eta_j, and all state–action pairs:

∣(P^−P)(vq(P)−vq′(P))∣≤2tj σP^(vq(P)−vq′(P))+32Hηjtj+10h,(8)|(\widehat{P}-P)(v_q(P)-v_{q'}(P))| \le2\sqrt{t_j}\,\sigma_{\widehat{P}}(v_q(P)-v_{q'}(P))+32H\eta_jt_j+10h, \tag*{(8)}
∣(P^−P)(vq(P^)−vq′(P^))∣≤2tj σP(vq(P^)−vq′(P^))+32Hηjtj+10h.(9)|(\widehat{P}-P)(v_q(\widehat{P})-v_{q'}(\widehat{P}))| \le2\sqrt{t_j}\,\sigma_P(v_q(\widehat{P})-v_{q'}(\widehat{P}))+32H\eta_jt_j+10h. \tag*{(9)}

Both inequalities are coordinatewise.

Proof. We will apply an absorbing-state construction to remove the dependence of the empirical-value increment on the sampled row.

For (8), first note that the function Δ≜vq(P)−vq′(P)\Delta\triangleq v_q(P)-v_{q'}(P) is deterministic and satisfies ∥Δ∥∞≤3Hηj\|\Delta\|_\infty\le3H\eta_j. Let Y1,…,YnY_1,\ldots,Y_n be the samples at (s,a)(s,a), and apply Lemma 4.2, with B=6HηjB=6H\eta_j and L=LjL=L_j; Xi≜Δ(Yi)+3Hηj∈[0,6Hηj]X_i\triangleq\Delta(Y_i)+3H\eta_j\in[0,6H\eta_j]. Since P(⋅∣s,a)P(\cdot\mid s,a) and P^(⋅∣s,a)\widehat{P}(\cdot\mid s,a) are probability vectors, the shift changes neither (P^−P)Δ(\widehat{P}-P)\Delta nor the standard deviations, and the empirical standard deviation of the XiX_i is σP^(Δ)\sigma_{\widehat{P}}(\Delta). Inequality (7) therefore implies

∣(P^−P)Δ∣≤2tjσP^(Δ)+24Hηjtj|(\widehat{P}-P)\Delta| \le2\sqrt{t_j}\sigma_{\widehat{P}}(\Delta)+24H\eta_jt_j

with failure probability at most 4e−Lj4e^{-L_j} for each row and pair.

For (9), we remove the dependence on the row being sampled, using the absorbing-MDP construction of [6 Lemmas 8–9]. Fix a state ss. We modify the empirical MDP by making ss absorbing and giving all its actions reward (1−γ)u(1-\gamma)u, where u∈[0,H]u \in[0,H]. Other states retain reward qq. Write vs,q,uv_{s,q,u} for its optimal value. This vector is independent of all empirical transition rows at state ss. It equals uu at state ss. It also satisfies

vs,q,q,vq(P^)(s)=vq(P^),(10)v_{s,q,q,v_q(\widehat{P})(s)} = v_q(\widehat{P}), \tag*{(10)}
∥vs,q,u−vs,q′,u′∥∞≤max⁡{∣u−u′∣,H∥q−q′∥∞}.(11)\lVert v_{s,q,u}-v_{s,q',u'}\rVert_\infty\le\max\{|u-u'|,H\lVert q-q'\rVert_\infty\}. \tag*{(11)}

The first identity is [6 Lemma 8]. The second extends their boundary Lipschitz bound to two different rewards: let aa be the norm on its left. At ss, the difference is ∣u−u′∣|u-u'|; outside ss, the Bellman inequality bounds it by ∥q−q′∥∞+γa\lVert q-q'\rVert_\infty+\gamma a. Hence a≤max⁡{∣u−u′∣,∥q−q′∥∞+γa}a \le\max\{|u-u'|,\lVert q-q'\rVert_\infty+\gamma a\}, which implies the displayed bound.

Now consider u,u′∈Gu,u' \in\mathcal{G} with ∣u−u′∣≤3Hηj+2h|u-u'| \le3H\eta_j+2h and define the proxy difference Δ0≜vs,q,u−vs,q′,u′\Delta_0 \triangleq v_{s,q,u}-v_{s,q',u'}. Since h≤HηJ/2≤Hηj/2h \le H\eta_J/2 \le H\eta_j/2, (11) implies ∥Δ0∥∞≤4Hηj\lVert\Delta_0\rVert_\infty\le4H\eta_j. Conditional on all data outside state ss, this is a fixed function independent of the nn samples at (s,a)(s,a). Bernstein’s inequality consequently implies

∣(P^−P)Δ0∣(s,a)≤2tj σP(Δ0)(s,a)+8Hηjtj|(\widehat{P}-P)\Delta_0|(s,a) \le\sqrt{2t_j}\,\sigma_P(\Delta_0)(s,a)+8H\eta_jt_j

with conditional, and hence unconditional, failure probability at most 2e−Lj2e^{-L_j}. We note the numerical constant 8 is conservative: the range length is at most 8Hηj8H\eta_j.

Then we choose grid points u,u′u,u' within hh of vq(P^)(s)v_q(\widehat{P})(s) and vq′(P^)(s)v_{q'}(\widehat{P})(s), respectively. The two exact boundary values differ by at most 3Hηj3H\eta_j, so this grid pair is among those considered. Equations (10)–(11) give

∥Δ−Δ0∥∞≤2h,where Δ≜vq(P^)−vq′(P^).\lVert\Delta-\Delta_0\rVert_\infty\le2h,\qquad\text{where }\Delta\triangleq v_q(\widehat{P})-v_{q'}(\widehat{P}).

Therefore ∣(P^−P)(Δ−Δ0)∣≤4h|(\widehat{P}-P)(\Delta-\Delta_0)| \le4h, and σP(Δ0)≤σP(Δ)+2h\sigma_P(\Delta_0) \le\sigma_P(\Delta)+2h by the triangle inequality in centered L2(P)L_2(P). Since tj≤1t_j \le1, we have

∣(P^−P)Δ∣≤2tj σP(Δ)+8Hηjtj+(4+22)h,|(\widehat{P}-P)\Delta| \le\sqrt{2t_j}\,\sigma_P(\Delta)+8H\eta_jt_j+(4+2\sqrt{2})h,

which implies (9). A union bound over at most SAMjMj−1SAM_jM_{j-1} true-value events, each failing with probability at most 4e−Lj4e^{-L_j}, and at most SAMjMj−1∣G∣2SAM_jM_{j-1}|\mathcal{G}|^2 empirical-proxy events at level jj, each failing with probability at most 2e−Lj2e^{-L_j}, has total failure probability at most

∑j=1J6SAMjMj−1∣G∣2e−Lj=3δ10<δ.\sum_{j=1}^{J}6SAM_jM_{j-1}|\mathcal{G}|^2e^{-L_j}=\frac{3\delta}{10}<\delta.

The union covers every grid pair, so it covers the data-dependent pair chosen above.

A one-sided variance bound for the comparison

In single-objective RL, [5] utilize the total-variance method to control a value function through its Bellman equation; But here, our objective contains signed differences of optimal values, evaluated under a second kernel. We therefore need the following form.

Lemma 4.4. Let KK be an S×SS \times S stochastic matrix, let RK≜(I−γK)−1R_K \triangleq(I-\gamma K)^{-1}, and for u∈RSu \in\mathbb{R}^S define

σK(u)(s)≜K(u2)(s)−(Ku(s))2.\sigma_K(u)(s) \triangleq\sqrt{K(u^2)(s)-(Ku(s))^2}.

Let c≥0c \ge0 and let β∈RS\beta\in\mathbb{R}^S satisfy β≥0\beta\ge0. If 0≤u≤c10 \le u \le c\mathbf{1} and b≜u−γKu≤βb \triangleq u-\gamma Ku \le\beta, then

γ2RKσK(u)2≤2cRKβ−u2andγ∥RKσK(u)∥∞≤2cH∥RKβ∥∞.\gamma^2R_K\sigma_K(u)^2 \le2cR_K\beta-u^2 \qquad\text{and}\qquad \gamma\lVert R_K\sigma_K(u)\rVert_\infty\le\sqrt{2cH\lVert R_K\beta\rVert_\infty}.

In particular, if v∈[0,H]Sv \in[0,H]^S and v−γKv≤21v-\gamma Kv \le2\mathbf{1}, then γ∥RKσK(v)∥∞≤2H3/2\gamma\lVert R_K\sigma_K(v)\rVert_\infty\le2H^{3/2}.

Proof. Note that RKR_K has nonnegative entries [25] and satisfies RK1=H1R_K\mathbf{1}=H\mathbf{1}. In particular, it preserves coordinatewise inequalities.

The relation γKu=u−b\gamma Ku=u-b implies γ2(Ku)2=(u−b)2=u2−2ub+b2\gamma^2(Ku)^2=(u-b)^2=u^2-2ub+b^2. Hence

γ2σK(u)2=γ2K(u2)−u2+2ub−b2≤γK(u2)−u2+2cβ.\gamma^2\sigma_K(u)^2=\gamma^2K(u^2)-u^2+2ub-b^2\le\gamma K(u^2)-u^2+2c\beta.

Specifically, it is from bounding three terms. First, γ2K(u2)≤γK(u2)\gamma^2 K(u^2) \le\gamma K(u^2), because K(u2)≥0K(u^2) \ge0 and γ2≤γ\gamma^2 \le\gamma. Second, −b2≤0-b^2 \le0. Third, 2ub≤2uβ≤2cβ2ub \le2u\beta\le2c\beta: multiplying b≤βb \le\beta by u≥0u \ge0 preserves its direction, and u≤c1u \le c1 together with β≥0\beta\ge0 implies the inequality.

Apply RKR_K and use RK(γK−I)=−IR_K(\gamma K-I)=-I:

γ2RKσK(u)2≤−u2+2cRKβ≤2cRKβ.\gamma^2R_K\sigma_K(u)^2\le-u^2+2cR_K\beta\le2cR_K\beta.

This proves the first claim. For each state ss, the weights RK(s,y)R_K(s,y) are nonnegative and sum to HH, so the Cauchy–Schwarz inequality implies

(RKσK(u)(s))2≤(∑yRK(s,y))(∑yRK(s,y)σK(u)(y)2)=H(RKσK(u)2)(s).\left(R_K\sigma_K(u)(s)\right)^2\le\left(\sum_y R_K(s,y)\right)\left(\sum_y R_K(s,y)\sigma_K(u)(y)^2\right)=H\left(R_K\sigma_K(u)^2\right)(s).

Multiplying by γ2\gamma^2 and using the first claim implies γ2(RKσK(u)(s))2≤2cH(RKβ)(s)≤2cH∥RKβ∥∞\gamma^2\left(R_K\sigma_K(u)(s)\right)^2\le2cH(R_K\beta)(s)\le2cH\lVert R_K\beta\rVert_\infty. Both γ\gamma and RKσK(u)(s)R_K\sigma_K(u)(s) are nonnegative, so taking square roots and the maximum over ss proves the second claim.

For the last claim, take u=vu=v, c=Hc=H, and β=21\beta=2\mathbf{1}. Then RKβ=2H1R_K\beta=2H\mathbf{1} and 2H⋅H⋅2H=2H3/2\sqrt{2H\cdot H\cdot2H}=2H^{3/2} and it completes the proof.

Chaining the comparison error

The following lemma will be applied twice, in opposite directions. All target and approximating rewards are the bounded arrays in the reward chain defined above, including the zero reward at level zero. Let K0K^0 and K1K^1 be two transition kernels. Denote the optimal values of the base kernel K0K^0 vq0≜vq(K0)v_q^0\triangleq v_q(K^0). For each target r∈NJr\in\mathcal{N}_J, one can choose a deterministic stationary policy πr\pi_r that is optimal for rr in K0K^0, and define

Rr≜(I−γKπr1)−1,fr,j≜vr−vqj(r),dr,j≜vqj(r)−vqj−1(r).R_r\triangleq(I-\gamma K^1_{\pi_r})^{-1},\qquad f_{r,j}\triangleq v_r-v_{q_j}(r),\qquad d_{r,j}\triangleq v_{q_j}(r)-v_{q_{j-1}}(r).

Then we have fr,J=0f_{r,J}=0, fr,0=vrf_{r,0}=v_r, and fr,j=∑k=j+1Jdr,kf_{r,j}=\sum_{k=j+1}^{J}d_{r,k}. Define the finite nonnegative quantity

E≜max⁡r∈NJ, 0≤j≤J∥γRr(Kπr1−Kπr0)fr,j∥∞.E\triangleq\max_{r\in\mathcal{N}_J,\ 0\le j\le J}\left\lVert\gamma R_r\left(K^1_{\pi_r}-K^0_{\pi_r}\right)f_{r,j}\right\rVert_\infty.

Lemma 4.5. Let tj=Lj/nt_j=L_j/n be as in Section 4, so that tj≤Λ/(nηj2)t_j\le\Lambda/(n\eta_j^2) by (5). Suppose that, for all targets r∈NJr\in\mathcal{N}_J, all levels 1≤j≤J1\le j\le J, and all state–action pairs,

∣(K1−K0)dr,j∣≤2tjσK1(dr,j)+32Hηjtj+10h.(12)\left|(K^1-K^0)d_{r,j}\right|\le2\sqrt{t_j}\sigma_{K^1}(d_{r,j})+32H\eta_jt_j+10h. \tag*{(12)}

Then

E≤36JH3/2Λ/n+1728H2ΛnηJ+20JHh,(13)E\le36JH^{3/2}\sqrt{\Lambda/n}+\frac{1728H^2\Lambda}{n\eta_J}+20JHh, \tag*{(13)}

and ∥vr(K0)−Vπr(K1)∥∞≤E\lVert v_r(K^0)-V_{\pi_r}(K^1)\rVert_\infty\le E for every r∈NJr\in\mathcal{N}_J.

Proof. We first bound the resolved variance of each tail fr,jf_{r,j}. We then sum the increment concentration bounds and absorb the resulting term proportional to E\sqrt{E}.

The Bellman inequality controls every tail. Fix a target and level and abbreviate f=fr,jf=f_{r,j} and η=ηj\eta=\eta_j. The reward Lipschitz property implies ∣f∣≤Hη1|f|\le H\eta\mathbf{1}. Optimality of πr\pi_r for rr and Bellman optimality of vqj(r)v_{q_j}(r) imply that

vr=rπr+γKπr0vr,vqj(r)≥qj(r)πr+γKπr0vqj(r).v_r=r_{\pi_r}+\gamma K^0_{\pi_r}v_r,\qquad v_{q_j}(r)\ge q_j(r)_{\pi_r}+\gamma K^0_{\pi_r}v_{q_j}(r).

Subtracting shows f−γKπr0f≤η1f-\gamma K^0_{\pi_r}f\le\eta\mathbf{1}. Moreover, note that the shift ϕ=f+Hη1\phi=f+H\eta\mathbf{1} satisfies 0≤ϕ≤2Hη10\le\phi\le2H\eta\mathbf{1} and, because (1−γ)H=1(1-\gamma)H=1, we have

ϕ−γKπr1ϕ=η1+(f−γKπr0f)−γ(Kπr1−Kπr0)f≤2η1+γ∣(Kπr1−Kπr0)f∣.\phi-\gamma K^1_{\pi_r}\phi=\eta\mathbf{1}+(f-\gamma K^0_{\pi_r}f)-\gamma(K^1_{\pi_r}-K^0_{\pi_r})f\le2\eta\mathbf{1}+\gamma\left|(K^1_{\pi_r}-K^0_{\pi_r})f\right|.

Apply Lemma 4.4 with K=Kπr1K=K^1_{\pi_r}, u=ϕu=\phi, c=2Hηc=2H\eta, and β=2η1+γ∣(Kπr1−Kπr0)f∣\beta=2\eta\mathbf{1}+\gamma\left|(K^1_{\pi_r}-K^0_{\pi_r})f\right|. Since KK is stochastic, σK(ϕ)=σK(f)\sigma_K(\phi)=\sigma_K(f). Since Rr1=H1R_r\mathbf{1}=H\mathbf{1}, the definition of EE implies Rrβ≤(2Hη+E)1R_r\beta\le(2H\eta+E)\mathbf{1}. Therefore we have that

γ∥RrσK(fr,j)∥∞≤8H3ηj2+4H2ηjE≤3H3/2ηj+2HηjE.(14)\gamma\lVert R_r\sigma_K(f_{r,j})\rVert_\infty\le\sqrt{8H^3\eta_j^2+4H^2\eta_jE}\le3H^{3/2}\eta_j+2H\sqrt{\eta_jE}. \tag*{(14)}

This argument also holds at j=0j=0, where q0=0q_0=0, vq0=0v_{q_0}=0, and ∥r∥∞≤1=η0\lVert r\rVert_\infty\le1=\eta_0, and trivially at j=Jj=J, where fr,J=0f_{r,J}=0.

Increment bounds close the comparison. Since dr,j=fr,j−1−fr,jd_{r,j}=f_{r,j-1}-f_{r,j}, the centered-L2L_2 triangle inequality and ηj−1=2ηj\eta_{j-1}=2\eta_j imply that

γ∥RrσK(dr,j)∥∞≤9H3/2ηj+5HnE.\gamma\lVert R_r\sigma_K(d_{r,j})\rVert_\infty\le9H^{3/2}\eta_j+5H\sqrt{n}E.

Use the tail representation of each fr,jf_{r,j}, the nonnegativity of RrR_r, and (12) at the rows (s,πr(s))(s,\pi_r(s)). These rows give ∣(Kπr1−Kπr0)dr,j∣≤2tjσK(dr,j)+(32Hηjtj+10h)1\lvert(K^1_{\pi_r}-K^0_{\pi_r})d_{r,j}\rvert\le2\sqrt{t_j}\sigma_K(d_{r,j})+(32H\eta_jt_j+10h)\mathbf{1}. Enlarge every tail sum to the full sum; all summands are nonnegative. After taking the maximum defining EE, we obtain

E≤∑j=1J[18H3/2ηjtj+10HηjEtj+32H2ηjtj+10Hh](15)E\le\sum_{j=1}^{J}\left[18H^{3/2}\eta_j\sqrt{t_j}+10H\sqrt{\eta_jE}\sqrt{t_j}+32H^2\eta_jt_j+10Hh\right] \tag*{(15)}
≤18JH3/2Λ/n+10HΛE/n∑j=1Jηj−1/2+32H2Λn∑j=1Jηj−1+10JHh(16)\le18JH^{3/2}\sqrt{\Lambda/n}+10H\sqrt{\Lambda E/n}\sum_{j=1}^{J}\eta_j^{-1/2}+\frac{32H^2\Lambda}{n}\sum_{j=1}^{J}\eta_j^{-1}+10JHh \tag*{(16)}
≤18JH3/2Λ/n+40HΛEnηJ+64H2ΛnηJ+10JHh.(17)\le18JH^{3/2}\sqrt{\Lambda/n}+40H\sqrt{\frac{\Lambda E}{n\eta_J}}+\frac{64H^2\Lambda}{n\eta_J}+10JHh. \tag*{(17)}

The second inequality uses (5); the third uses the geometric-sum bounds ∑jηj−1/2≤4ηJ−1/2\sum_j\eta_j^{-1/2}\le4\eta_J^{-1/2} and ∑jηj−1≤2ηJ−1\sum_j\eta_j^{-1}\le2\eta_J^{-1}. Finally, Young’s inequality implies

40HΛEnηJ≤E2+800H2ΛnηJ.40H\sqrt{\frac{\Lambda E}{n\eta_J}}\le\frac{E}{2}+\frac{800H^2\Lambda}{n\eta_J}.

Plugging it in (15) then proves (13).

The comparison controls policy evaluation. For the last claim, write V=Vrπr(K1)V=V_r^{\pi_r}(K^1). Subtracting V=rπr+γKπr1VV=r_{\pi_r}+\gamma K^1_{\pi_r}V from vr=rπr+γKπr0vrv_r=r_{\pi_r}+\gamma K^0_{\pi_r}v_r implies (I−γKπr1)(vr−V)=−γ(Kπr1−Kπr0)fr,0(I-\gamma K^1_{\pi_r})(v_r-V)=-\gamma(K^1_{\pi_r}-K^0_{\pi_r})f_{r,0}, thus we have that

vr−V=−γRr(Kπr1−Kπr0)fr,0.v_r-V=-\gamma R_r(K^1_{\pi_r}-K^0_{\pi_r})f_{r,0}.

Since RrR_r has nonnegative entries, ∣Rrx∣≤Rr∣x∣\lvert R_rx\rvert\le R_r\lvert x\rvert for every vector xx. Hence ∥vr−V∥∞\lVert v_r-V\rVert_\infty is at most the level-zero term in the definition of EE. □

Policy comparison and completion of the proof

Now we are ready to prove Theorem 4.1. We will consider the event of Lemma 4.3.

We will apply Lemma 4.5 first with K0=P^K^0=\widehat{P} and K1=PK^1=P (inequality (9) verifies its hypothesis hence we can apply it). Let π^r\widehat{\pi}_r be any empirical optimal deterministic stationary policy, and note that since (9) concerns values only, the conclusion holds simultaneously for every such choice. The exact policy-evaluation identity is

vr(P^)−Vrπ^r(P)=γ(I−γPπ^r)−1(P^π^r−Pπ^r)vr(P^),v_r(\widehat{P})-V_r^{\widehat{\pi}_r}(P)=\gamma(I-\gamma P_{\widehat{\pi}_r})^{-1}(\widehat{P}_{\widehat{\pi}_r}-P_{\widehat{\pi}_r})v_r(\widehat{P}),

and the last claim of Lemma 4.5 bounds its norm by EE. Hence ∥vr(P^)−Vrπ^r(P)∥∞≤Γn\lVert v_r(\widehat{P})-V_r^{\widehat{\pi}_r}(P)\rVert_\infty\le\Gamma_n, where

Γn≜36JH3/2Λ/n+1728H2ΛnηJ+20JHh.\Gamma_n\triangleq36JH^{3/2}\sqrt{\Lambda/n}+\frac{1728H^2\Lambda}{n\eta_J}+20JHh.

Apply the same lemma with K0=PK^0=P and K1=P^K^1=\widehat{P}. Inequality (8) verifies its hypothesis. For a true optimal policy πr∗\pi_r^*, the lemma implies ∥vr(P)−Vrπr∗(P^)∥∞≤Γn\lVert v_r(P)-V_r^{\pi_r^*}(\widehat{P})\rVert_\infty\le\Gamma_n.

For each target reward and state, empirical optimality implies

vr(P)−Vrπ^r(P)=vr(P)−Vrπr∗(P^)+Vrπr∗(P^)−vr(P^)+vr(P^)−Vrπ^r(P)≤2Γn1.v_r(P)-V_r^{\widehat{\pi}_r}(P)=v_r(P)-V_r^{\pi_r^*}(\widehat{P})+V_r^{\pi_r^*}(\widehat{P})-v_r(\widehat{P})+v_r(\widehat{P})-V_r^{\widehat{\pi}_r}(P)\le2\Gamma_n\mathbf{1}.

The sample-size condition, ηJ>ε/(32H)\eta_J>\varepsilon/(32H), and J≥4J\ge4 imply

Γn≤(361024+55296220J2+150)ε<ε4.\Gamma_n\le\left(\frac{36}{1024}+\frac{55296}{220J^2}+\frac{1}{50}\right)\varepsilon<\frac{\varepsilon}{4}.

Thus every finest-net target has true policy loss at most $\varepsilon/2.

Finally, for an arbitrary query reward r∈Rr \in\mathcal{R}, choose q∈NJq \in\mathcal{N}_J at distance at most ηJ\eta_J and return π^q\widehat{\pi}_q. For any fixed policy, changing the reward by at most ηJ\eta_J changes every discounted value by at most HηJH\eta_J. The same bound holds for optimal values by (3). Consequently, we have that

vr(P)−Vrπ^q(P)≤2HηJ1+vq(P)−Vqπ^q(P)≤(ε8+ε2)1≤ε1.(18)v_r(P)-V^{\widehat{\pi}_q}_r(P) \le2H\eta_J\mathbf{1}+v_q(P)-V^{\widehat{\pi}_q}_q(P) \le\left(\frac{\varepsilon}{8}+\frac{\varepsilon}{2}\right)\mathbf{1}\le\varepsilon\mathbf{1}. \tag*{(18)}

Namely, the output policy is ε\varepsilon-optimal under rr. All these events were simultaneous over the finite sets used to answer every query, and the bounds hold for every admissible choice of qq and of the empirical optimal policy. (18) therefore holds simultaneously over the entire reward hull. This hence proves Theorem 4.1.

An upper bound independent of the number of objectives

From the other perspective, we can apply the similar argument and bound simultaneously to every scalar reward in [0,1]SA[0,1]^{SA}, and therefore supplies the state-dimension saturation for the reward-hull upper bound.

Theorem 5.1 (Uniform planning). Let H=(1−γ)−1H=(1-\gamma)^{-1}, 0<ε≤H0<\varepsilon\le H, and 0<δ<10<\delta<1. Set h=ε/(1000H)h=\varepsilon/(1000H), and define

Fh≜{min⁡{jh,H}:0≤j≤⌈H/h⌉}S,Lsat≜log⁡8SA∣Fh∣δ.\mathcal{F}_h \triangleq\left\{\min\{jh,H\}:0\le j\le\left\lceil H/h\right\rceil\right\}^{S}, \qquad L_{\mathrm{sat}}\triangleq\log\frac{8SA|\mathcal{F}_h|}{\delta}.

If nn independent transitions are collected at every state--action pair and

n≥214H3Lsat/ε2,n\ge2^{14}H^3L_{\mathrm{sat}}/\varepsilon^2,

then, with probability at least 1−δ1-\delta, for every reward r∈[0,1]SAr\in[0,1]^{SA}, every empirical optimal deterministic stationary policy is ε\varepsilon-optimal in the true MDP at every state. In particular, the total sample is

O(SAH3ε2[Slog⁡eH2ε+log⁡SAδ]).O\left(\frac{SAH^3}{\varepsilon^2}\left[S\log\frac{eH^2}{\varepsilon}+\log\frac{SA}{\delta}\right]\right).

The proof applies the same one-sided variance comparison to a grid of all value vectors in [0,H]S[0,H]^S. It is given in Appendix A. The finite value grid makes the concentration event uniform over every bounded reward and every empirical optimal policy.

Lower bounds

We then study lower bounds in this section. We assume that all rewards are known and bounded by one, and every test uses a simplex preference. The lower bound combines two constructions: a scalar problem supplies the baseline SAH3/ε2SAH^3/\varepsilon^2, and a multi-objective construction which adds a factor proportional to the dimension of an unknown exit distribution. Subset rewards identify that distribution, while a short collection of action rewards isolates the action whose distribution is being tested. Our technique, the packing and subset-testing approach, is related to reward-free and finite-known-reward lower bounds [9, 20]. Our arguments below imply the discounted simulator construction, a simplex-normalized encoding of the target action pair, and a decoder valid for history-dependent deployment policies.

We first introduce the three ingredients shared by the constructions. The first explains why deployment memory cannot circumvent the lower bound; the other two are standard coding and information inequalities in the form needed here.

Lemma 6.1. Fix γ∈[1/2,1)\gamma\in[1/2,1), H=(1−γ)−1H=(1-\gamma)^{-1}, and p=H−1p=H^{-1}. At a decision state xx, every action bb returns to xx with probability 1−p1-p and otherwise exits to an absorbing state yjy_j according to a distribution qbq_b. Let the known immediate reward at xx be aba_b, and let the reward at yjy_j be a known number tjt_j and zero at every other action. Set

D≜11−γ(1−p)=H2−H−1≥H2,gb≜ab+γ∑jqb(j)tj.D\triangleq\frac{1}{1-\gamma(1-p)}=\frac{H}{2-H^{-1}}\ge\frac{H}{2}, \qquad g_b\triangleq a_b+\gamma\sum_jq_b(j)t_j.

Then, for every randomized history-dependent policy π\pi started from xx, there is a probability vector zπz^\pi determined by the policy and the known rewards, independently of the distributions qbq_b for a fixed policy, such that

Vπ(x)=D∑bzbπgb,V∗(x)=Dmax⁡bgb.V^\pi(x)=D\sum_b z^\pi_b g_b,\qquad V^*(x)=D\max_b g_b.

Proof. Let ρt(b)\rho_t(b) be the probability of choosing action bb at time tt conditional on remaining at xx through time tt. Before exit, the observed state is always xx, the rewards are known functions of the chosen actions, and each action has the same survival probability. Thus ρt\rho_t is a functional of the policy that does not depend on the unknown exit distributions. Define

zbπ≜D−1∑t=0∞[γ(1−p)]tρt(b).z_b^\pi\triangleq D^{-1}\sum_{t=0}^{\infty}[\gamma(1-p)]^t\rho_t(b).

The geometric series sums to DD, so zπz^\pi is a probability vector. A visit to xx contributes the immediate reward aba_b and the expected discounted reward after exit, γpH∑jqb(j)tj\gamma p H \sum_j q_b(j)t_j. Since pH=1pH=1, summing these contributions implies the value identity. Every policy therefore implies a convex combination of the gbg_b, and a stationary action maximizing gbg_b attains the upper endpoint.

Lemma 6.2. For every even integer d≥128d \ge128, there is a set Cd⊂{−1,1}dC_d \subset\{-1,1\}^d such that each vector has d/2d/2 positive entries and

log⁡∣Cd∣≥d/16,dist⁡Ham(θ,θ′)≥d/4for θ≠θ′.\log|C_d| \ge d/16,\qquad\operatorname{dist}_{\mathrm{Ham}}(\theta,\theta') \ge d/4 \quad\text{for }\theta\ne\theta'.

Proof. Apply the greedy Gilbert packing argument [28] to the (dd/2)≥2d/(d+1)\binom{d}{d/2} \ge2^d/(d+1) balanced vectors. A Hamming ball of radius ⌊d/4⌋\lfloor d/4\rfloor in the full cube contains at most exp⁡(dh2(1/4))\exp(dh_2(1/4)) vectors, where h2(t)=−tlog⁡t−(1−t)log⁡(1−t)h_2(t)=-t\log t-(1-t)\log(1-t). Consequently the selected set has logarithmic size at least

d(log⁡2−h2(1/4))−log⁡(d+1)≥d/16.d\bigl(\log2-h_2(1/4)\bigr)-\log(d+1)\ge d/16.

The last inequality holds for d≥128d \ge128: the first coefficient exceeds 0.130.13, and log⁡(d+1)/d\log(d+1)/d decreases on this range and is less than 0.06750.0675 at d=128d=128.

Lemma 6.3. Let d≥128d \ge128 be even, let 0<p≤10 < p \le1, let 0<α≤1/20 < \alpha\le1/2, and write

u(j)≜1d,qθ(j)≜1+αθjd,θ∈Cd.u(j) \triangleq\frac{1}{d},\qquad q_\theta(j) \triangleq\frac{1+\alpha\theta_j}{d},\qquad\theta\in C_d.

Consider a family with an integer R≥1R \ge1 of independently indexed unknown transition rows. Each such row self-loops with probability 1−p1-p and exits with probability pp according to its distribution qθq_\theta; all other rows are fixed throughout the family. If a learner using at most NN adaptive simulator queries produces an output from which all RR codewords can be decoded with probability at least 3/43/4 in every model, then

N≥Rd32pα2.N \ge\frac{Rd}{32p\alpha^2}.

Proof. Give the parameter vector Θ\Theta the uniform prior on CdRC_d^R. For a fixed parameter vector ϑ\vartheta, compare the learner’s transcript with the reference model in which every unknown exit distribution is replaced by uu. One query to an unknown row has relative entropy at most

pKL⁡(qϑr∥u)≤p∑j=1d(qϑr(j)−u(j))2u(j)=pα2.p\operatorname{KL}(q_{\vartheta_r}\mathbin\Vert u)\le p\sum_{j=1}^{d}\frac{(q_{\vartheta_r}(j)-u(j))^2}{u(j)}=p\alpha^2.

Here KL⁡≤χ2\operatorname{KL}\le\chi^2 follows from log⁡x≤x−1\log x\le x-1. The adaptive relative-entropy chain rule [29 Lemma 15.1] implies

KL⁡(PϑZ∥P0Z)≤Npα2,\operatorname{KL}(\mathbb{P}_{\vartheta}^{Z}\mathbin\Vert\mathbb{P}_{0}^{Z})\le Np\alpha^2,

where ZZ includes the transcript, a model-independent internal random seed, and the learner’s output. Conditional on the past and the seed, the next query is the same function in both experiments; hence only its next-state observation contributes to the chain rule. Early stopping can be padded with queries to a known absorbing state. Apply Fano’s inequality in the reference-distribution form of [20 Lemma D.10]. The decoder in the hypothesis has error probability at most 1/41/4, so

Npα2≥34Rlog⁡∣Cd∣−log⁡2≥12Rlog⁡∣Cd∣≥Rd32.Np\alpha^2\ge\frac{3}{4}R\log|C_d|-\log2\ge\frac{1}{2}R\log|C_d|\ge\frac{Rd}{32}.

The middle inequality uses Rlog⁡∣Cd∣≥d/16≥8R\log|C_d|\ge d/16\ge8. Rearranging proves the claim.

The multi-objective lower bound

The next construction uses 2d2^d objectives for subset tests and only O(log⁡A)O(\log A) additional objectives to select an action pair.

Theorem 6.4 (Lower bound with additive objective budget). Let A≥2A \ge2, B≜⌊A/2⌋B \triangleq\lfloor A/2 \rfloor, and

ℓ≜2⌈max⁡{64,8log⁡B}⌉.\ell\triangleq2\left\lceil\max\{64,8\log B\}\right\rceil.

Let k≥1k \ge1, let d≥128d \ge128 be even, and assume S≥k+dS \ge k+d and m≥ℓ+2dm \ge\ell+2^d. For γ∈[1/2,1)\gamma\in[1/2,1), H=(1−γ)−1H=(1-\gamma)^{-1}, and 0<ε≤H/40960 < \varepsilon\le H/4096, there is a family of discounted MDPs with SS states, AA actions, and mm known reward functions in [0,1][0,1] for which every learner satisfying (1) with probability at least 3/43/4 in every model requires

N≥2−27kBdH3ε2.N \ge2^{-27}\frac{kBdH^3}{\varepsilon^2}.

This holds for adaptive simulator queries and arbitrary randomized history-dependent output policies.

Proof. We construct the family, show that a successful policy map identifies all its unknown distributions, and then apply Lemma 6.3.

Constructing the dynamics and the action codes. Take decision states x1,…,xkx_1,\ldots,x_k and absorbing outcome states y1,…,ydy_1,\ldots,y_d; any additional states are absorbing with zero rewards. At each decision state, pair the first 2B2B actions as (b,0),(b,1)(b,0),(b,1), b∈[B]b \in[B]. Every action self-loops with probability 1−p1-p, where p=H−1p=H^{-1}. Conditional on exit, action (b,0)(b,0) uses uu, and action (b,1)(b,1) uses qθi,bq_{\theta_i,b}. Here

Θ=(θi,b)∈CdkB,α=2048ε/H≤1/2.\Theta=(\theta_{i,b})\in\mathcal{C}_d^{kB},\qquad\alpha=2048\varepsilon/H\le1/2.

When AA is odd, the remaining action duplicates (1,0)(1,0) in both its transitions and its known rewards.

To make a preference select one pair, apply Lemma 6.2 in dimension ℓ\ell. Since ℓ≥128\ell\ge128 and ℓ/16≥log⁡B\ell/16 \ge\log B, it provides BB balanced binary vectors c1,…,cB∈{0,1}ℓc_1,\ldots,c_B \in\{0,1\}^{\ell}, obtained by replacing signs by zeros and ones. Each vector has ℓ/2\ell/2 ones, and any two differ in at least ℓ/4\ell/4 coordinates. Therefore va≜2ca/ℓ∈Δℓv^a \triangleq2c_a/\ell\in\Delta_\ell satisfies

⟨va,ca⟩=1,⟨va,cb⟩≤3/4(b≠a).\langle v^a,c_a\rangle=1,\qquad\langle v^a,c_b\rangle\le3/4\quad(b\ne a).

Indeed, equal Hamming weights imply that two distinct vectors share at most ℓ/2−ℓ/8=3ℓ/8\ell/2-\ell/8=3\ell/8 coordinates equal to one.

Defining simplex preferences that isolate a pair. The first ℓ\ell reward coordinates are action rewards:

rj(xi,(b,t))=cb(j),rj(yz,(b,t))=0.r_j(x_i,(b,t))=c_b(j),\qquad r_j(y_z,(b,t))=0.

One further coordinate is supplied for each subset U⊆[d]U\subseteq[d]:

rU(xi,(b,t))=0,rU(yz,(b,t))=1{z∈U}.r_U(x_i,(b,t))=0,\qquad r_U(y_z,(b,t))=\mathbf{1}\{z\in U\}.

All remaining coordinates are zero. These known rewards lie in [0,1][0,1] and are identical in every environment.

For pair aa and subset UU, use the simplex preference

wa,U≜(78va,18eU),w_{a,U}\triangleq\left(\frac{7}{8}v^a,\frac{1}{8}e_U\right),

with zero entries in unused coordinates. Lemma 6.1 expresses the value at xix_i through the effective rewards

gb,t=78⟨va,cb⟩+γ8qb,t(U).g_{b,t}=\frac{7}{8}\langle v^a,c_b\rangle+\frac{\gamma}{8}q_{b,t}(U).

Here qb,0=uq_{b,0}=u and qb,1=qθi,bq_{b,1}=q_{\theta_{i,b}} for the fixed decision state xix_i. Both target actions have effective reward at least 7/87/8, whereas every other pair has effective reward at most

7834+18=2532<78.\frac{7}{8}\frac{3}{4}+\frac{1}{8}=\frac{25}{32}<\frac{7}{8}.

The maximum effective reward is attained within the target pair. If the extra duplicate exists and a=1a=1, it has exactly the value of the target reference action; it does not change this comparison.

Recovering a codeword from the learned policy map. Fix a row (i,a)(i,a) and distinct θ,θ′∈Cd\theta,\theta'\in\mathcal{C}_d. Set

Uθ,θ′≜{j:θj=1, θj′=−1}.U_{\theta,\theta'}\triangleq\{j:\theta_j=1,\ \theta'_j=-1\}.

Balance and separation give ∣Uθ,θ′∣≥d/8|U_{\theta,\theta'}| \ge d/8, and

qθ(Uθ,θ′)−u(Uθ,θ′)=α∣Uθ,θ′∣d,qθ′(Uθ,θ′)−u(Uθ,θ′)=−α∣Uθ,θ′∣d.q_{\theta}(U_{\theta,\theta'}) - u(U_{\theta,\theta'}) = \frac{\alpha|U_{\theta,\theta'}|}{d}, \qquad q_{\theta'}(U_{\theta,\theta'}) - u(U_{\theta,\theta'}) = -\frac{\alpha|U_{\theta,\theta'}|}{d}.

For preference wa,Uθ,θ′,w_{a,U_{\theta,\theta'}}, the optimal target action therefore changes when the row changes from θ\theta to θ′\theta'. Their stationary value gap in either model is at least

Dγα∣Uθ,θ′∣8d≥Hα256=8ε,D\frac{\gamma\alpha|U_{\theta,\theta'}|}{8d} \ge\frac{H\alpha}{256} = 8\varepsilon,

using D≥H/2D \ge H/2 and γ≥1/2\gamma\ge1/2.

Let za,1z_{a,1} be the occupancy functional of the output policy from Lemma 6.1, at this preference and initial state. If the row is θ\theta, every other action has effective reward at most that of the target reference action. Consequently its value loss is at least 8ε(1−za,1)8\varepsilon(1-z_{a,1}), and ε\varepsilon-optimality requires za,1≥7/8z_{a,1} \ge7/8. If the row is θ′\theta', the value loss is at least 8εza,18\varepsilon z_{a,1}, so za,1≤1/8z_{a,1} \le1/8. These are restrictions on the same model-independent functional of the learned policy.

Decode row (i,a)(i,a) by selecting the codeword θ\theta whose policy at wa,Uθ,θ′w_{a,U_{\theta,\theta'}} has za,1≥7/8z_{a,1} \ge7/8 for every θ′≠θ\theta' \ne\theta; use any fixed output if there is no unique candidate. On the simultaneous success event, the true codeword passes every test. Every false candidate fails its comparison against the true codeword, by the preceding negative-gap calculation with the candidates reversed. Thus the decoder recovers all kBkB codewords on that event. This is an information-theoretic decoder; evaluating its occupancy functionals has no computational role in the argument.

Counting simulator observations. Lemma 6.3 now applies with R=kBR = kB. Substituting p=H−1p = H^{-1} and α=2048ε/H\alpha= 2048\varepsilon/H implies

N≥kBd32pα2=2−27kBdH3ε2.N \ge\frac{kBd}{32p\alpha^2} = 2^{-27}\frac{kBdH^3}{\varepsilon^2}.

This thus completes the proof.

Since ℓ=O(log⁡(A+1))\ell= O(\log(A+1)), choosing dd of order min⁡{S,log⁡(m−ℓ)}\min\{S,\log(m-\ell)\} and k=S−dk = S-d implies the desired min⁡{S,log⁡m}\min\{S,\log m\} factor when m≥2ℓm \ge2\ell and that minimum is sufficiently large. Appendix C implies a related construction that uses only pure preferences and has objective budget (A−1)2d(A-1)2^d.

The scalar baseline

For the remaining parameter regimes, we use the following scalar change-of-measure bound. Its proof, given in Appendix B, reuses Lemma 6.1 to cover history-dependent policies.

Theorem 6.5 (Scalar lower bound). Let S≥3S \ge3, A≥2A \ge2, m≥1m \ge1, γ∈[1/2,1)\gamma\in[1/2,1), and H=(1−γ)−1H = (1-\gamma)^{-1}. If 0<ε≤H/640 < \varepsilon\le H/64, every learner that uses at most NN adaptive generative-model queries and satisfies (1) with probability at least 3/43/4 on every instance must satisfy

N≥(S−2)AH312288ε2.N \ge\frac{(S-2)AH^3}{12288\varepsilon^2}.

The conclusion allows arbitrary randomized history-dependent output policies.

Assembling the joint minimax rate

Proof of Theorem 3.1. We first combine the two upper bounds. Fix δ=1/4\delta= 1/4. In Theorem 4.1, the definitions give

J≤C1L,log⁡∣G∣≤C2L,Λ≤C3log⁡(em)L,J \le C_1L,\qquad\log|\mathcal{G}| \le C_2L,\qquad\Lambda\le C_3\log(em)L,

for universal constants C1,C2,C3C_1,C_2,C_3. To check these estimates, note that L=log⁡(eSAH2/ε)L = \log(eSAH^2/\varepsilon) dominates 11, log⁡(SA)\log(SA), log⁡(H/ε)\log(H/\varepsilon), and log⁡H\log H in the stated range ε≤H/4096\varepsilon\le H/4096. Also log⁡J≤CL\log J \le CL, so the displayed upper bound on ∣G∣|\mathcal{G}| implies the second estimate. Since log⁡(em)≥1\log(em) \ge1, the terms of Λ\Lambda not containing mm can be included in its right-hand side. Therefore the chaining algorithm uses at most

CSAH3ε2log⁡(em)L3C\frac{SAH^3}{\varepsilon^2}\log(em)L^3

samples. The ceiling adds at most SASA, which is absorbed by this bound. Theorem 5.1, whose logarithmic term satisfies Lsat≤CSLL_{\mathrm{sat}} \le CSL, implies at most

CSAH3ε2SLC\frac{SAH^3}{\varepsilon^2}SL

samples. Choose the algorithm with the smaller displayed sufficient sample count. Since L≥1L \ge1, the minimum is at most CSAH3ε−2min⁡{S,log⁡(em)}L3CSAH^3\varepsilon^{-2}\min\{S,\log(em)\}L^3.

For the lower bound, write κ=min⁡{S,log⁡(em)}\kappa= \min\{S,\log(em)\} and use the action-code length

ℓ=2⌈max⁡{64,8log⁡⌊A/2⌋}⌉≤C4log⁡(eA).\ell= 2\left\lceil\max\{64,8\log\lfloor A/2\rfloor\}\right\rceil\le C_4\log(eA).

Suppose first that m≥2ℓm \ge2\ell and κ≥512\kappa\ge512. Define

x≜min⁡{S/2,log⁡2(m−ℓ)},d≜2⌊x/2⌋,k≜S−d.x \triangleq\min\{S/2,\log_2(m-\ell)\}, \qquad d \triangleq2\lfloor x/2\rfloor, \qquad k \triangleq S-d.

The assumptions imply x≥κ/2x \ge\kappa/2: the state term has this property, while m−ℓ≥m/2m-\ell\ge m/2 and the large lower bound on log⁡(em)\log(em) imply log⁡2(m/2)≥log⁡(em)/2\log_2(m/2) \ge\log(em)/2. Hence d≥x−2≥κ/4≥128d \ge x-2 \ge\kappa/4 \ge128, dd is even, and k≥S/2k \ge S/2. Moreover ℓ+2d≤m\ell+2^d \le m. Theorem 6.4 applies, and ⌊A/2⌋≥A/3\lfloor A/2\rfloor\ge A/3 yields

N∗≥c1SAH3ε2κ.N^* \ge c_1\frac{SAH^3}{\varepsilon^2}\kappa.

If κ<512\kappa< 512, Theorem 6.5 implies the same conclusion after decreasing the universal constant: S−2≥S/3S-2 \ge S/3 for S≥3S \ge3, and the factor κ\kappa is bounded by 512. The remaining case has m<2ℓm < 2\ell and κ≥512\kappa\ge512. Then

κ≤log⁡(em)≤log⁡(2eℓ)≤C5(1+log⁡log⁡(eeA))=C5LA.\kappa\le\log(em) \le\log(2e\ell) \le C_5(1+\log\log(e^eA)) = C_5L_A.

The scalar lower bound consequently implies

N∗≥c2SAH3ε2≥c3SAH3ε2κLA.N^* \ge c_2\frac{SAH^3}{\varepsilon^2} \ge c_3\frac{SAH^3}{\varepsilon^2}\frac{\kappa}{L_A}.

This proves the universal lower bound. When m≥2ℓm \ge2\ell, only the first two cases are needed, and the LAL_A denominator is absent. Since 2ℓ≤Clog⁡(A+1)2\ell\le C\log(A+1), the stated sufficient objective-budget condition follows. Together, they complete the proofs for both upper and lower bounds.

Discussion

The objective dependence is determined by the geometry of the known reward hull. A fine cover used in a single union bound would introduce H2/ε2H^2/\varepsilon^2 through its entropy. Chaining avoids that loss because finer reward increments have smaller resolved variance. The one-sided Bellman inequality remains valid even though the policy optimal for the target reward need not optimize its approximants.

The logarithmic-objective guarantee applies to empirical planning after reward rounding. Direct empirical planning for every bounded reward has the separate state-saturation guarantee. Both statements assume known bounded reward coordinates, simplex preferences, a stationary discounted kernel, and uniform accuracy at every initial state. The result identifies the joint rate up to logarithmic factors; exact logarithmic and confidence dependence remain separate questions.

Proof of the state-saturation upper bound

Proof. Write t=Lsat/nt = L_{\mathrm{sat}}/n. The displayed sample condition implies t≤1t \le1. For every fixed f0∈Fhf_0 \in\mathcal{F}_h and every row, apply Lemma 4.2 with B=HB = H to Xi=f0(Yi)∈[0,H]X_i = f_0(Y_i) \in[0,H], where Y1,…,YnY_1,\ldots,Y_n are the samples at that row. On an event with failure probability at most 6e−Lsat6e^{-L_{\mathrm{sat}}}, it implies the following bound; for K=P^K = \widehat{P} this is (7), and for K=PK = P it follows from (6) because 2≤2\sqrt{2} \le2 and 2/3≤42/3 \le4:

∣(P^−P)f0∣≤2t σK(f0)+4Ht,K∈{P,P^}.\left|(\widehat{P}-P)f_0\right| \le2\sqrt{t}\,\sigma_K(f_0) + 4Ht,\qquad K \in\{P,\widehat{P}\}.

A union bound makes these statements simultaneous over rows and grid points with failure probability at most δ\delta. For any f∈[0,H]Sf \in[0,H]^S, choose f0∈Fhf_0 \in\mathcal{F}_h with ∥f−f0∥∞≤h\|f-f_0\|_\infty\le h. The row error changes by at most 2h2h, and the triangle inequality for centered L2(K)L_2(K) implies ∣σK(f)−σK(f0)∣≤h\left|\sigma_K(f)-\sigma_K(f_0)\right| \le h. Consequently, on the same event,

∣(P^−P)f∣≤2t σK(f)+4Ht+4h,K∈{P,P^},f∈[0,H]S.(19)\left|(\widehat{P}-P)f\right| \le2\sqrt{t}\,\sigma_K(f) + 4Ht + 4h,\qquad K \in\{P,\widehat{P}\},\quad f \in[0,H]^S. \tag*{(19)}

All inequalities here are coordinatewise.

We next prove a deterministic evaluation comparison that can be used in either direction. Let (K0,K1)(K^0,K^1) be either (P,P^)(P,\widehat{P}) or (P^,P)(\widehat{P},P). For any reward r∈[0,1]SAr \in[0,1]^{SA}, let f=vr(K0)f = v_r(K^0) and let π\pi be a deterministic stationary optimal policy in the base kernel K0K^0. Define

K=Kπ1,R=(I−γK)−1,E=∥γR∣(Kπ1−Kπ0)f∣∥∞.K = K^1_\pi,\qquad R = (I-\gamma K)^{-1},\qquad E = \left\|\gamma R\left|(K^1_\pi-K^0_\pi)f\right|\right\|_\infty.

The vector ff satisfies 0≤f≤H10 \le f \le H\mathbf{1}. Its Bellman equation in the base model implies the one-sided bound

b≜f−γKf=rπ+γ(Kπ0−Kπ1)f≤1+γ∣(Kπ1−Kπ0)f∣.b \triangleq f-\gamma Kf = r_\pi+\gamma(K^0_\pi-K^1_\pi)f \le\mathbf{1}+\gamma\left|(K^1_\pi-K^0_\pi)f\right|.

Lemma 4.4, applied with u=fu=f, c=Hc=H, and β=1+γ∣(Kπ1−Kπ0)f∣\beta=\mathbf{1}+\gamma\left|(K^1_\pi-K^0_\pi)f\right|, for which Rβ≤(H+E)1R\beta\le(H+E)\mathbf{1} because R1=H1R\mathbf{1}=H\mathbf{1}, implies

γ∥RσK(f)∥∞≤2H3+2H2E.\gamma\left\|R\sigma_K(f)\right\|_\infty\le\sqrt{2H^3+2H^2E}.

Apply γR\gamma R to (19) with the variance taken under K1K^1 (the true variance when K1=PK^1=P, the empirical variance when K1=P^K^1=\widehat{P}), evaluated at the rows (s,π(s))(s,\pi(s)). By the row convention, this implies

E≤2t2H3+2H2E+4H2t+4HhE \le2\sqrt{t}\sqrt{2H^3+2H^2E}+4H^2t+4Hh
≤22H3/2t+22HtE+4H2t+4Hh.\le2\sqrt{2}H^{3/2}\sqrt{t}+2\sqrt{2}H\sqrt{t}\sqrt{E}+4H^2t+4Hh.

Young’s inequality bounds the second term by E/2+4H2tE/2+4H^2t. Rearranging therefore implies

E≤Bn≜42H3/2t+16H2t+8Hh.E \le B_n \triangleq4\sqrt{2}H^{3/2}\sqrt{t}+16H^2t+8Hh.

By the definitions of nn and hh, and since ϵ≤H\epsilon\le H,

Bn≤(42128+11024+1125)ϵ<ϵ4.B_n \le\left(\frac{4\sqrt{2}}{128}+\frac{1}{1024}+\frac{1}{125}\right)\epsilon< \frac{\epsilon}{4}.

The exact policy-evaluation identity bounds the difference between f=vr(K0)f=v_r(K^0) and the value of π\pi under K1K^1 by EE.

Apply this comparison to a true optimal policy and then to an empirical optimal policy, using opposite choices of (K0,K1)(K^0,K^1). Empirical optimality makes the middle term in the resulting three-term value decomposition nonpositive. The true suboptimality of the empirical optimal policy is therefore at most EP→P^+EP^→P≤2Bn<ϵ/2E_{P\to\widehat{P}}+E_{\widehat{P}\to P}\le2B_n<\epsilon/2. Here the two errors use different policies and resolvents, and each is bounded by BnB_n. The concentration event covers every vector in [0,H]S[0,H]^S, so both comparisons hold for every reward and every corresponding optimal policy simultaneously. Finally, ∣Fh∣≤(1000H2/ϵ+2)S|\mathcal{F}_h|\le(1000H^2/\epsilon+2)^S, which implies the stated sample-complexity bound. ∎

The scalar change-of-measure argument

Proof of Theorem 6.5. Let k=S−2k = S - 2 decision states x1,…,xkx_1,\ldots,x_k share two absorbing states y+y_+ and y−y_-. The first objective rewards one at y+y_+ and zero elsewhere; all other objectives are zero. We use preference e1e_1. Every action at a decision state exits with probability p=H−1p = H^{-1} and otherwise self-loops. Conditional on exit, it selects y+y_+ with probability qi,aq_{i,a} and y−y_- otherwise.

The null model has qi,a=1/2q_{i,a} = 1/2 for every row. Alternative (i,a)(i,a) changes only that row to qi,a=1/2+αq_{i,a} = 1/2 + \alpha, with α=16ε/H≤1/4\alpha= 16\varepsilon/H \le1/4. Lemma 6.1 implies

Vπ(xi)=Dγ∑azi,aqi,a,V∗(xi)=Dγmax⁡aqi,a.V^\pi(x_i) = D_\gamma\sum_a z_{i,a}q_{i,a}, \qquad V^*(x_i) = D_\gamma\max_a q_{i,a}.

Here ziz_i is a model-independent probability vector determined by the output policy at e1e_1. In alternative (i,a)(i,a), the value gap to every other stationary action is Dγα≥Hα/4=4εD_\gamma\alpha\ge H\alpha/4 = 4\varepsilon. An ε\varepsilon-optimal output must therefore have zi,a≥3/4z_{i,a} \ge3/4.

For fixed ii, the output events Ei,a={zi,a≥3/4}E_{i,a} = \{z_{i,a} \ge3/4\} are disjoint. Thus at least A−1≥A/2A - 1 \ge A/2 actions satisfy P0(Ei,a)≤1/2\mathbb{P}_0(E_{i,a}) \le1/2, while the success requirement in their respective alternatives implies Pi,a(Ei,a)≥3/4\mathbb{P}_{i,a}(E_{i,a}) \ge3/4. Treat simulator rows as arms. The changed rows have the same positive support, and the number of queries is bounded. The change-of-measure inequality of [30 Lemma 1], followed by binary Pinsker, implies

E0Ni,a p kl⁡(1/2∥1/2+α)≥kl⁡(P0(Ei,a),Pi,a(Ei,a))≥2(3/4−1/2)2=1/8.\mathbb{E}_0N_{i,a}\,p\,\operatorname{kl}(1/2\mathbin{\|}1/2+\alpha) \ge\operatorname{kl}\bigl(\mathbb{P}_0(E_{i,a}),\mathbb{P}_{i,a}(E_{i,a})\bigr) \ge2(3/4-1/2)^2 = 1/8.

Only queries to row (i,a)(i,a) differ between the experiments. Their null-to-alternative divergence satisfies

p kl⁡(1/2∥1/2+α)=−p2log⁡(1−4α2)≤2pα21−4α2≤3pα2.p\,\operatorname{kl}(1/2\mathbin{\|}1/2+\alpha) = -\frac{p}{2}\log(1-4\alpha^2) \le\frac{2p\alpha^2}{1-4\alpha^2} \le3p\alpha^2.

The first inequality uses −log⁡(1−x)≤x/(1−x)-\log(1-x) \le x/(1-x), and the second uses α≤1/4\alpha\le1/4. The preceding change-of-measure inequality therefore implies

E0Ni,a≥124pα2.\mathbb{E}_0N_{i,a} \ge\frac{1}{24p\alpha^2}.

Summing over at least kA/2kA/2 selected rows and using the maximum query budget NN implies

N≥kA48pα2=(S−2)AH312288ε2.N \ge\frac{kA}{48p\alpha^2} = \frac{(S-2)AH^3}{12288\varepsilon^2}.

As in Lemma 6.3, early stopping is handled by padding with queries to a known absorbing state. □

A lower bound using only pure preferences

The following variant uses one objective for each action–subset pair. It implies the same logarithmic objective dependence for a fixed number of actions, and shows that the lower-bound mechanism already appears when the learner must support only the simplex vertices.

Theorem C.1 (Simulator lower bound for simultaneous preferences). Let A≥2A \ge2, let k≥1k \ge1, and let d≥128d \ge128 be even. Suppose S≥k+dS \ge k+d and m≥(A−1)2dm \ge(A-1)2^d. For γ∈[1/2,1)\gamma\in[1/2,1), H=(1−γ)−1H = (1-\gamma)^{-1}, and 0<ε≤H/20480 < \varepsilon\le H/2048, there is a family of discounted MDPs with SS states, AA actions, and mm known reward functions in [0,1][0,1] for which every learner satisfying (1) with probability at least 3/43/4 in every model requires

N≥2−25k(A−1)dH3ε2.N \ge2^{-25}\frac{k(A-1)dH^3}{\varepsilon^2}.

The conclusion allows adaptive simulator queries and arbitrary randomized history-dependent output policies.

Proof. Write B=A−1B = A-1, and use the balanced code Cd\mathcal{C}_d of Lemma 6.2. Set p=H−1p = H^{-1} and α=1024ε/H≤1/2\alpha= 1024\varepsilon/H \le1/2. As in the main construction, take decision states x1,…,xkx_1,\ldots,x_k and absorbing outcome states y1,…,ydy_1,\ldots,y_d. Any additional states are absorbing with zero reward. Actions are 0,1,…,B0,1,\ldots,B. At xix_i, every action self-loops with probability 1−p1-p. Conditional on exit, action 00 uses uu, and action a∈[B]a \in[B] uses qΘi,aq_{\Theta_{i,a}}, where Θ=(θi,a)∈Cdk\Theta= (\theta_{i,a}) \in\mathcal{C}_d^k.

For each a∈[B]a \in[B] and U⊆[d]U \subseteq[d], provide the known reward coordinate

ra,U(xi,b)=341{b∈{0,a}},ra,U(yj,b)=141{j∈U}.r^{a,U}(x_i,b) = \frac{3}{4}\mathbf{1}\{b \in\{0,a\}\}, \qquad r^{a,U}(y_j,b) = \frac{1}{4}\mathbf{1}\{j \in U\}.

Pad unused reward coordinates with zero. These rewards lie in [0,1][0,1], and we use only their pure simplex preferences ea,Ue_{a,U}. Lemma 6.1 implies the effective rewards

gb=341{b∈{0,a}}+γ4qb(U).g_b = \frac{3}{4}\mathbf{1}\{b \in\{0,a\}\} + \frac{\gamma}{4}q_b(U).

The target actions 0,a0,a have gb≥3/4g_b \ge3/4, whereas every other action has gb≤1/4g_b \le1/4. Thus all other unknown rows are irrelevant to the optimal comparison.

For distinct codewords θ,θ′\theta,\theta', take Uθ,θ′={j:θj=1,θj′=−1}U_{\theta,\theta'} = \{j:\theta_j=1,\theta'_j=-1\}. Its size is at least d/8d/8, and qθ(U)−u(U)q_\theta(U)-u(U) and qθ′(U)−u(U)q_{\theta'}(U)-u(U) equal respectively α∣U∣/d\alpha|U|/d and −α∣U∣/d-\alpha|U|/d. The two target stationary actions exchange optimality, with value gap at least

Dγα∣Uθ,θ′∣4d≥Hα128=8ε.D\frac{\gamma\alpha|U_{\theta,\theta'}|}{4d} \ge\frac{H\alpha}{128}=8\varepsilon.

The occupancy zaz_a of the learned policy must therefore satisfy za≥7/8z_a \ge7/8 when the row is θ\theta, and za≤1/8z_a \le1/8 when it is θ′\theta'. This follows directly from the convex-combination value formula: the losses are at least 8ε(1−za)8\varepsilon(1-z_a) and 8εza8\varepsilon z_a, respectively.

For each row (i,a)(i,a), decode a candidate θ\theta precisely when its output policies satisfy za≥7/8z_a \ge7/8 at every preference ea,Uθ,θ′, θ′≠θe_{a,U_{\theta,\theta'}},\ \theta'\ne\theta; break a nonunique or empty candidate set arbitrarily. On the simultaneous success event, the true codeword passes every comparison, and any false codeword fails its comparison against the true one. The output thus identifies all kBkB codewords. Lemma 6.3 implies

N≥kBd32pα2=2−25k(A−1)dH3ε2.N \ge\frac{kBd}{32p\alpha^2}=2^{-25}\frac{k(A-1)dH^3}{\varepsilon^2}.

Taking an even dd below both S/2S/2 and log⁡2(m/(A−1))\log_2(m/(A-1)), and setting k=S−dk=S-d, yields

N≥cSAH3ε2min⁡{S,log⁡(m/(A−1))}.N \ge c\frac{SAH^3}{\varepsilon^2}\min\{S,\log(m/(A-1))\}.

when the indicated minimum is sufficiently large. In particular, for fixed AA this is the min⁡{S,log⁡m}\min\{S,\log m\} dependence. The main construction improves its objective budget by using mixed preferences to encode the target action pair.

References

  1. [1]D. M. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley, “A survey of multi-objective sequential decision-making,” Journal of Artificial Intelligence Research, vol. 48, pp. 67–113, 2013.
  2. [2]C. F. Hayes, R. Rădulescu, E. Bargiacchi, J. Källström, M. Macfarlane, M. Reymond, T. Verstraeten, L. M. Zintgraf, R. Dazeley, F. Heintz, et al., “A practical guide to multi-objective reinforcement learning and planning,” Autonomous Agents and Multi-Agent Systems, vol. 36, no. 1, p. 26, 2022.DOI
  3. [3]R. Yang, X. Sun, and K. Narasimhan, “A generalized algorithm for multi-objective reinforcement learning and policy adaptation,” Advances in neural information processing systems, vol. 32, 2019.arxiv.org/abs/1908.08342
  4. [4]A. Rame, G. Couairon, C. Dancette, J.-B. Gaya, M. Shukor, L. Soulier, and M. Cord, “Rewarded soups: towards pareto-optimal alignment by interpolating weights fine-tuned on diverse rewards,” Advances in Neural Information Processing Systems, vol. 36, pp. 71095–71134, 2023.arxiv.org/abs/2306.04488
  5. [5]M. G. Azar, R. Munos, and H. J. Kappen, “Minimax pac bounds on the sample complexity of reinforcement learning with a generative model,” Machine learning, vol. 91, pp. 325–349, June 2013.DOI
  6. [6]A. Agarwal, S. Kakade, and L. F. Yang, “Model-based reinforcement learning with a generative model is minimax optimal,” Conference on Learning Theory, pp. 67–83, 2020.arxiv.org/abs/1906.03804
  7. [7]G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen, “Breaking the sample size barrier in model-based reinforcement learning with a generative model,” in Proc. Advances in Neural Information Processing Systems (NeurIPS) (H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, eds.), vol. 33, pp. 12861–12872, Curran Associates, Inc., December 2020. arXiv: 2005.12900.arxiv.org/abs/2005.12900
  8. [8]D. Zhou, J. Chen, and Q. Gu, “Provable multi-objective reinforcement learning with generative models,” arXiv preprint arXiv:2011.10134, 2020.arxiv.org/abs/2011.10134
  9. [9]Z. Chen and Z. Zhang, “Optimal multi-reward reinforcement learning,” arXiv preprint arXiv:2609.36486, 2026.arxiv.org/abs/2609.36486
  10. [10]H. Lu, D. Herman, and Y. Yu, “Multi-objective reinforcement learning: Convexity, stationarity and pareto optimality,” in The Eleventh International Conference on Learning Representations, 2023.
  11. [11]Y. Li, P. Ju, and N. B. Shroff, “How to find the exact pareto front for multi-objective mdps?,” arXiv preprint arXiv:2410.15557, 2024.arxiv.org/abs/2410.15557
  12. [12]S. Mannor and N. Shimkin, “A geometric approach to multi-criterion reinforcement learning,” Journal of machine learning research, vol. 5, no. Apr, pp. 325–360, 2004.
  13. [13]T. Zhou, F. Hairi, H. Yang, J. Liu, T. Tong, F. Yang, M. Momma, and Y. Gao, “Finite-time convergence and sample complexity of actor-critic multi-objective reinforcement learning,” arXiv preprint arXiv:2405.03082, 2024.arxiv.org/abs/2405.03082
  14. [14]A. Abels, D. Roijers, T. Lenaerts, A. Nowé, and D. Steckelmacher, “Dynamic weights in multi-objective deep reinforcement learning,” in International conference on machine learning, pp. 11–20, PMLR, 2019.arxiv.org/abs/1809.07803
  15. [15]B. Zhu, M. Dang, and A. Grover, “Scaling pareto-efficient decision making via offline multi-objective rl,” arXiv preprint arXiv:2305.00567, 2023.arxiv.org/abs/2305.00567
  16. [16]S. Vaswani, L. Yang, and C. Szepesvári, “Near-optimal sample complexity bounds for constrained mdps,” Advances in Neural Information Processing Systems, vol. 35, pp. 3110–3122, 2022.arxiv.org/abs/2206.06270
  17. [17]J. Wu, V. Braverman, and L. Yang, “Accommodating picky customers: Regret bound and exploration complexity for multi-objective reinforcement learning,” Advances in Neural Information Processing Systems, vol. 34, pp. 13112–13124, 2021.arxiv.org/abs/2011.13034
  18. [18]S. Qiu, D. Zhang, R. Yang, B. Lyu, and T. Zhang, “Traversing pareto optimal policies: Provably efficient multi-objective reinforcement learning,” arXiv preprint arXiv:2407.17466, 2024.arxiv.org/abs/2407.17466
  19. [19]M. Hu and M. Yu, “Near-minimax multi-objective RL under predictable adversarial preferences and preference-free exploration in linear MDPs,” in Forty-third International Conference on Machine Learning, 2026.
  20. [20]C. Jin, A. Krishnamurthy, M. Simchowitz, and T. Yu, “Reward-free exploration for reinforcement learning,” in International Conference on Machine Learning, pp. 4870–4879, PMLR, 2020.arxiv.org/abs/2002.02794
  21. [21]X. Zhang, Y. Ma, and A. Singla, “Task-agnostic exploration in reinforcement learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 11734–11743, 2020.arxiv.org/abs/2006.09497
  22. [22]P. Ménard, O. D. Domingues, A. Jonsson, E. Kaufmann, E. Leurent, and M. Valko, “Fast active learning for pure exploration in reinforcement learning,” in International Conference on Machine Learning, pp. 7599–7608, PMLR, 2021.arxiv.org/abs/2007.13442
  23. [23]G. Li, Y. Yan, Y. Chen, and J. Fan, “Minimax-optimal reward-agnostic exploration in reinforcement learning,” Mathematics of Operations Research, 2026.arxiv.org/abs/2304.07278
  24. [24]O. Ridel and A. Cohen, “Improved bounds for reward-agnostic and reward-free exploration,” arXiv preprint arXiv:2602.16363, 2026.arxiv.org/abs/2602.16363
  25. [25]M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
  26. [26]W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American statistical association, vol. 58, no. 301, pp. 13–30, 1963.
  27. [27]A. Maurer and M. Pontil, “Empirical bernstein bounds and sample variance penalization,” arXiv preprint arXiv:0907.3740, July 2009. arXiv: 0907.3740.arxiv.org/abs/0907.3740
  28. [28]E. N. Gilbert, “A comparison of signalling alphabets,” The Bell system technical journal, vol. 31, no. 3, pp. 504–522, 1952.DOI
  29. [29]T. Lattimore and C. Szepesvári, Bandit algorithms. Cambridge University Press, 2020.
  30. [30]E. Kaufmann, O. Cappé, and A. Garivier, “On the complexity of best-arm identification in multi-armed bandit models,” The Journal of Machine Learning Research, vol. 17, no. 1, pp. 1–42, 2016.

Paper details

vlnc:W_zvev8kuy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents