
## 7. Conclusion And Related Work

In this paper, we introduced L1**-regularized Approximate Linear Programming and demonstrated its properties for combined feature selection and value function approximation in reinforcement learning. RALP**
simultaneously addresses the feature selection, value function approximation, and policy determination problems; our experimental results demonstrate that it addresses these issues effectively for several sample problems, while our bounds explain the effects of sampling on the resulting approximation. There are many additional issues that need to be addressed. The first is the construction of better bounds to guide the sampling. Our bounds explain the behavior of RALP approximation as it relates to the trade-off between the richness of the features with the number of available samples, but these bounds may at times be quite loose. Future work must identify conditions that can provide stronger guarantees. Additionally, a data-driven approach which can calculate a tighter bound online would be valuable. Finally, our analysis did not address the conditions that would guarantee sparse RALP solutions and, therefore, allow more computationally efficient solvers.

## Acknowledgements

This work was supported in part by DARPA CSSG HR0011-06-1-0027, by NSF IIS-0713435, by the Air Force Office of Scientific Research under Grant No. FA9550-08-1-0171, and by the Duke University Center for Theoretical and Mathematical Sciences. We also thank the anonymous reviewers for their useful comments.

## References

Asif, Salman. Dantzig selector homotopy with dynamic measurements. In IS&T/SPIE Computational Imaging VII**, 2009.**
Barto, Andrew G. and Sutton, Richard S. Reinforcement Learning: an Introduction**. MIT Press, 1998.**

Candes, Emmanuel and Tao, Terence. The Dantzig selector:statistical estimation when p is much larger than n. Annals of Statistics**, 35:2313–2351, 2007.**
de Farias, Daniela Pucci and Van Roy, Benjamin.

On constraint sampling for the linear programming approach to approximate dynamic programming.

Math. of Operations Res**, 2001.**
de Farias, Daniela Pucci and Van Roy, Benjamin. The
Linear Programming Approach to Approximate Dynamic Programming. Operations Research**, 2003.**

Desai, Vijay, Farias, Vivek, and Moallemi, Ciamac. A
smoothed approximate linear program. In **Advances**
in Neural Information Processing Systems (NIPS),
pp. 459–467, 2009.

Farahmand, Amir Massoud, Ghavamzadeh, Mohammad, Szepesvari, Csaba, and Mannor, Shie. Regularized policy iteration. In Advances in Neural Information Processing Systems**, volume 21, pp. 441–448,**
2008.

James, Gareth M., Radchenko, Peter, and Lv, Jinchi.

DASSO: Connections between the Dantzig selector and lasso. **Journal of the Royal Statistical Society,** Series B**, 71:127–142, 2009.**
Kolter, J. Zico and Ng, Andrew. Regularization and feature selection in least-squares temporal difference learning. In **International Conference on Machine** Learning (ICML)**, pp. 521–528, 2009.**
Lagoudakis, Michail G. and Parr, Ronald. LeastSquares Policy Iteration. **The Journal of Machine**
Learning Research**, 4:1107–1149, 2003.**
Mahadevan, Sridhar. Learning representation and control in markov decision processes: New frontiers.

Foundations and Trends in Machine Learning**, 1(4):** 403–565, 2008.

Parr, Ronald, Painter-Wakefield, Christopher, Li, Lihong, and Littman, Michael. Analyzing feature generation for value-function approximation. In **International Conference on Machine Learning (ICML)**,
pp. 744–751, 2007.

Petrik, Marek and Zilberstein, Shlomo. Constraint Relaxation in Approximate Linear Programs. In **International Conference on Machine Learning (ICML)**,
pp. 809–816, 2009.

Randløv, Jette and Alstrøm, Preben. Learning to drive a bicycle using reinforcement learning and shaping.

In **International Conference on Machine Learning**, pp. 463–471, 1998.

Schweitzer, Paul J. and Seidmann, Abraham. Generalized polynomial approximations in Markovian decision processes. **Journal of mathematical analysis**
and applications**, 110(6):568–582, 1985.**
Taylor, Gavin and Parr, Ronald. Kernelized Value Function Approximation for Reinforcement Learning. In International Conference on Machine Learning**, pp. 1017–1024, Montreal, Canada, June 2009.**
Omnipress.