acceptodds
Under review as a conference paper at ICLR 2027

Optimal Multi-Reward Reinforcement Learning

Abstract

We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions . The goal is to output an -optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error where represents the reward function and . Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of episodes, with no additional burn-in cost. This matches the information-theoretic lower bound up to a factor of . Our method combines three technical ingredients. First, we adapt MVP to reward-switching learning to construct optimistic value estimates. Second, we use fresh replay samples to conservatively evaluate the candidate policies. Third, gap-based multiplicative weights updates adjust the reward-sampling distribution using the differences between these estimates, converting weighted learning progress into simultaneous guarantees for all rewards.

Primary area:
learning theory
Keywords:
Reinforcement Learning, Multi-Reward, Optimal Sample Complexity, no burn-in term, finite-horizon tabular MDP

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_Lu99OpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies online reinforcement learning in tabular episodic Markov decision processes (MDPs), where the goal is to learn a near-optimal policy for each reward function in a finite collection. The collection of reward functions is known to the learner in advance. The paper proposes an algorithm that achieves minimax-optimal sample complexity without additional burn-in costs.

A closely related problem is reward-free (or reward-agnostic) exploration, where the reward functions are unknown to the learner during the data collection phase.

Critical strengths
  1. The theoretical result is strong. To the best of my knowledge, this is the first work to achieve minimax-optimal sample complexity without additional burn-in costs in the studied setting.

  2. The problem setup and theorem statements are clearly presented. The introduction is well written and provides an accessible overview of the research landscape, effectively positioning the paper within the existing literature.

Critical weaknesses

There is no critical weaknesses of the paper. In the questions for authors section, I have listed clarification questions that could, if addressed, potentially improve the quality of the paper.

Questions for authors
  1. Is the multi-reward setting studied in this paper novel? More importantly, is there a fundamental difference between the reward-agnostic setting, where the collection of reward functions is unknown during data collection, and the multi-reward setting, where this collection is known in advance? Since reward-agnostic exploration already achieves minimax-optimality in terms of the leading sample complexity term, do the authors believe that eliminating the burn-in cost is also possible in this more challenging setting, or might there be an information-theoretic barrier?

  2. Table 1 identifies some prior works as studying "reward-free exploration." Should the reward-agnostic setting also be explicitly identified for Zhang et al. (2020), Li et al. (2026), and Ridel & Cohen (2026)? Clarifying the distinctions among these settings would make the comparison more informative.

  3. Judging from Table 1, the sample complexity bound of Zhang et al. (2020) does not appear to contain a burn-in term with higher-order dependence on S and H. Is this because such a term is omitted from the reported bound, or does their result genuinely avoid this burn-in cost? If the latter is true, how does their result differ from the claimed contribution of the present paper?

  4. The introduction does not clearly explain what gives rise to the burn-in term or why eliminating it is difficult. Is there an existing line of research specifically focused on reducing or eliminating burn-in costs? What are the main technical obstacles, and how does the proposed approach overcome them?

  5. The paper builds on the MVP framework of Zhang et al. (2021), which is appropriately acknowledged. However, the main paper does not explain this framework in sufficient detail to distinguish the existing techniques from the new contributions. Could the authors provide a more detailed overview of the MVP framework and explicitly identify the algorithmic modifications and technical challenges specific to the multi-reward MDP setting?

  6. Could the authors elaborate on why conservative evaluation, which shrinks the continuation value rather than adding an exploration bonus, is necessary for establishing the proposed sample complexity bound? In particular, which part of the theoretical analysis requires this design choice, and what would fail if a more conventional bonus-based approach were used? I think it is addressed in the paragraph starting in line 348, but it is hard to understand fully from this paragraph. In my opinion, this is the most interesting technical contribution, and discussing this clearly in the main paper would significantly improve the quality of the paper.

Reviewer_Z6RUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper learns near-optimal policies for many known reward functions at once in an unknown tabular MDP. It shares one transition model across rewards and reweights rewards that remain uncertain. It needs only a log⁡M\log M factor more episodes than single-reward learning, with no extra burn-in, and a lower bound shows this is optimal in a stated regime.

Critical strengths

