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, states, actions, and known reward functions taking values in , given access to a generative model. The learner must provide an -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 , we establish the constant-confidence minimax sample complexity , where the suppressed factors are logarithmic in and the dependence on 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 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 rewards , which we call the coordinate rewards; together they form the reward dictionary . A preference vector assigns them nonnegative weights summing to one and induces the scalar reward . 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 and for the numbers of states and actions, for the discount factor, and for the effective horizon. For one fixed bounded reward, the minimax sample complexity is in the standard nontrivial parameter regime [5, 6, 7]. The closest discounted MORL analysis gives an bound for estimating scalarized -functions uniformly over preferences [8]. A direct reduction through a net of preferences also gives linear dependence on 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 , , , and , we show that the minimax sample complexity is
where the suppressed factors are logarithmic in , , , and the dependence on 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 factor (Theorem 4.1). Direct empirical planning for the requested reward gives the factor , since its guarantee holds for every reward in (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 , their logarithmic size is of order . A single union bound over the cover at the final resolution would add a factor of order . 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 and the 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 dependence. Subset rewards distinguish distributions over shared absorbing outcomes using coordinate rewards, which yields a factor of order , capped by . An additional action code of length lets a simplex preference single out one pair of actions while keeping every reward in (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 for a preference-weighted -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 . 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 denoting the episode length, their exploration upper bound is 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 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 episodes for a list of rewards. Under the parameter conditions of their Corollary 1, they also prove a lower bound of order . 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 . Theorem 5.1 supplies the complementary all-rewards guarantee under our sampling model. Table 1 collects these rates.
| Work | Access | Rewards served | Upper bound | Lower bound |
| Zhou et al. [8] | generative, discounted | -values for all with | single objective only | |
| Net + planning [6, 7] | generative, discounted | – | ||
| Wu et al. [17] | online, episodic | , preferences revealed later | 1 | |
| Jin et al. [20] | online, episodic | all rewards, revealed later | ||
| Zhang et al. [21] | online, episodic | tasks, unknown during exploration | ||
| Li et al. [23] | online, episodic | given rewards; all rewards | ; 2 | – |
| Ridel and Cohen [24] | online, episodic | given rewards; all rewards | ; | –; 3 |
| Chen and Zhang [9] | online, episodic | known rewards | 3 | |
| This work | generative, discounted | (equivalently ) |
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 ; constants and logarithmic factors other than those shown are omitted, and is the number of rewards or objectives. Online episodic rows count episodes of length with per-step rewards in . Generative rows count simulator queries in discounted MDPs with . 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 sphere; under that normalization, all actions in its construction are within of each other in scalarized value, so the lemma does not hold as stated. 2A lower-order term of order dominates unless is small; [24] reduces it to . 3Time-inhomogeneous constructions; the bound of [9] holds under the parameter conditions of its Corollary 1.
Problem formulation
Model and reward class
Let and be finite sets with cardinalities and . The stationary transition kernel is unknown. The discount factor is known, and . The learner is given the complete tables of the deterministic coordinate rewards , , which form the reward dictionary . We identify each reward with its table in . Define
We call a preference and the reward hull. Since , every scalarized reward lies in , whatever the value of .
A policy may be randomized and history-dependent. For a reward , we use unnormalized discounted values,
where denotes expectation over trajectories with , actions drawn from , and transitions drawn from . Both values lie in . For a preference , we abbreviate and . 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 target | Reward information during sampling | Query class |
| Fixed reward | One scalar reward is known | The singleton |
| Finite known tasks | The rewards are known | The finite set |
| Uniform MORL (this work) | The rewards are known; the query preference is not | The reward hull |
| Reward-free learning | No reward is known | Every reward in |
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 is fixed and known before sampling, optimizing is an ordinary single-reward learning problem, and the sampling procedure may be tailored to that reward. For the finite list , one dataset must support policies 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 are , , and . The first two actions are optimal for and , respectively. The third is optimal for , 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
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 , and through the policy selection after sampling.
Simulator access and the simultaneous guarantee
Each generative-model query selects a state–action pair and returns a fresh draw from , 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 . Answering a query may use the stored data and additional computation, but makes no further simulator calls. Let denote the training transcript together with the learner’s internal random seed, so that the selection rule is fixed once is fixed. Define the loss of the rule at preference by
For every transition kernel and every reward dictionary, we require the event
to hold with probability at least :
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
for every fixed . Its exceptional datasets may depend on . Our requirement places the supremum over 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 -approximate convex coverage set, with accuracy required at every initial state: rather than listing policies, it returns an -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 assigns a distribution on to each state–action pair; the two kernels used below are the true kernel and the empirical kernel of § 4. For a reward , let be the optimal value vector in , and let be the value vector of a policy in . An omitted kernel is , so and . For a deterministic stationary policy , write , and let be the stochastic matrix whose row is . For , write
For , the same notation is indexed by states. Thus , and similarly . Vector inequalities are coordinatewise. Squares, absolute values, and products of vectors are also coordinatewise, is the all-ones vector, and 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 , every policy , and all , Bellman contraction and the discounted reward sum give
In particular, implies that optimal values are -Lipschitz in the preference with respect to , although an optimal policy need not vary continuously with the preference.
Main result: Near Minimax Sample Complexity
Let be the smallest worst-case maximum number of simulator queries sufficient for (1) with success probability at least , uniformly over all known reward functions and all transition kernels. Computational cost is not included in this definition. Set
Natural logarithms are used unless a base is displayed.
Theorem 3.1 (Joint near-minimax characterization). There are universal constants such that, for , , , , and ,
If is at least a sufficiently large constant times , the denominator can be removed from the lower bound, after adjusting the universal constant. The upper bound has a high-probability version for every , with logarithmic dependence on 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 , , , , not on an unspecified polynomial in . In particular, if a tilde hides only logarithms in these other parameters, the joint rate is
This statement retains the objective dependence explicitly. When is exponentially large in , the logarithmic objective cost can itself be of order . For fixed , 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 . In the reward-hull regime, it rounds a query to a finite reward cover and returns an optimal policy for the rounded reward in . Fixing an order on the cover and on the actions makes both selections deterministic. In the state-saturation regime, it plans directly for . 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 , the cover entropy is of order . Its square root contributes a factor to Bernstein’s inequality. The variance comparison supplies a matching factor , 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 , and let . Rewards are known. All samples below concern transitions. Fix and , and define
and
Then , , and .
Theorem 4.1 (Reward-hull chaining upper bound). Draw independent next states at each state–action pair, form the empirical kernel , and suppose
Then there is a finite -cover in the supremum norm, depending only on the known rewards, with the following property. With probability at least , simultaneously for every , every with , and every deterministic stationary policy that is optimal for reward in the empirical kernel (ties broken arbitrarily),
In particular, the algorithm that chooses any such and returns any such is simultaneously -optimal for all . The total sample complexity is at most
In particular, the dependence on the number of reward coordinates is logarithmic, and the polynomial dependence is .
Finite reward covers
For , define
and set and . Clearly . We then claim that is an -cover of . To verify this, consider a fixed reward . We can sample independent coordinate rewards with index distribution . At each of the state-action entries, their average differs from its mean by more than with probability at most . Specifically, Hoeffding’s inequality [26 Theorem 2] applied to a -sample average with index distribution implies
and a union bound implies total probability at most . Therefore, at least one deterministic average in is consequently within of in the supremum norm.
Now for every target , fix an approximant with for ; set and . These choices depend only on the rewards. For every , we claim
To prove it, note that for , the bound holds as ; for , it uses the fact that and triangle inequality. Therefore, these approximants form a subset of all adjacent pairs with (we will use them later in § 4.2). There are at most of them, and the union bound at level runs over these pairs. Define
For , we have , with and . Because and , the additive constant is at most . Hence
The same bound holds for because . Since and , it follows that
The sample-size condition implies for every .
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 be i.i.d. copies of supported in an interval of length , with . Write , , , and . For , the following bounds have failure probabilities at most and , respectively:
They hold jointly with failure probability at most .
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 ; These bounds require and , and every sample-size condition below ensures them.
Lemma 4.3 (Simultaneous concentration of adjacent value increments). With probability at least , the following inequalities hold simultaneously for all , all adjacent reward pairs satisfying , and all state–action pairs:
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 is deterministic and satisfies . Let be the samples at , and apply Lemma 4.2, with and ; . Since and are probability vectors, the shift changes neither nor the standard deviations, and the empirical standard deviation of the is . Inequality (7) therefore implies
with failure probability at most 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 . We modify the empirical MDP by making absorbing and giving all its actions reward , where . Other states retain reward . Write for its optimal value. This vector is independent of all empirical transition rows at state . It equals at state . It also satisfies
The first identity is [6 Lemma 8]. The second extends their boundary Lipschitz bound to two different rewards: let be the norm on its left. At , the difference is ; outside , the Bellman inequality bounds it by . Hence , which implies the displayed bound.
Now consider with and define the proxy difference . Since , (11) implies . Conditional on all data outside state , this is a fixed function independent of the samples at . Bernstein’s inequality consequently implies
with conditional, and hence unconditional, failure probability at most . We note the numerical constant 8 is conservative: the range length is at most .
Then we choose grid points within of and , respectively. The two exact boundary values differ by at most , so this grid pair is among those considered. Equations (10)–(11) give
Therefore , and by the triangle inequality in centered . Since , we have
which implies (9). A union bound over at most true-value events, each failing with probability at most , and at most empirical-proxy events at level , each failing with probability at most , has total failure probability at most
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 be an stochastic matrix, let , and for define
Let and let satisfy . If and , then
In particular, if and , then .
Proof. Note that has nonnegative entries [25] and satisfies . In particular, it preserves coordinatewise inequalities.
The relation implies . Hence
Specifically, it is from bounding three terms. First, , because and . Second, . Third, : multiplying by preserves its direction, and together with implies the inequality.
Apply and use :
This proves the first claim. For each state , the weights are nonnegative and sum to , so the Cauchy–Schwarz inequality implies
Multiplying by and using the first claim implies . Both and are nonnegative, so taking square roots and the maximum over proves the second claim.
For the last claim, take , , and . Then and 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 and be two transition kernels. Denote the optimal values of the base kernel . For each target , one can choose a deterministic stationary policy that is optimal for in , and define
Then we have , , and . Define the finite nonnegative quantity
Lemma 4.5. Let be as in Section 4, so that by (5). Suppose that, for all targets , all levels , and all state–action pairs,
Then
and for every .
Proof. We first bound the resolved variance of each tail . We then sum the increment concentration bounds and absorb the resulting term proportional to .
The Bellman inequality controls every tail. Fix a target and level and abbreviate and . The reward Lipschitz property implies . Optimality of for and Bellman optimality of imply that
Subtracting shows . Moreover, note that the shift satisfies and, because , we have
Apply Lemma 4.4 with , , , and . Since is stochastic, . Since , the definition of implies . Therefore we have that
This argument also holds at , where , , and , and trivially at , where .
Increment bounds close the comparison. Since , the centered- triangle inequality and imply that
Use the tail representation of each , the nonnegativity of , and (12) at the rows . These rows give . Enlarge every tail sum to the full sum; all summands are nonnegative. After taking the maximum defining , we obtain
The second inequality uses (5); the third uses the geometric-sum bounds and . Finally, Young’s inequality implies
Plugging it in (15) then proves (13).
The comparison controls policy evaluation. For the last claim, write . Subtracting from implies , thus we have that
Since has nonnegative entries, for every vector . Hence is at most the level-zero term in the definition of . □
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 and (inequality (9) verifies its hypothesis hence we can apply it). Let 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
and the last claim of Lemma 4.5 bounds its norm by . Hence , where
Apply the same lemma with and . Inequality (8) verifies its hypothesis. For a true optimal policy , the lemma implies .
For each target reward and state, empirical optimality implies
The sample-size condition, , and imply
Thus every finest-net target has true policy loss at most $\varepsilon/2.
Finally, for an arbitrary query reward , choose at distance at most and return . For any fixed policy, changing the reward by at most changes every discounted value by at most . The same bound holds for optimal values by (3). Consequently, we have that
Namely, the output policy is -optimal under . All these events were simultaneous over the finite sets used to answer every query, and the bounds hold for every admissible choice of 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 , and therefore supplies the state-dimension saturation for the reward-hull upper bound.
Theorem 5.1 (Uniform planning). Let , , and . Set , and define
If independent transitions are collected at every state--action pair and
then, with probability at least , for every reward , every empirical optimal deterministic stationary policy is -optimal in the true MDP at every state. In particular, the total sample is
The proof applies the same one-sided variance comparison to a grid of all value vectors in . 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 , 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 , , and . At a decision state , every action returns to with probability and otherwise exits to an absorbing state according to a distribution . Let the known immediate reward at be , and let the reward at be a known number and zero at every other action. Set
Then, for every randomized history-dependent policy started from , there is a probability vector determined by the policy and the known rewards, independently of the distributions for a fixed policy, such that
Proof. Let be the probability of choosing action at time conditional on remaining at through time . Before exit, the observed state is always , the rewards are known functions of the chosen actions, and each action has the same survival probability. Thus is a functional of the policy that does not depend on the unknown exit distributions. Define
The geometric series sums to , so is a probability vector. A visit to contributes the immediate reward and the expected discounted reward after exit, . Since , summing these contributions implies the value identity. Every policy therefore implies a convex combination of the , and a stationary action maximizing attains the upper endpoint.
Lemma 6.2. For every even integer , there is a set such that each vector has positive entries and
Proof. Apply the greedy Gilbert packing argument [28] to the balanced vectors. A Hamming ball of radius in the full cube contains at most vectors, where . Consequently the selected set has logarithmic size at least
The last inequality holds for : the first coefficient exceeds , and decreases on this range and is less than at .
Lemma 6.3. Let be even, let , let , and write
Consider a family with an integer of independently indexed unknown transition rows. Each such row self-loops with probability and exits with probability according to its distribution ; all other rows are fixed throughout the family. If a learner using at most adaptive simulator queries produces an output from which all codewords can be decoded with probability at least in every model, then
Proof. Give the parameter vector the uniform prior on . For a fixed parameter vector , compare the learner’s transcript with the reference model in which every unknown exit distribution is replaced by . One query to an unknown row has relative entropy at most
Here follows from . The adaptive relative-entropy chain rule [29 Lemma 15.1] implies
where 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 , so
The middle inequality uses . Rearranging proves the claim.
The multi-objective lower bound
The next construction uses objectives for subset tests and only additional objectives to select an action pair.
Theorem 6.4 (Lower bound with additive objective budget). Let , , and
Let , let be even, and assume and . For , , and , there is a family of discounted MDPs with states, actions, and known reward functions in for which every learner satisfying (1) with probability at least in every model requires
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 and absorbing outcome states ; any additional states are absorbing with zero rewards. At each decision state, pair the first actions as , . Every action self-loops with probability , where . Conditional on exit, action uses , and action uses . Here
When is odd, the remaining action duplicates in both its transitions and its known rewards.
To make a preference select one pair, apply Lemma 6.2 in dimension . Since and , it provides balanced binary vectors , obtained by replacing signs by zeros and ones. Each vector has ones, and any two differ in at least coordinates. Therefore satisfies
Indeed, equal Hamming weights imply that two distinct vectors share at most coordinates equal to one.
Defining simplex preferences that isolate a pair. The first reward coordinates are action rewards:
One further coordinate is supplied for each subset :
All remaining coordinates are zero. These known rewards lie in and are identical in every environment.
For pair and subset , use the simplex preference
with zero entries in unused coordinates. Lemma 6.1 expresses the value at through the effective rewards
Here and for the fixed decision state . Both target actions have effective reward at least , whereas every other pair has effective reward at most
The maximum effective reward is attained within the target pair. If the extra duplicate exists and , 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 and distinct . Set
Balance and separation give , and
For preference the optimal target action therefore changes when the row changes from to . Their stationary value gap in either model is at least
using and .
Let be the occupancy functional of the output policy from Lemma 6.1, at this preference and initial state. If the row is , every other action has effective reward at most that of the target reference action. Consequently its value loss is at least , and -optimality requires . If the row is , the value loss is at least , so . These are restrictions on the same model-independent functional of the learned policy.
Decode row by selecting the codeword whose policy at has for every ; 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 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 . Substituting and implies
This thus completes the proof.
Since , choosing of order and implies the desired factor when and that minimum is sufficiently large. Appendix C implies a related construction that uses only pure preferences and has objective budget .
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 , , , , and . If , every learner that uses at most adaptive generative-model queries and satisfies (1) with probability at least on every instance must satisfy
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 . In Theorem 4.1, the definitions give
for universal constants . To check these estimates, note that dominates , , , and in the stated range . Also , so the displayed upper bound on implies the second estimate. Since , the terms of not containing can be included in its right-hand side. Therefore the chaining algorithm uses at most
samples. The ceiling adds at most , which is absorbed by this bound. Theorem 5.1, whose logarithmic term satisfies , implies at most
samples. Choose the algorithm with the smaller displayed sufficient sample count. Since , the minimum is at most .
For the lower bound, write and use the action-code length
Suppose first that and . Define
The assumptions imply : the state term has this property, while and the large lower bound on imply . Hence , is even, and . Moreover . Theorem 6.4 applies, and yields
If , Theorem 6.5 implies the same conclusion after decreasing the universal constant: for , and the factor is bounded by 512. The remaining case has and . Then
The scalar lower bound consequently implies
This proves the universal lower bound. When , only the first two cases are needed, and the denominator is absent. Since , 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 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 . The displayed sample condition implies . For every fixed and every row, apply Lemma 4.2 with to , where are the samples at that row. On an event with failure probability at most , it implies the following bound; for this is (7), and for it follows from (6) because and :
A union bound makes these statements simultaneous over rows and grid points with failure probability at most . For any , choose with . The row error changes by at most , and the triangle inequality for centered implies . Consequently, on the same event,
All inequalities here are coordinatewise.
We next prove a deterministic evaluation comparison that can be used in either direction. Let be either or . For any reward , let and let be a deterministic stationary optimal policy in the base kernel . Define
The vector satisfies . Its Bellman equation in the base model implies the one-sided bound
Lemma 4.4, applied with , , and , for which because , implies
Apply to (19) with the variance taken under (the true variance when , the empirical variance when ), evaluated at the rows . By the row convention, this implies
Young’s inequality bounds the second term by . Rearranging therefore implies
By the definitions of and , and since ,
The exact policy-evaluation identity bounds the difference between and the value of under by .
Apply this comparison to a true optimal policy and then to an empirical optimal policy, using opposite choices of . 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 . Here the two errors use different policies and resolvents, and each is bounded by . The concentration event covers every vector in , so both comparisons hold for every reward and every corresponding optimal policy simultaneously. Finally, , which implies the stated sample-complexity bound. ∎
The scalar change-of-measure argument
Proof of Theorem 6.5. Let decision states share two absorbing states and . The first objective rewards one at and zero elsewhere; all other objectives are zero. We use preference . Every action at a decision state exits with probability and otherwise self-loops. Conditional on exit, it selects with probability and otherwise.
The null model has for every row. Alternative changes only that row to , with . Lemma 6.1 implies
Here is a model-independent probability vector determined by the output policy at . In alternative , the value gap to every other stationary action is . An -optimal output must therefore have .
For fixed , the output events are disjoint. Thus at least actions satisfy , while the success requirement in their respective alternatives implies . 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
Only queries to row differ between the experiments. Their null-to-alternative divergence satisfies
The first inequality uses , and the second uses . The preceding change-of-measure inequality therefore implies
Summing over at least selected rows and using the maximum query budget implies
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 , let , and let be even. Suppose and . For , , and , there is a family of discounted MDPs with states, actions, and known reward functions in for which every learner satisfying (1) with probability at least in every model requires
The conclusion allows adaptive simulator queries and arbitrary randomized history-dependent output policies.
Proof. Write , and use the balanced code of Lemma 6.2. Set and . As in the main construction, take decision states and absorbing outcome states . Any additional states are absorbing with zero reward. Actions are . At , every action self-loops with probability . Conditional on exit, action uses , and action uses , where .
For each and , provide the known reward coordinate
Pad unused reward coordinates with zero. These rewards lie in , and we use only their pure simplex preferences . Lemma 6.1 implies the effective rewards
The target actions have , whereas every other action has . Thus all other unknown rows are irrelevant to the optimal comparison.
For distinct codewords , take . Its size is at least , and and equal respectively and . The two target stationary actions exchange optimality, with value gap at least
The occupancy of the learned policy must therefore satisfy when the row is , and when it is . This follows directly from the convex-combination value formula: the losses are at least and , respectively.
For each row , decode a candidate precisely when its output policies satisfy at every preference ; 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 codewords. Lemma 6.3 implies
Taking an even below both and , and setting , yields
when the indicated minimum is sufficiently large. In particular, for fixed this is the dependence. The main construction improves its objective budget by using mixed preferences to encode the target action pair.
References
- [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]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]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]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]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]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]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]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]Z. Chen and Z. Zhang, “Optimal multi-reward reinforcement learning,” arXiv preprint arXiv:2609.36486, 2026.arxiv.org/abs/2609.36486
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
- [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]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]E. N. Gilbert, “A comparison of signalling alphabets,” The Bell system technical journal, vol. 31, no. 3, pp. 504–522, 1952.DOI
- [29]T. Lattimore and C. Szepesvári, Bandit algorithms. Cambridge University Press, 2020.
- [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.