  Markov decision processes (MDPs) with large number of states are of high
practical interest. However, conventional algorithms to solve MDP are
computationally infeasible in this scenario. Approximate dynamic programming
(ADP) methods tackle this issue by computing approximate solutions. A widely
applied ADP method is approximate linear program (ALP) which makes use of
linear function approximation and offers theoretical performance guarantees.
Nevertheless, the ALP is difficult to solve due to the presence of a large
number of constraints and in practice, a reduced linear program (RLP) is solved
instead. The RLP has a tractable number of constraints sampled from the
original constraints of the ALP. Though the RLP is known to perform well in
experiments the theoretical guarantees are available only for a specific RLP
obtained under idealized assumptions.
  In this paper, we generalize the RLP to define a generalized reduced linear
program (GRLP) which has a tractable number of constraints that are obtained as
positive linear combinations of the original constraints of the ALP. The main
contribution of this paper is the novel theoretical framework developed to
obtain error bounds for any given GRLP. Central to our framework are two
$\max$-norm contraction operators. Our result solves theoretically justifies
linear approximation of constraints. We discuss the implication of our results
in the contexts of ADP and reinforcement learning. We also demonstrate via an
example in the domain of controlled queues that the experiments conform to the
theory.
