  We propose a novel generalization of constrained Markov decision processes
(CMDPs) that we call the \emph{semi-infinitely constrained Markov decision
process} (SICMDP). Particularly, we consider a continuum of constraints instead
of a finite number of constraints as in the case of ordinary CMDPs. We also
devise two reinforcement learning algorithms for SICMDPs that we call SI-CRL
and SI-CPO. SI-CRL is a model-based reinforcement learning algorithm. Given an
estimate of the transition model, we first transform the reinforcement learning
problem into a linear semi-infinitely programming (LSIP) problem and then use
the dual exchange method in the LSIP literature to solve it. SI-CPO is a policy
optimization algorithm. Borrowing the ideas from the cooperative stochastic
approximation approach, we make alternative updates to the policy parameters to
maximize the reward or minimize the cost. To the best of our knowledge, we are
the first to apply tools from semi-infinitely programming (SIP) to solve
constrained reinforcement learning problems. We present theoretical analysis
for SI-CRL and SI-CPO, identifying their iteration complexity and sample
complexity. We also conduct extensive numerical examples to illustrate the
SICMDP model and demonstrate that our proposed algorithms are able to solve
complex sequential decision-making tasks leveraging modern deep reinforcement
learning techniques.