The paper looks at a clear and useful question: what is the cost of supporting MM known rewards in one environment? It avoids a factor of MM while still keeping the burn-in-free SAH3/ϵ2SAH^3/\epsilon^2 rate (Theorem 1). It also shows that the log⁡M\log M dependence is optimal when log⁡M≲S\log M\lesssim S.The proof technique is interesting, but I wish the explanation was a bit easier to follow.

Critical weaknesses
  • The log⁡M\log M saving hides extra costs that the paper does not discuss. Computation and memory both grow linearly with MM. Specifically, Algorithm 2 replans all MM rewards every episode (line 7) even though the model only changes at doubling triggers, and it stores MM mixtures of KLKL policies.

*The paper also lacks any runtime or memory numbers, as well as a basic "MM separate MVP runs" baseline to show the practical benefit.The experiments do not match the algorithm as stated. With the chosen constants, the exploration bonus exceeds HH at every tested budget, so all optimistic values just clip to HH.

*Also, all four baselines are reward-free methods, and a uniform-weight ablation is missing.

Some important related works are missing. Russo & Vannella (2024) study the same multi-reward setting, and Wu, Braverman & Yang (2021) are an earlier work on multi-objective RL.The primary learner is from MVP 2025 (Zhang, Chen, Lee & Du) and should be credited.

Questions for authors
  • Each episode samples only one reward, so rewards with low weights get very few episodes. Does any term in the analysis grow with MM or 1/pℓ(m)1/p_\ell(m)? How much do the per-reward certificates vary in practice, and what are the runtime and memory costs as functions of MM?
  • What exact settings were used for Figure 1 (KK, LL, δ\delta, bonus constants, warmup size, and tie-breaking)? How is clipping to HH avoided?
  • At a matched episode budget, how does the method compare with MM independent MVP runs and with uniform reward weights?
Reviewer_1wsMOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to learn a near-optimal policy for each of several known reward functions that share unknown transition dynamics. It combines shared-model learning, conservative policy evaluation, and adaptive reward selection to achieve a sample complexity of O(SAH3log⁡M/ϵ2)O(SAH^3\log M/\epsilon^2).

Critical strengths

The paper provides a clear theoretical advance in multi-reward learning, achieving a sample complexity of O(SAH3log⁡M/ϵ2)O(SAH^3\log M/\epsilon^2). It also establishes a lower bound, matching the upper bound up to logarithmic factors when log⁡M≤S\log M\le S. The technical contribution extends beyond applying single-reward MVP separately to each reward. Sealed replay and a count-dependent shrinkage evaluator control both conditional evaluation bias and cumulative overestimation. These properties derive a multiplicative-weights analysis with signed estimation gaps, changing weighted learning into theoretical guarantees for every reward.

Critical weaknesses
  1. The related-work discussion omits Russo and Vannella "Multi-Reward Best Policy Identification" (NeurIPS 2024), which directly studies online policy identification for a known collection of rewards. Although its settings and results are little different, this distinction should be explicitly discussed. Other than this, The paper should discuss the extension of that result to multiple rewards from improvements over existing multi-reward methods. I believe there are much more papers to discuss with it. Also, while previous studies of single-reward MVP provides an technical foundation, its guarantee does not address dependence on the number of rewards. Table 1 should therefore more clearly position the proposed method against approaches that exploit a known reward collection.

  2. The logarithmic dependence on MM concerns environment interactions, whereas the prescribed algorithm evaluates all KMKM candidates in each phase and episode. With KK learning episodes and LL phases, I think the algorithm requires approximately O(KLMHS2A)O(KLMHS^2A) arithmetic operations, and retaining the histories of policy also requires O(KLMHS)O(KLMHS) action entries, in straightforward thought. These costs grow with both the reward count and the number of learning episodes. Without runtime and peak-memory measurements, larger-scale experiments, or a method for compressing the policy collection, it remains unclear whether the statistical improvement translates into a practically usable algorithm.

  3. minor. In extension to weakness 2, following the theoretical analysis is made more difficult by the dense notation across phases, episodes, rewards, and stages. The algorithm maintains several closely related value estimates, transition models, and visit counts whose roles are difficult to track. A clearer overview of these quantities and more consistent notation would improve both readability and reproducibility.

