An Analysis of State-Relevance Weights and Sampling Distributions on
  L1-Regularized Approximate Linear Programming Approximation Accuracy
  Recent interest in the use of $L_1$ regularization in the use of value
function approximation includes Petrik et al.'s introduction of
$L_1$-Regularized Approximate Linear Programming (RALP). RALP is unique among
$L_1$-regularized approaches in that it approximates the optimal value function
using off-policy samples. Additionally, it produces policies which outperform
those of previous methods, such as LSPI. RALP's value function approximation
quality is affected heavily by the choice of state-relevance weights in the
objective function of the linear program, and by the distribution from which
samples are drawn; however, there has been no discussion of these
considerations in the previous literature. In this paper, we discuss and
explain the effects of choices in the state-relevance weights and sampling
distribution on approximation quality, using both theoretical and experimental
illustrations. The results provide insight not only onto these effects, but
also provide intuition into the types of MDPs which are especially well suited
for approximation with RALP.
