Research map / Reinforcement learning / MDPs and planning
Multi-Reward Best Policy Identification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines multi-reward best policy identification (MR-BPI), derives an instance-specific sample complexity lower bound and a convex relaxation, proposes MR-NaS for tabular MDPs and DBMR-BPI for deep RL.
Problem
Identifying the best policy for every reward in a known finite or continuous set of rewards with minimal samples and a fixed confidence level (δ-PC), in MDPs with unknown transitions.
Approach
Extends the single-reward BPI lower bound (Track-and-Stop / NaS style) to a set of rewards, derives a convex upper bound (relaxed characteristic rate) over allocations, and uses it to drive exploration: MR-NaS in tabular MDPs and DBMR-BPI (bootstrapped Q-ensemble over all rewards, sampling rewards by inverse squared gap) in deep RL.
Key results
- On tabular environments, MR-NaS reaches low estimation error quickly across RiverSwim, ForkedRiverSwim, DoubleChain and NArms, compared with RF-UCRL, ID3AL and MR-PSRL (50 seeds, 50k steps).
- On Cartpole swing-up (k=3, 150k steps), DBMR-BPI achieves average reward statistic 21.3 vs 1.3 for RND, 0.3 for APT and 0.9 for Disagreement on base rewards.
- On DeepSea N=30, DBMR-BPI reaches a geometric mean reward of 3.1, comparable to RND (1.8) and above APT (0.0) and Disagreement (0.0) under the reported metric.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DBMR-BPI instead of RND | Deep RL exploration · Cartpole swing-up, k=3, base rewards R | E[AvgR({Xi})]: 21.3(20.6, 21.9) vs 1.3(1.0, 1.6) | Helped |
| Use DBMR-BPI instead of RND | Deep RL exploration · Cartpole swing-up, k=5, base rewards R | E[AvgR({Xi})]: 20.2(19.6, 20.6) vs 1.2(0.9, 1.5) | Helped |
| Use DBMR-BPI to explore the base reward set | DBMR-BPI · Cartpole swing-up, random rewards Rrnd | E[AvgRrnd({Xi})]: 23.1(22.2, 24.2) vs 1.4(1.1, 1.7) | Helped |
| Use DBMR-BPI instead of RND | Deep RL exploration · Cartpole swing-up, k=5, random rewards Rrnd | E[AvgRrnd({Xi})]: 22.3(21.5, 23.1) vs 1.1(0.9, 1.4) | Helped |
| Use DBMR-BPI instead of RND | Deep RL exploration · DeepSea, N=20, base rewards R | E[GMR({Xi})]: 4.6(4.6, 4.6) vs 4.6(4.2, 4.7) | No clear effect |
| Use DBMR-BPI instead of RND | Deep RL exploration · DeepSea, N=30, base rewards R | E[GMR({Xi})]: 3.1(2.9, 3.2) vs 1.8(1.3, 2.2) | Helped |
| Use DBMR-BPI instead of RND | Deep RL exploration · DeepSea, N=20, random rewards Rrnd | E[AvgRrnd({Xi})]: 8.9(8.5, 9.2) vs 8.7(8.4, 9.1) | No clear effect |
| Use DBMR-BPI instead of RND | Deep RL exploration · DeepSea, N=30, random rewards Rrnd | E[AvgRrnd({Xi})]: 6.0(5.8, 6.3) vs 6.1(5.9, 6.4) | No clear effect |
| Explore according to the difficulty of each reward, with probability proportional to 1/∆²t,r | DBMR-BPI · Multi-reward Deep RL | exploration performance | Mixed |
Surprising findings
- Sampling rewards by inverse squared gap and learning Q-values for all rewards jointly was reported as more effective than feeding a one-hot reward encoding to the network.
- DBMR-BPI collected more reward from unseen random rewards in Cartpole than from the base training rewards.
Limitations
- Theory applies only to tabular MDPs; deep RL extension has no theoretical guarantees.
- Assumes a unique optimal policy per reward and a finite action space for DBMR-BPI.
- Computing the allocation at every step may be prohibitive for large problems; scalability to many rewards untested.
Experimental setup
Datasets: RiverSwim ForkedRiverSwim DoubleChain NArms DeepSea (bsuite) Cartpole swing-up (bsuite) link adaptation simulator
Benchmarks: RiverSwim ForkedRiverSwim DoubleChain NArms DeepSea Cartpole swing-up link adaptation
Metrics: fraction of misidentified policies (estimation error) average reward collected per reward function geometric mean reward number of unvisited cells
Baselines: RF-UCRL ID3AL MR-PSRL RND APT Disagreement
Builds on: NaS (MDP-NaS) DBMF-BPI Track-and-Stop RF-UCRL PSRL
Closest papers by meaning
- Adaptive Exploration for Multi-Reward Multi-Policy Evaluation (ICML 2025 · similarity 0.91)
- Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning (NeurIPS 2026 · similarity 0.91)
- Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs (ICLR 2023 · similarity 0.90)
- Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration (NeurIPS 2023 · similarity 0.89)
- Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Reward-Free Kernel-Based Reinforcement Learning (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.