Questions for authors

The experiments are limited to small toy problems. Many real-world multi-reward problems require a policy that balances several objectives, meets constraints, or reflects user preferences. This paper focuses on learning a separate policy for each given reward.

  1. Could the authors give any concrete example where users need a separate policy for each reward? I am asking for some real application examples and an explanation of how these policies would be used. If there is any example, is the proposed algorithm applicable to it?

  2. If a user wants to maximize a weighted sum (or any preferences) of the rewards, does the method guarantee a near-optimal policy for that weighted sum? Does the weighted sum need to be added as a new reward before learning, or can the learned policies support weights chosen after learning?

Introduction says that the previous studies typically focus on a single reward function, an assumption that is restrictive in many applications, so the above questions must be clarified.

Reviewer_MaQeOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies simultaneous policy learning for M known reward functions in a finite-horizon, time-inhomogeneous tabular MDP with unknown shared transition dynamics. The objective is to return a separate ϵ\epsilon-optimal policy for every reward, simultaneously with high probability, using online episodic interaction. The proposed algorithm combines a shared-model version of MVP with adaptive reward sampling. In each phase, it constructs candidate policies for every reward, executes policies for sampled rewards, and then collects fresh data by replaying each executed policy eight times. A conservative evaluator shrinks continuation values by a count-dependent factor instead of subtracting a conventional pessimistic bonus. Multiplicative weights then increases the sampling probability of rewards with larger optimistic-versus-evaluated value gaps. The output for each reward is a uniform, episode-level mixture of its candidate policies. The main theorem establishes an episode complexity of $ O\left( \frac{SAH^3\log M}{\epsilon^2} \log^4\frac{SAH\log M}{\min{\epsilon,1}\delta} \right), $ including replay episodes and without an additional polynomial burn-in term. Appendix F gives a lower bound of $ \Omega\left( \frac{SAH^3\min{S,\log M}}{\epsilon^2} \right) $ under additional parameter restrictions. Experiments on small random MDPs compare worst-reward policy error and estimated episode requirements against four exploration baselines.

Critical strengths

Extending a burn-in-free single-reward guarantee to a known finite reward class with logarithmic dependence on its cardinality is a worthwhile theoretical contribution. The starting single-reward MVP result already provides an all-range guarantee; the additional challenge here is allocating exploration and certifying performance across rewards. The paper addresses that challenge rather than simply applying a union bound to independent learners.

The conservative evaluator is technically interesting: for the auxiliary fixed-prefix construction, shrinking the continuation value by n/(n+1)n/(n+1) supports the bound. Together with the weighted bias bound, this provides exactly the type of cumulative control needed by the outer algorithm. Avoiding a requirement of high-probability pessimism in every phase is an insightful way to reduce evaluation cost.

The analysis takes the important adaptive dependencies seriously. The learning model persists across phases, and future reward weights depend on previous replay outcomes. Appendix D constructs concentration events uniformly over profiles and candidate values to accommodate this dependence. The treatment of recorded initial states and episode-level policy mixtures also addresses details that could otherwise invalidate the final PAC guarantee.

The lower bound respects advance knowledge of the rewards. Appendix F constructs a reward class independent of the hidden transition indices and explicitly reveals it before exploration. The localization rewards force policies to solve designated time–leaf problems, after which simultaneous near-optimality permits decoding the hidden indices. This is stronger and more relevant than simply importing a lower bound whose difficulty depends on rewards being withheld.

