Approximate dynamic programming has been used successfully in a large variety
of domains, but it relies on a small set of provided approximation features to
calculate solutions reliably. Large and rich sets of features can cause
existing algorithms to overfit because of a limited number of samples. We
address this shortcoming using $L_1$ regularization in approximate linear
programming. Because the proposed method can automatically select the
appropriate richness of features, its performance does not degrade with an
increasing number of features. These results rely on new and stronger sampling
bounds for regularized approximate linear programs. We also propose a
computationally efficient homotopy method. The empirical evaluation of the
approach shows that the proposed method performs well on simple MDPs and
standard benchmark problems.

本文介绍了使用 $L_1$ 正则化方法的近似线性规划，以解决过多和丰富的特征对现有算法的过拟合问题，并为正则化的近似线性规划提供新的和更强的采样上界；并提出了计算有效的同伦方法。在简单的 MDPs 和基准问题上，提出的方法表现良好。