This paper develops a theoretical framework to understand the sample complexity of offline Pareto extraction when specialists are imperfect. It establishes lower bounds and proposes Pareto-PEVI, an algorithm achieving these bounds, revealing the bias-variance tradeoff introduced by specialist imperfection.
Key findings
Developed the first theoretical framework for sample complexity in offline Pareto extraction with imperfect specialists.
Established information-theoretic lower bounds showing that extracting an ε-approximate Pareto front requires Ω(MC⋆/ε2) samples.
Proposed Pareto-PEVI, an algorithm achieving the lower bound up to logarithmic factors.
Analyzed the impact of specialist imperfection on sample complexity and extraction quality.
Validated theoretical predictions through comprehensive experiments on multi-objective MuJoCo benchmarks.
Limitations & open questions
The analysis assumes the use of tabular MDPs, which may not generalize to all environments.
The study focuses on the pessimism principle, potentially overlooking other strategies for handling specialist imperfection.