Critical weaknesses
  1. The auxiliary replay process and the scope of the conditional guarantees need a precise statement. Algorithm 3 uses the actual count $ \widetilde N_{\ell,h}(s,a) =\min{T_{\ell,h,s,a},N_{\ell,h}(s,a)}, $ which can fall below its target. In contrast, the proofs of Lemmas 17 and 18 use fixed prefixes containing exactly Nℓ,h(s,a)N_{\ell,h}(s,a) independent transition samples. This distinction matters. In the implemented replay process, downstream visit counts can depend on upstream transition outcomes. Freshness relative to the learning history does not, by itself, establish the stage-wise independence used in the backward conditional-expectation argument. Appendix C.4 appropriately proposes intersecting with replay success only after deriving the moment bounds. However, the auxiliary execution should be defined before these proofs, including how it completes unavailable prefixes and how its evaluations affect subsequent weights and policies. Lemmas 4 and 5 should then explicitly distinguish auxiliary guarantees from guarantees transferred to Algorithm 1. I regard this as a formalization gap, rather than an established counterexample to Theorem 1.

  2. The experimental implementation is insufficiently specified and appears to involve undocumented modifications. Appendix E mentions an “initial random warmup,” which is absent from Algorithm 1. Its episode-accounting discussion mentions warmup and subsequent learning, but does not explicitly enumerate the sealed replay episodes, even though these account for eight ninths of the analyzed interaction budget. The PDF also does not specify the experimental choices of K,L,δK,L,\delta, bonus constants, warmup length, or handling of incomplete phases under a fixed budget. It is unclear whether evaluation uses the prescribed uniform mixture or a different extracted policy. The statement that supplementary code exists is helpful, but that code was not among the supplied files. Consequently, the numerical results cannot yet be confidently attributed to the exact analyzed algorithm.

  3. The headline optimality claim needs more visible qualifications. Theorem 1 covers a broader parameter range than Corollary 1. The latter requires, among other conditions, $ H\ge4(1+\lceil\log_2 S\rceil),\qquad \epsilon\le1/192,\qquad M\ge(CSHA^2)^2, $ together with restrictions on SS and AA. Furthermore, the displayed upper bound matches the lower bound’s reward dependence when log⁡M≤S\log M\le S. For larger classes, a reward-free method provides the relevant SS-saturated upper bound. The manuscript acknowledges this saturation in Footnote 2, but the abstract and discussion should communicate the scope of “optimal” more accurately. The remaining lower-bound restrictions should also be summarized near the main result.

  4. The experiments provide limited evidence about which ingredients help. All experiments use one small configuration, S=10,A=5,H=6S=10,A=5,H=6, with full-support random transitions and action-independent immediate rewards. This is a reasonable sanity check, but it does not test difficult coverage patterns, rare states, or substantially different horizons. More importantly, the comparisons do not isolate the proposed mechanisms. Useful controls would include uniform reward sampling with the same shared model, separate reward-specific MVP learners, and an ablation of the conservative evaluator. Comparisons against reward-agnostic algorithms alone cannot establish how much improvement comes from adaptive weighting, shared learning, or access to the reward class. These additions would strengthen the empirical interpretation; large-scale application experiments are not essential for this primarily theoretical paper.

  5. The distinction from reward-agnostic learning requires sharper definitions. The introduction emphasizes advance knowledge of all reward functions as the distinguishing feature. However, Section 3 of https://proceedings.mlr.press/v247/zhang24a.html explicitly states that the learner knows the predefined reward class. The paper should distinguish knowledge of the class, knowledge of the eventual selected reward, and an exploration procedure that does not use reward values. This affects both the framing of the contribution and the remaining open problem stated in Section 6, although it does not by itself negate the sample-complexity improvement.

  6. Computational and storage costs are largely unaddressed. Logarithmic dependence on MM applies to environment interaction. The algorithm still computes candidate policies for every reward and retains KLKL policies per reward. An explicit runtime and memory analysis would help readers assess the meaning of “efficient,” particularly when MM is large. It would also be useful to discuss whether the output mixtures can be compressed without materially weakening the guarantee.

Questions for authors

Can you explicitly define the auxiliary replay execution before Appendix C.2, restate Lemmas 4 and 5 for the appropriate process, and prove agreement with Algorithm 1 inductively across phases on the quota-success event?

What exact experimental settings were used for K,L,δK,L,\delta, the bonus constants, warmup, replay, and policy extraction?

Can you add uniform-reward-sampling and separate-MVP baselines, together with an evaluator ablation, using comparable tuning procedures and total interaction budgets?

Which lower-bound restrictions are essential? In particular, can the explicit log⁡M\log M dependence be established below M≥(CSHA2)2M\ge(CSHA^2)^2, or should the headline optimality claim be restricted accordingly?

Precisely what information about the reward class is unavailable in the reward-agnostic setting used for your comparison?

What are the algorithm’s runtime, peak memory requirements, and output-policy representation costs?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.