Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning
Guy Lever, John S. Shawe-Taylor, Ronnie Stafford et al. · Proceedings of the AAAI Conference on Artificial Intelligence · 2016
We present a model-based approach to solving Markov decision processes (MDPs) in which the system dynamics are learned using conditional mean embeddings (CMEs). This class of methods comes with strong performance guarantees, and enables planning to be performed in an induced finite (pseudo-)MDP, which approximates the MDP, but can be solved exactly using dynamic programming. Two drawbacks of existing methods exist: firstly, the size of the induced finite (pseudo-)MDP scales quadratically with the amount of data used to learn the model, costing much memory and time when planning with the learned model; secondly, learning the CME itself using powerful kernel least-squares is costly – a second computational bottleneck. We present an algorithm which maintains a rich kernelized CME model class, but solves both problems: firstly we demonstrate that the loss function for the CME model suggests a principled approach to compressing the induced (pseudo-)MDP, leading to faster planning, while maintaining guarantees; secondly we propose to learn the CME model itself using fast sparse-greedy kernel regression well-suited to the RL context. We demonstrate superior performance to existing methods in this class of modelbased approaches on a range of MDPs.
Cited by 18 works. doi:10.1609/aaai.v30i1.10304
Authors
References
- Dynamic Programming
- Regression Shrinkage and Selection Via the Lasso
- Matching pursuits with time-frequency dictionaries
- Dynamic Programming and Markov Processes.
- Dynamic Programming and Optimal Control
- Kernel Methods for Pattern Analysis
- Residual Algorithms: Reinforcement Learning with Function Approximation
- Efficient projections onto the l 1 -ball for learning in high dimensions
- Reinforcement learning with replacing eligibility traces
- Linear Least-Squares algorithms for temporal difference learning