Markov Decision Processes (MDPs) have been used to formulate many decision-making problems in science and engineering. The objective is to synthesize the best decision (action selection) policies to maximize expected rewards (minimize costs) in a given stochastic dynamical environment. In many practical scenarios (multi-agent systems, telecommunication, queuing, etc.), the decision-making problem can have state constraints that must be satisfied, which leads to Constrained MDP (CMDP) problems. In the presence of such state constraints, the optimal policies can be very hard to characterize. This paper introduces a new approach for finding non-stationary randomized policies for finite-horizon CMDPs. An efficient algorithm based on Linear Programming (LP) and duality theory is proposed, which gives the convex set of feasible policies and ensures that the expected total reward is above a computable lower-bound. The resulting decision policy is a randomized policy, which is the projection of the unconstrained deterministic MDP policy on this convex set. To the best of our knowledge, this is the first result in state constrained MDPs to give an efficient algorithm for generating finite horizon randomized policies for CMDP with optimality guarantees. A simulation example of a swarm of autonomous agents running MDPs is also presented to demonstrate the proposed CMDP solution algorithm.
@cite_30: Linear Programming is known to be an important and useful tool for solving Markov Decision Processes (MDP). Its derivation relies on the Dynamic Programming approach, which also serves to solve MDP. However, for Markov Decision Processes with several constraints the only available methods are based on Linear Programs. The aim of this paper is to investigate some aspects of such Linear Programs, related to multi-chain MDPs. We first present a stochastic interpretation of the decision variables that appear in the Linear Programs available in the literature. We then show for the multi-constrained Markov Decision Process that the Linear Program suggested in [9] can be obtained from an equivalent unconstrained Lagrange formulation of the control problem. This shows the connection between the Linear Program approach and the Lagrange approach, that was previously used only for the case of a single constraint [3, 14, 15].
@cite_26: 
@cite_29: Due to increasing computer processing power, Newton's method is receiving again increasing interest for solving optimization problems. In this paper, we provide a methodology for solving smooth norm optimization problems under some linear constraints using the Newton's method. This problem arises in many machine learning and graph optimization applications. We consider as a case study optimal weight selection for average consensus protocols for which we show how Newton's method significantly outperforms gradient methods both in terms of convergence speed and in term of robustness to the step size selection.
@cite_21: We consider a discrete-time queueing system consisting of K + 1 classes of customers competing for a single server at an infinite capacity queue. For each customer class the arrival sequence forms a renewal sequence but is otherwise arbitrary. The service requirements are geometric with class-dependent parameter. The optimization criterion is to minimize a linear combination of the average line lengths for classes 1 through K , while simultaneously subjecting the average line length of class-0 customers to a hard constraint. The optimal policy is shown to be a randomized modification of a static-priority policy. The optimization problem is thereby reduced to a problem of finding the optimal randomization factor. This is done in a particular case, when the arrival processes are independent and geometrically distributed.
@cite_1: A multichain Markov decision process with constraints on the expected state-action frequencies may lead to a unique optimal policy which does not satisfy Bellman's principle of optimality. The model with sample-path constraints does not suffer from this drawback.
@cite_0: This paper deals with constrained optimization of Markov Decision Processes. Both objective function and constraints are sums of standard discounted rewards, but each with a different discount factor Such models arise, e.g., in production and in applications involving multiple time scales. We prove that it a feasible policy exists, then there exists an optimal policy which is (i) stationary (nonrandomized) from some step onward, (ii) randomized, Markov before this step, but the total number of actions which are added by randomization is bounded by the number of constraints. Optimality of such policies for multi-criteria problems is also established. These new policies have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. This result is new even for constrained optimization with a single discount factor, where the optimality of randomized stationary policies is known. However, a randomized stationary policy may req...
@cite_24: 
@cite_27: 
@cite_23: This paper deals with constrained optimization of Markov Decision Processes with a countable state space, compact action sets, continuous transition probabilities, and upper semicontinuous reward functions. The objective is to maximize the expected total discounted reward for one reward function, under several inequality constraints on similar criteria with other reward functions. Suppose a feasible policy exists for a problem with M constraints. We prove two results on the existence and structure of optimal policies. First, we show that there exists a randomized stationary optimal policy which requires at most M actions more than a nonrandomized stationary one. This result is known for several particular cases. Second, we prove that there exists an optimal policy which is i stationary nonrandomized from some step onward, ii randomized Markov before this step, but the total number of actions which are added by randomization is at most M, iii the total number of actions that are added by nonstationarity is at most M. We also establish Pareto optimality of policies from the two classes described above for multi-criteria problems. We describe an algorithm to compute optimal policies with properties i--iii for constrained problems. The policies that satisfy properties i--iii have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. In contrast, a randomized stationary policy may require an infinite number of randomizations over time.
@cite_16: In this paper we investigate the computation of optimal policies in constrained discrete stochastic dynamic programming with the average reward as utility function. The state-space and action-sets are assumed to be finite. Constraints which are linear functions of the state-action frequencies are allowed. In the general multichain case, an optimal policy will be a randomized nonstationary policy. An algorithm to compute such an optimal policy is presented. Furthermore, sufficient conditions for optimal policies to be stationary are derived. There are many applications for constrained undiscounted stochastic dynamic programming, e.g., in multiple objective Markovian decision models.
@cite_12: 
Previous research has focused on finding infinite-horizon stationary policies for constrained MDPs. Due to the constraints, the optimal policies might no longer be deterministic and stationary @cite_0 . @cite_1 gives an example of a transient multi-chain MDP with state constraints and shows that the Bellman principle fails to hold and the optimal policy is not necessarily stationary. In the presence of constraints, randomization in the actions can then be necessary for obtaining optimal policies @cite_21 @cite_29 . For stationary policies to be optimal, specific assumptions on the underlying Markov chain are often introduced @cite_12 . Stationary policies for these specific models can be found by using algorithms based on Linear Programming (LP) @cite_16 or Lagrange multipliers ( @cite_30 @cite_26 ). However, finding optimal policies in the broader class of randomized policies for CMDPs can be very expensive computationally and there is no previously known algorithm for the general case See @cite_23 for very specific examples where solutions can be obtained. @cite_27 @cite_24 .