Batch Active Preference-Based Learning of Reward Functions

1 Introduction

• The approach targets costly robotics data collection, where people may struggle to assign rewards or provide demonstrations and continuous-space query synthesis can be inefficient.Source: §1 · p. 1
• The algorithm generates batches of comparison pairs from labeled data to balance query count against query-generation time.The framework synthesizes and queries b pairs at once.Source: §1 · p. 1
• The work develops approximation algorithms for batch active preference learning and formalizes the query-count versus generation-time tradeoff with convergence guarantees.Source: §1 · pp. 1–2
• The authors compare approximation methods on complex preference-learning tasks and demonstrate preference prediction for autonomous driving and ball tossing.Source: §1 · p. 2

2 Problem Statement

• A feasible trajectory consists of continuous state and action pairs over a finite horizon and must satisfy the system dynamics.Source: §2 · p. 2
• The preference reward function assigns real-valued scores to feasible trajectories and is modeled as a linear combination of trajectory features.Source: §2 · p. 2
• The preference model treats user responses as potentially noisy, with a softmax function given as a common noise model.Source: §2 · p. 2
• Active preference learning synthesizes pairwise queries over continuous trajectory space to learn preferences, avoiding reliance on demonstrations that can be difficult for high-degree-of-freedom robots.Source: §2 · p. 2
• Batch active learning presents multiple queries together to balance query count and generation time, and batches can be parallelized when personalized collection is unnecessary.Source: §2 · p. 3

3 Time-Efficient Active Learning for Synthesizing Queries

• Active query selection maximizes the minimum volume removed from the preference-weight distribution across possible user inputs, using an approximation to the likelihood for Bayesian updates.The method samples candidate weights with adaptive Metropolis and solves the selection optimization with a Quasi-Newton method.Source: §3 · p. 3
• Batch selection maximizes joint conditional entropy over feasible queries, but exhaustive search is intractable because its search space grows exponentially.The method discretizes trajectory space by sampling K trajectory pairs; computation increases linearly with K.Source: §3 · p. 3

3.1 Algorithms for Time-Efficient Batch Active Learning

• Greedy selection chooses b individually high-entropy queries under an independence approximation, which can put redundant, similar samples in the same batch.The paper notes that the independence assumption is not valid.Source: §3.1 · p. 4
• Medoid selection clusters B greedy-selected ψ-vectors into b groups and selects a candidate medoid from each group to increase dissimilarity.Unlike cluster centroids, medoids are selected from the original candidate set.Source: §3.1 · p. 4
• Boundary medoid selection first restricts candidates to the convex-hull boundary of the greedy set, then clusters them and selects one medoid per cluster.The paper notes that in sufficiently high-dimensional ψ spaces, most clusters will have boundary points.Source: §3.1 · p. 4
• Successive elimination repeatedly removes the lower-entropy point from the closest pair until b candidates remain, aiming for a diversified batch.It uses each candidate’s conditional entropy to decide which member of a close pair to retain.Source: §3.1 · p. 4, Figure 3 · p. 5

3.2 Convergence Guarantees

• Under the stated assumptions, greedy selection and successive elimination remove at least 1−ϵ as much volume as the best adaptive strategy after b ln(1/ϵ) times as many queries.The guarantee ignores specified sampling, noise-model, and optimization errors.Source: §3.2 · p. 5

4 Simulations and Experiments

• Experiments use batch size b = 10, candidate set size B = 20b, and M = 1000, reusing 5×10^5 sampled inputs and their feature vectors.The sampled input space is used for every experiment and iteration.Source: §4 · p. 5

4.1 Tasks

• The evaluation uses LDS, driving, LunarLander, Mountain Car, Swimmer, and Tosser, with task-specific trajectory features and simulation settings.For LDS, the feature vector is set equal to the control inputs; preference responses are noisy in LDS and oracle-based in the other tasks.Source: §4.1 · p. 6

4.2 Experiment Results

• In LDS, non-batch active learning performs best; among batch methods, successive elimination ranks above medoids, boundary medoids, and greedy selection.Successive elimination is significantly better than medoid selection, and the last three batch methods significantly outperform greedy selection.Source: §4.2 · p. 6, Figure 4 · p. 6
• Across five tasks, batch methods generate queries faster than non-batch active learning and random querying, while non-batch learning performs poorly on LunarLander and Tosser.The figure also reports successive elimination outperforming other batch methods on MountainCar and Tosser.Source: §4.2 · p. 6, Figure 5 · p. 7

4.3 User Preferences

• In the Driver study, users’ preferences were mostly similar, and 70 queries were enough to converge to safe, sensible driving in the defined scenario.Two users showed slightly different collision-avoidance preferences, corresponding to potentially more aggressive driving styles.Source: §4.3 · p. 7, Figure 7 · p. 7
• In Tosser, users expressed distinct basket preferences, and 100 queries were enough to see reasonable convergence.Demonstrations optimized controls for two users, one preferring the green basket and the other the red basket.Source: §4.3 · p. 8, Figure 8 · p. 8

• Compared with previous studies, the method requires few queries generated in reasonable time and provides convergence guarantees, with performance demonstrated in simulation.Source: §5 · p. 8
• Batch methods parallelize control-space sampling, while non-batch methods repeat un-parallelizable optimization per query, qualifying runtime comparisons.The authors also note that sampling can reduce non-batch performance and is currently the best available option for batch methods.Source: §5 · p. 8
• Because batch size is fixed, the authors propose starting with smaller batches and increasing them over time to make early queries more informative and later queries faster.Source: §5 · p. 8
• For safety-critical dynamical systems, further research is needed to ensure optimization is not evaluated with unsafe inputs.Source: §5 · p. 8
• Future work would learn handcrafted feature transformations jointly with preferences to learn reward functions directly from trajectories, and considers determinantal point processes for batch diversity.Source: §5 · p. 8