Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
This addresses the problem of efficiently evaluating multiple policies across different reward functions for reinforcement learning practitioners, though it is incremental as it builds on prior work.
The paper tackles the policy evaluation problem in an online multi-reward multi-policy discounted setting, achieving ε-accurate estimates with high confidence across finite or convex reward sets, with experiments demonstrating effectiveness in tabular domains.
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.