Method and apparatus for improved reward-based learning using nonlinear dimensionality reduction
View Patent ↗The present invention is a method and an apparatus for reward-based learning of management policies. In one embodiment, a method for reward-based learning includes receiving a set of one or more exemplars, where at least two of the exemplars comprise a (state, action) pair for a system, and at least one of the exemplars includes an immediate reward responsive to a (state, action) pair. A distance measure between pairs of exemplars is used to compute a Non-Linear Dimensionality Reduction (NLDR) mapping of (state, action) pairs into a lower-dimensional representation, thereby producing embedded exemplars, wherein one or more parameters of the NLDR are tuned to minimize a cross-validation Bellman error on a holdout set taken from the set of one or more exemplars. The mapping is then applied to the set of exemplars, and reward-based learning is applied to the embedded exemplars to obtain a learned management policy.
1. A method for learning a management policy, comprising:
receiving a set of one or more exemplars, wherein at least two of the one or more exemplars comprise a (state, action) pair for a system, and at least one of the one or more exemplars comprises a reward responsive to performing an action in a state;
obtaining a set of one or more pairwise distances between one or more pairs of the one or more exemplars;
applying a nonlinear dimensionality reduction to the one or more exemplars and to the one or more pairwise distances in order to embed the one or more exemplars into a lower dimensional space, thereby producing embedded exemplars, wherein one or more parameters of the nonlinear dimensionality reduction are tuned to minimize a cross-validation Bellman error on a holdout set taken from the set of one or more exemplars; and
applying a reward-based learning method to the embedded exemplars in order to derive a learned management policy,
wherein at least one of: the receiving, the obtaining, the applying the nonlinear dimensionality reduction, or the applying the reward-based learning method is performed using a processor.
2. The method of claim 1 , wherein the obtaining comprises:
applying a distance metric to the one or more pairs of the one or more exemplars.
3. The method of claim 1 , further comprising:
applying the learned management policy to manage a computing system or to control a plant.
4. The method of claim 1 , wherein the nonlinear dimensionality reduction is at least one of: Laplacian Eigenmaps, Maximum Variance Unfolding, Isomap, Spatio-temporal Isomap, Local Linear Embedding, Stochastic Proximity Embedding or Random Projections.
5. The method of claim 1 , further comprising:
constructing a general out-of-sample embedding function in accordance with the embedded exemplars.
6. The method of claim 5 , wherein the out-of-sample embedding function is constructed using Local Linear Embedding.
7. The method of claim 2 , wherein the one or more pairwise distances are computed in accordance with a pre-specified distance metric.
8. The method of claim 1 , wherein the reward-based learning method is a Reinforcement Learning method.
9. The method of claim 8 , wherein the Reinforcement Learning method is one of: a value-function learning method, an actor-critic method or a direct policy method.
10. The method of claim 8 , wherein the Reinforcement Learning method is one of: Temporal Difference Learning, Q-Learning, Sarsa or a policy gradient method.
11. The method of claim 2 , wherein the one or more pairwise distances are computed in accordance with a learned distance metric.
12. The method of claim 1 , wherein the nonlinear dimensionality reduction is applied separately to a state associated with each of the one or more exemplars and to an action associated with the each of the one or more exemplars.
13. The method of claim 1 , wherein the nonlinear dimensionality reduction is applied to only one of: a state associated with each of the one or more exemplars or an action associated with the each of the one or more exemplars.
14. A computer readable medium containing an executable program for reward-based learning of a management policy, where the program performs steps of:
receiving a set of one or more exemplars, wherein at least two of the one or more exemplars comprise a (state, action) pair for a system, and at least one of the one or more exemplars comprises a reward responsive to performing an action in a state;
obtaining a set of one or more pairwise distances between one or more pairs of the one or more exemplars;
applying a nonlinear dimensionality reduction to the one or more exemplars and to the one or more pairwise distances in order to embed the one or more exemplars into a lower dimensional space, thereby producing embedded exemplars, wherein one or more parameters of the nonlinear dimensionality reduction are tuned to minimize a cross-validation Bellman error on a holdout set taken from the set of one or more exemplars; and
applying a reward-based learning method to the embedded exemplars in order to derive a learned management policy.
15. The computer readable medium of claim 14 , wherein the obtaining comprises:
applying a distance metric to the one or more pairs of the one or more exemplars.
16. The computer readable medium of claim 14 , further comprising:
applying the learned management policy to manage a computing system or to control a plant.
17. The computer readable medium of claim 14 , wherein the nonlinear dimensionality reduction is at least one of: Laplacian Eigenmaps, Maximum Variance Unfolding, Isomap, Spatio-temporal Isomap, Local Linear Embedding, Stochastic Proximity Embedding or Random Projections.
18. The computer readable medium of claim 14 , further comprising:
constructing a general out-of-sample embedding function in accordance with the embedded exemplars.
19. The computer readable medium of claim 18 , wherein the out-of-sample embedding function is constructed using Local Linear Embedding.
20. The computer readable medium of claim 15 , wherein the one or more pairwise distances are computed in accordance with a pre-specified distance metric.
21. The computer readable medium of claim 14 , wherein the reward-based learning method is a Reinforcement Learning method.
22. The computer readable medium of claim 15 , wherein the one or more pairwise distances are computed in accordance with a learned distance metric.
23. A system for learning a management policy, comprising:
means for receiving a set of one or more exemplars, wherein at least two of the one or more exemplars comprise a (state, action) pair for a system, and at least one of the one or more exemplars comprises a reward responsive to performing an action in a state;
means for obtaining a set of one or more pairwise distances between one or more pairs of the one or more exemplars;
means for applying a nonlinear dimensionality reduction to the one or more exemplars and to the one or more pairwise distances in order to embed the one or more exemplars into a lower dimensional space, thereby producing embedded exemplars, wherein one or more parameters of the nonlinear dimensionality reduction are tuned to minimize a cross-validation Bellman error on a holdout set taken from the set of one or more exemplars; and
means for applying a reward-based learning method to the embedded exemplars in order to derive a learned management policy.
24. The system of claim 23 , wherein the means for obtaining comprises:
means for applying a distance metric to the one or more pairs of the one or more exemplars.