A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints

Constrained Markov Decision Processes (CMDPs) formalize sequential decision-making problems whose objective is to minimize a cost function while satisfying constraints on various cost functions. In this paper, we consider the setting of episodic fixed-horizon CMDPs. We propose an online algorithm which leverages the linear programming formulation of finitehorizon CMDP for repeated optimistic planning to provide a probably approximately correct (PAC) guarantee on the number of episodes needed to ensure an ǫ-optimal policy, i.e., with resulting objective value within ǫ of the optimal value and satisfying the constraints within ǫ-tolerance, with probability at least 1δ. The number of episodes needed is shown to be of the order δ , where C is the upper bound on the number of possible successor states for a state-action pair. Therefore, if C ≪ |S|, the number of episodes needed have a linear dependence on the state and action space sizes |S| and |A|, respectively, and quadratic dependence on the time horizon H. I. INTRODUCTION Markov decision processes (MDPs) [1] offer a natural framework to express sequential decision-making problems and reason about autonomous system behaviors. However, the single cost objective of a traditional MDP formulation may fall short of fully capturing problems with multiple conflicting objectives and additional constraints that must be satisfied. Consider, for example, an autonomous car that is required to reach a destination at the earliest, but also satisfy a set of safety requirements and fuel consumption constraints, while keeping a desired comfort level [2] . The framework of constrained MDPs (CMDPs) [3] extended MDPs by considering additional constraints on the expected long-term performance of a policy. The objective in a CMDP is to minimize the expected cumulative cost while satisfying the additional constraints. In this paper, we consider episodic finite-horizon CMDPs, where an agent interacts with a CMDP repeatedly in episodes of fixed length, a setting that can model a large number of repetitive tasks such as goods delivery or customer service. We address the problem of online learning of CMDPs with unknown transition probabilities, by requiring only observed trajectories rather than sampling the transition function for any state-action pair from a generative model, which may not always be available. An important question which arises in online learning is the exploration-exploitation dilemma, i.e., the trade-off between exploration, to gain more information about the model, and exploitation, to minimize the cost. In this respect, the performance of learning algorithms is commonly evaluated in terms of (i) regret, i.e., the difference between the cumulative cost of the agent and that of the optimal policy in hindsight, and (ii) sample complexity, i.e., the number of steps for which the learning agent may not play a near-optimal policy. We consider a policy to be near optimal if the expected cumulative cost is close to the optimal and the constraints are satisfied within a small tolerance. In this paper, we address sample-efficiency by proposing an algorithm that provide Probably Approximately Correct (PAC) guarantees. Our algorithm leverages the concept of optimism-in-the-face-of-uncertainty [4], [5] to balance exploration and exploitation. The learning agent repeatedly defines a set of statistically plausible transition models given the observations made so far. It then chooses an optimistic transition probability model and optimistic policy with respect to the given constrained MDP problem. This planning step is formulated as a linear programming (LP) problem in occupancy measures, whose solution gives the desired optimistic policy. This policy is then executed for multiple episodes until a state-action pair has been visited sufficiently often. The total visitation counts are then updated and these steps are repeated. We show that the number of episodes in which the learning agent plays an ǫ-suboptimal policy is upper bounded by δ with probability at least 1 -δ, where C is the upper bound on the number of possible successor states for a state-action pair. Contribution. In this paper, we present one of the first online algorithms with PAC guarantees for episodic constrained MDPs with unknown transition probabilities. We build on the work of [6] which provides a PAC algorithm for unconstrained episodic MDPs. However, differently from planning based on the Bellman optimality equations [6], we address the presence of constraints by formulating an optimistic planning problem as an LP in occupancy measures. Consequently, our formulation leverages a novel construction for the set of plausible transition models and results in a sample complexity that is quadratic in the time-horizon H, thus improving on the cubic bounds previously obtained with regret-based formulations (e.g., see [7] ). Related Work. There has been significant work on efficient learning for unconstrained MDPs.