# Adaptive Exploration for Multi-Reward Multi-Policy Evaluation

arXiv: https://arxiv.org/abs/2502.02516 · HTML: https://mlsanity.com/paper/2502.02516/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 4 Feb 2025.

## Builds on (most cited first, 27 of 27)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Personalizing Reinforcement Learning from Human Feedback with Variational Preference Learning](https://mlsanity.com/paper/2408.10075/) (2024)
- [Explainable Reinforcement Learning: A Survey](https://mlsanity.com/paper/2005.06247/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Data-Efficient Policy Evaluation Through Behavior Policy Search](https://mlsanity.com/paper/1706.03469/) (2017)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling](https://mlsanity.com/paper/2203.04510/) (2022)
- [Policy Gradient with Active Importance Sampling](https://mlsanity.com/paper/2405.05630/) (2024)
- [Continual Auxiliary Task Learning](https://mlsanity.com/paper/2202.11133/) (2022)
- [On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure](https://mlsanity.com/paper/2211.15129/) (2022)
- [Model-Free Active Exploration in Reinforcement Learning](https://mlsanity.com/paper/2407.00801/) (2024)
- [Explainable Reinforcement Learning via Temporal Policy Decomposition](https://mlsanity.com/paper/2501.03902/) (2025)
- [Multiple-policy Evaluation via Density Estimation](https://mlsanity.com/paper/2404.00195/) (2024)
- [Adaptive Exploration for Data-Efficient General Value Function Evaluations](https://mlsanity.com/paper/2405.07838/) (2024)

## Built on by (most cited first, 6 of 6)

- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)
- [Improved Bounds for Reward-Agnostic and Reward-Free Exploration](https://mlsanity.com/paper/2602.16363/) (2026)
- [Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning](https://mlsanity.com/paper/2607.17201/) (2026)
- [The geometry of AI validation: From structural blindness to reusable audits](https://mlsanity.com/paper/2608.21496/) (2026)
- [ICMAPE: In-Context Multiagent Pure Exploration](https://mlsanity.com/paper/2609.33986/) (2026)

## Abstract (arXiv)

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