  Approximate linear programs (ALPs) are well-known models based on value
function approximations (VFAs) to obtain policies and lower bounds on the
optimal policy cost of discounted-cost Markov decision processes (MDPs).
Formulating an ALP requires (i) basis functions, the linear combination of
which defines the VFA, and (ii) a state-relevance distribution, which
determines the relative importance of different states in the ALP objective for
the purpose of minimizing VFA error. Both these choices are typically
heuristic: basis function selection relies on domain knowledge while the
state-relevance distribution is specified using the frequency of states visited
by a heuristic policy. We propose a self-guided sequence of ALPs that embeds
random basis functions obtained via inexpensive sampling and uses the known VFA
from the previous iteration to guide VFA computation in the current iteration.
Self-guided ALPs mitigate the need for domain knowledge during basis function
selection as well as the impact of the initial choice of the state-relevance
distribution, thus significantly reducing the ALP implementation burden. We
establish high probability error bounds on the VFAs from this sequence and show
that a worst-case measure of policy performance is improved. We find that these
favorable implementation and theoretical properties translate to encouraging
numerical results on perishable inventory control and options pricing
applications, where self-guided ALP policies improve upon policies from
problem-specific methods. More broadly, our research takes a meaningful step
toward application-agnostic policies and bounds for MDPs.
