Source-linked AI summary
Agnostic System Identification for Model-Based Reinforcement Learning
Stephane Ross, J. Andrew Bagnell
TL;DR
System identification for model-based reinforcement learning is difficult when the true system lies outside the chosen model class and learned policies visit states unlike the training distribution. The paper reduces agnostic MBRL to no-regret online learning, yielding near-optimal policies when a low-error model and good exploration distribution are available, with guarantees demonstrated in helicopter control.
Problem
System identification can produce models with low training error but poor controller performance because learned policies visit states unlike those in exploration data, while prior guarantees assume the true system belongs to the model class.
Method
The paper iterates between learning a transition model and synthesizing a controller, interpreting the procedure as no-regret online learning with access to a good exploration distribution.
Results
The approach provides strong agnostic performance guarantees, applies to discrete and continuous domains, and demonstrates efficacy and scalability on helicopter control.
Takeaways & Limitations
The method offers a practical MBRL procedure whose sample complexity scales with model-class complexity rather than MDP size.
Takeaways & Limitations
The batch method is limited by train-test distribution mismatch, while the guarantees require a model with low error and a good exploration distribution.
Abstract
from arXiv · showhide
A fundamental problem in control is to learn a model of a system from observations that is useful for controller synthesis. To provide good performance guarantees, existing methods must assume that the real system is in the class of models considered during learning. We present an iterative method with strong guarantees even in the agnostic case where the system is not in the class. In particular, we show that any no-regret online learning algorithm can be used to obtain a near-optimal policy, provided some model achieves low training error and access to a good exploration distribution. Our approach applies to both discrete and continuous domains. We demonstrate its efficacy and scalability on a challenging helicopter domain from the literature.
1. Introduction
System identification for control suffers from train-test mismatch because the learned policy visits states unlike those represented in exploration data. The paper proposes an iterative, agnostic MBRL approach with guarantees based on no-regret online learning.
- Motivation: A model can fit exploration data well yet perform poorly when the synthesized policy visits different states.The mismatch arises because exploration-policy states may differ from those induced by the learned policy.
- Limitations of prior methods: Existing identification methods often assume the true system belongs to the model class used for learning.Under that assumption, sufficiently covering the state-action space can eventually identify the correct model.
- Approach: The paper analyzes system identification and controller synthesis under the weaker agnostic assumption that a model achieves statistically good prediction.Its reduction-based analysis relates learned-policy performance to prediction error during training.
- Approach: The proposed iterative method alternates between model learning and controller synthesis, using online-learning ideas to address distribution mismatch.Unlike the batch approach, its guarantees need not scale with the MDP size when a good exploration distribution is available.
- Evaluation: The method supports any no-regret online algorithm and is demonstrated on helicopter aerobatic maneuvers.The helicopter experiment is presented as a challenging domain from the literature.
2. Background and Notation
The paper models the unknown controlled system as an MDP and seeks a low-regret policy by learning a transition model and optimizing against it. It connects this objective to standard control formulations and iterative identification practice.
- MDP formulation: The system is represented as an unknown MDP with states, actions, transition function, and initial-state distribution.States and actions may be infinite and continuous, and performance is measured by discounted cumulative cost.
- Objective: The objective is to find a policy whose expected discounted cost is close to that of any comparator policy.The paper defines this as achieving small regret under the initial distribution.
- Model-based control: The approach learns a transition model and solves an optimal-control problem under that model to obtain a policy.Dynamic programming or approximate control methods can be used for the model-based optimization.
- Related practice: Iterative system identification collects data, fits a model, tests the resulting controller, and changes sampling when performance is unsatisfactory.This engineering practice is related to dataset aggregation and iterative policy improvement.
- Control examples: LQR is identified as an important continuous-system case with linear dynamics and quadratic costs, for which the optimal policy is linear.Its value function is quadratic, and the problem can be solved by dynamic programming.
- Exploration: The method leverages a state exploration distribution that can support guarantees for policies inducing relevant state distributions.This connects its exploration strategy to agnostic model-free reinforcement-learning methods.
3. A Simple Batch Algorithm
The Batch algorithm fits a transition model from i.i.d. exploratory transitions and optimizes control under that model. Its guarantees connect control performance to predictive error, optimization quality, model-class misspecification, and train-test distribution mismatch.
- Algorithm: Batch samples m state-action transitions from an exploration distribution, fits the best model in T, and solves the learned model’s optimal-control problem.The returned policy may be computed exactly or approximately.
- Guarantee: The batch guarantee improves when model prediction error and learned-model control error are small, but includes a factor measuring mismatch between ν and the policy being compared.The mismatch factor is unavoidable when the comparison policy visits state-action regions that exploration rarely covers.
- Error measures: Predictive error is measured by the expected L1 distance between true and learned next-state distributions under the training distribution ν.Because L1 error cannot be optimized directly from sampled transitions, the analysis also uses KL divergence and classification losses.
- Agnostic setting: In agnostic settings, the irreducible best-in-class model error determines how performance degrades even with more data.This model-class error is zero in realizable settings and generally nonzero otherwise.
- Statistical behavior: Consistent fitting drives generalization error toward zero as m increases, typically at an O(1/√m) rate under standard complexity-dependent behavior.Finite-sample bounds can be derived for specific settings, including finite MDPs.
- Limitation and extension: The batch method can require uniform exploration, causing bounds to scale with state-action space size and potentially producing arbitrarily poor policies when exploration is inadequate.Iterative learning is introduced to use learned-policy feedback and remove the mismatch factor from the guarantee.
4. No-Regret Methods for Agnostic MBRL
The method reduces agnostic model-based reinforcement learning to no-regret online learning by iteratively collecting policy-dependent data, updating system models, and solving control problems. With suitable exploration and low predictive error, its guarantees avoid train-test mismatch and can depend on model-class complexity rather than MDP size.
- Iterative no-regret method: DAgger iteratively collects transitions from exploratory and learned-policy distributions, updates the model with an online learner, and solves a control problem for each updated model.The procedure can use FTRL or another no-regret algorithm, with approximate optimal-control solutions permitted.
- Guarantees: Sampling data from learned policies removes the train-test mismatch factor from the control guarantees, improving on the batch setting when control problems are solved well.The guarantee concerns the learned policy's performance relative to comparison policies under the stated exploration and optimization conditions.
- Iterative no-regret method: The reduction relates control performance to predictive losses accumulated over changing training distributions, including KL, classification, or L1-based losses.KL loss corresponds to maximizing sampled-transition log likelihood, while classification losses apply to suitable deterministic finite-MDP model classes.
- Guarantees: No-regret algorithms provide average regret that decreases with iterations, so sufficiently many iterations can yield strong agnostic guarantees when a low-error model exists under the training distribution.The agnostic degradation is governed by the best achievable model loss, while the guarantee applies relative to policies whose induced distributions are sufficiently covered by exploration.
- Finite-sample considerations: In finite MDPs, empirical model estimation supports high-probability guarantees from sampled losses, while finite-sample analysis adds a generalization-error term.The exact-loss analysis would require infinitely many samples per iteration; sampled-loss bounds use martingale and online-to-batch techniques.
- Scope and computational considerations: With a good exploration distribution and a low-error model, sample complexity can depend on model-class complexity rather than the size of the MDP.For simpler model classes, the dependence on state and action space can disappear, although solving many control problems may be computationally expensive.
5. Discussion
The discussion contrasts DAgger’s reduction-style guarantees with Batch’s vulnerability to train/test mismatch, while noting computational costs from repeatedly solving optimal-control problems. DAgger’s balanced use of exploration and learned-policy data supports agnostic guarantees when a suitable model exists.
- Reduction-style guarantees: DAgger guarantees either good policies or evidence that no model in the class achieves low error on the aggregate dataset.If the latter occurs, the model class must be improved; Batch can achieve low training error yet still produce poor control policies.
- Reduction-style guarantees: Batch can fail because its low-error training models do not necessarily perform well under the policy-induced test distribution.This train/test mismatch can occur even when DAgger finds good policies.
- Computational considerations: DAgger may be computationally expensive because it requires solving many optimal-control problems, especially for nonlinear or high-dimensional models.Approximate policy-gradient, fitted-value-iteration, and iLQR methods can reduce this burden when solutions are good on average.
- Agnostic learning: DAgger balances exploration data with data collected from learned policies, preventing exploration from being ignored in favor of lower-error policy-distribution models.This balance is identified as crucial for avoiding suboptimal performance in agnostic settings.
- Agnostic learning: The approach can use any no-regret model-update algorithm and any exploration distribution while retaining guarantees in agnostic settings.Its analysis connects model-based reinforcement learning to no-regret online learning.
6. Experiments on Helicopter Domain
The experiments evaluate DAgger and Batch methods on simulated helicopter hovering and nose-in-funnel maneuvers under continuous-state control. In the hover experiments, DAgger eventually outperforms the expert and other compared approaches, while the funnel task evaluates learning time-varying models over repeated rotations.
- Experimental setting: The helicopter benchmark uses a continuous 21-dimensional state and 4-dimensional control space, including hover and nose-in-funnel maneuvers.The experiments compare DAgger with Batch under several exploration distributions.
- Hover: Hover learning fits offset matrices A′ and B′ to predict the next state from state and control deviations around an initial linear model.Experiments include noise and delays of 0 and 1; delay 1 introduces dynamics not representable by the current state.
- Hover: DAgger eventually learns a policy that outperforms the expert policy in the hover experiments.The expert visits states far from hover because of noise and delay, whereas DAgger learns a better linear model for states visited by its learned policy.
- Hover: Abbeel’s algorithm improves the initial policy but reaches a plateau because it lacks exploration data after the first iteration.A model-free policy-gradient comparison showed only small improvement with 100 samples per iteration and reached average total cost approximately 15000 with 500 samples after 100 iterations.
- Nose-in Funnel: The nose-in-funnel task learns a time-varying linear model for four complete rotations of radius 5 under noise and no delay.All methods collect 500 samples per iteration over 100 iterations, and Figure 2 reports test performance after each iteration.
7. Conclusion
The paper concludes that no-regret online learning provides a practical model-based reinforcement-learning approach with strong agnostic guarantees. Its sample complexity scales with model-class complexity rather than MDP size, distinguishing it from the largely theoretical agnostic Rmax approach described by the authors.
- Conclusion: The proposed no-regret online-learning approach has strong theoretical and practical performance in agnostic settings.It formalizes iterating between controller synthesis and system identification and applies when approximate optimal-control solutions are feasible.
- Conclusion: The method’s sample complexity scales with model-class complexity rather than the size of the MDP.The conclusion identifies this scaling as a central advantage of the approach.
- Conclusion: The authors describe the method as the first practical model-based reinforcement-learning algorithm with agnostic guarantees.They contrast it with an agnostic Rmax extension that is largely theoretical, requires unknown quantities, and has exponential sample complexity in class complexity.