A Survey of Multi-Objective Sequential Decision-Making
---
paper_title: Power systems stability control: reinforcement learning framework

paper_content:

In this paper, we explore how a computational approach to learning from interactions, called reinforcement learning (RL), can be applied to control power systems. We describe some challenges in power system control and discuss how some of those challenges could be met by using these RL methods. The difficulties associated with their application to control power systems are described and discussed as well as strategies that can be adopted to overcome them. Two reinforcement learning modes are considered: the online mode in which the interaction occurs with the real power system and the offline mode in which the interaction occurs with a simulation model of the real power system. We present two case studies made on a four-machine power system model. The first one concerns the design by means of RL algorithms used in offline mode of a dynamic brake controller. The second concerns RL methods used in online mode when applied to control a thyristor controlled series capacitor (TCSC) aimed to damp power system oscillations.
---
paper_title: Introduction to Reinforcement Learning

paper_content:

From the Publisher: ::: In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability.
---
paper_title: Reinforcement learning in robotics: A survey

paper_content:

Reinforcement learning offers to robotics a framework and set of tools for the design of sophisticated and hard-to-engineer behaviors. Conversely, the challenges of robotic problems provide both inspiration, impact, and validation for developments in reinforcement learning. The relationship between disciplines has sufficient promise to be likened to that between physics and mathematics. In this article, we attempt to strengthen the links between the two research communities by providing a survey of work in reinforcement learning for behavior generation in robots. We highlight both key challenges in robot reinforcement learning as well as notable successes. We discuss how contributions tamed the complexity of the domain and study the role of algorithms, representations, and prior knowledge in achieving these successes. As a result, a particular focus of our paper lies on the choice between model-based and model-free as well as between value-function-based and policy-search methods. By analyzing a simple problem in some detail we demonstrate how reinforcement learning approaches may be profitably applied, and we note throughout open questions and the tremendous potential for future research.
---
paper_title: Computing convex coverage sets for multi-objective coordination graphs

paper_content:

Many real-world decision problems require making trade-offs between multiple objectives. However, in some cases, the relative importance of the objectives is not known when the problem is solved, precluding the use of single-objective methods. Instead, multi-objective methods, which compute the set of all potentially useful solutions, are required. This paper proposes new multi-objective algorithms for cooperative multi-agent settings. Following previous approaches, we exploit loose couplings, as expressed in graphical models, to coordinate efficiently. Existing methods, however, calculate only the Pareto coverage set PCS, which we argue is inappropriate for stochastic strategies and unnecessarily large when the objectives are weighted in a linear fashion. In these cases, the typically much smaller convex coverage set CCS should be computed instead. A key insight of this paper is that, while computing the CCS is more expensive in unstructured problems, in many loosely coupled settings it is in fact cheaper to compute because the local solutions are more compact. We propose convex multi-objective variable elimination, which exploits this insight. We analyze its correctness and complexity and demonstrate empirically that it scales much better in the number of agents and objectives than alternatives that compute the PCS.
---
paper_title: Decision-Theoretic Military Operations Planning

paper_content:

Military operations planning involves concurrent actions, resource assignment, and conflicting costs. Individual tasks sometimes fail with a known probability, promoting a decision-theoretic approach. The planner must choose between multiple tasks that achieve similar outcomes but have different costs. The military domain is particularly suited to automated methods because hundreds of tasks, specified by many planning staff, need to be quickly and robustly coordinated. The authors are not aware of any previous planners that handle all characteristics of the operations planning domain in a single package. This paper shows that problems with such features can be successfully approached by realtime heuristic search algorithms, operating on a formulation of the problem as a Markov decision process. Novel automatically generated heuristics, and classic caching methods, allow problems of interesting sizes to be handled. Results are presented on data provided by the Australian Defence Science and Technology Organisation.
---
paper_title: Multiobjective Decision Making Theory And Methodology

paper_content:

multiobjective decision making theory and methodology is available in our digital library an online access to it is set as public so you can get it instantly. Our digital library spans in multiple countries, allowing you to get the most less latency time to download any of our books like this one. Merely said, the multiobjective decision making theory and methodology is universally compatible with any devices to read.
---
paper_title: A CRITICAL SURVEY ON THE STATUS OF MULTIPLE CRITERIA DECISION MAKING THEORY AND PRACTICE

paper_content:

This paper seeks to review and to contrast the main streams of thought in Multiple Criteria Decision Making (MCDM) theory and practice, without attempting to review all MCDM methods in detail. The main purpose is to identify pitfalls in the usage of various approaches, and to suggest approaches which are most robustly and effectively useable, especially by the non-expert in MCDM methodology. Problem areas in MCDM still requiring further research are also discussed.
---
paper_title: Improving Elevator Performance Using Reinforcement Learning

paper_content:

This paper describes the application of reinforcement learning (RL) to the difficult real world problem of elevator dispatching. The elevator domain poses a combination of challenges not seen in most RL research to date. Elevator systems operate in continuous state spaces and in continuous time as discrete event dynamic systems. Their states are not fully observable and they are nonstationary due to changing passenger arrival rates. In addition, we use a team of RL agents, each of which is responsible for controlling one elevator car. The team receives a global reinforcement signal which appears noisy to each agent due to the effects of the actions of the other agents, the random nature of the arrivals and the incomplete observation of the state. In spite of these complications, we show results that in simulation surpass the best of the heuristic elevator control algorithms of which we are aware. These results demonstrate the power of RL on a very large scale stochastic dynamic optimization problem of practical utility.
---
paper_title: Introduction to Reinforcement Learning

paper_content:

From the Publisher: ::: In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability.
---
paper_title: Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

paper_content:

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. ::: ::: This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. ::: ::: Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques-- in particular those based on the use of structured, intensional representations--can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.
---
paper_title: Constrained Markov Decision Processes

paper_content:

INTRODUCTION Examples of Constrained Dynamic Control Problems On Solution Approaches for CMDPs with Expected Costs Other Types of CMDPs Cost Criteria and Assumptions The Convex Analytical Approach and Occupation Measures Linear Programming and Lagrangian Approach for CMDPs About the Methodology The Structure of the Book PART ONE: FINITE MDPS MARKOV DECISION PROCESSES The Model Cost Criteria and the Constrained Problem Some Notation The Dominance of Markov Policies THE DISCOUNTED COST Occupation Measure and the Primal LP Dynamic Programming and Dual LP: the Unconstrained Case Constrained Control: Lagrangian Approach The Dual LP Number of Randomizations THE EXPECTED AVERAGE COST Occupation Measure and the Primal LP Equivalent Linear Program The Dual Program Number of Randomizations FLOW AND SERVICE CONTROL IN A SINGLE-SERVER QUEUE The Model The Lagrangian The Original Constrained Problem Structure of Randomization and Implementation Issues On Coordination Between Controllers Open Questions PART TWO: INFINITE MDPS MDPS WITH INFINITE STATE AND ACTION SPACES The Model Cost Criteria Mixed Policies, and Topologic Structures The Dominance of Markov Policies Aggregation of States Extra Randomization in the Policies Equivalent Quasi-Markov Model and Quasi-Markov Policies THE TOTAL COST: CLASSIFICATION OF MDPS Transient and Absorbing MDPs MDPs With Uniform Lyapunov Functions Equivalence of MDP With Unbounded and bounded costs Properties of MDPs With Uniform Lyapunov Functions Properties for Fixed Initial Distribution Examples of Uniform Lyapunov Functions Contracting MDPs THE TOTAL COST: OCCUPATION MEASURES AND THE PRIMAL LP Occupation Measure Continuity of Occupation Measures More Properties of MDPs Characterization of Achievable Sets of Occupation Measure Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program THE TOTAL COST: DYNAMIC AND LINEAR PROGRAMMING Non-Constrained Control: Dynamic and Linear Programming Superharmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP State Truncation A Second LP Approach for Optimal Mixed Policies More on Unbound Costs THE DISCOUNTED COST The Equivalent Total Cost Model Occupation Measure and LP Non-negative Immediate Cost Weak Contracting Assumptions and Lyapunov Functions Example: Flow and Service Control THE EXPECTED AVERAGE COST Occupation Measures Completeness Properties of Stationary Policies Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program The Contracting Framework Other Conditions for the Uniform Integrability The Case of Uniform Lyapunov Conditions EXPECTED AVERAGE COST: DYNAMIC PROGRAMMING AND LP The Non-Constrained Case: Optimality Inequality Non-Constrained Control: Cost Bounded Below Dynamic Programming and Uniform Lyapunov Function Super-Harmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP A Second LP Approach for Optimal Mixed Policies PART THREE: ASYMPTOTIC METHODS AND APPROXIMATIONS SENSITIVITY ANALYSIS Introduction Approximation of the Values Approximation and Robustness of the Policies CONVERGENCE OF DISCOUNTED CONSTRAINED MDPS Convergence in the Discount Factor Convergence to the Expected Average Cost The Case of Uniform Lyapunov Function CONVERGENCE AS THE HORIZON TENDS TO INFINITY The Discounted Cost The Expected Average Cost: Stationary Policies The Expected Average Cost: General Policies STATE TRUNCATION AND APPROXIMATION The Approximating sets of States Scheme I: the Total Cost Scheme II: the Total Cost Scheme III: the Total Cost The Expected Average Cost Infinite MDPs: on the Number of Randomizations APPENDIX: CONVERGENCE OF PROBABILITY MEASURES REFERENCES LIST OF SYMBOLS AND NOTATION INDEX
---
paper_title: Constrained Markov Decision Models With Weighted Discounted Rewards

paper_content:

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...
---
paper_title: Multiple Criteria Decision Making, Multiattribute Utility Theory: The Next Ten Years

paper_content:

Management science and decision science have grown exponentially since midcentury. Two closely-related fields central to this growth are multiple criteria decision making MCDM and multiattribute utility theory MAUT. This paper comments on the history of MCDM and MAUT and discusses topics we believe are important in their continued development and usefulness to management science over the next decade. Our aim is to identify exciting directions and promising areas for future research.
---
paper_title: Transition-independent decentralized markov decision processes

paper_content:

There has been substantial progress with formal models for sequential decision making by individual agents using the Markov decision process (MDP). However, similar treatment of multi-agent systems is lacking. A recent complexity result, showing that solving decentralized MDPs is NEXP-hard, provides a partial explanation. To overcome this complexity barrier, we identify a general class of transition-independent decentralized MDPs that is widely applicable. The class consists of independent collaborating agents that are tied together through a global reward function that depends upon both of their histories. We present a novel algorithm for solving this class of problems and examine its properties. The result is the first effective technique to solve optimally a class of decentralized MDPs. This lays the foundation for further work in this area on both exact and approximate solutions.
---
paper_title: Empirical evaluation methods for multiobjective reinforcement learning algorithms

paper_content:

While a number of algorithms for multiobjective reinforcement learning have been proposed, and a small number of applications developed, there has been very little rigorous empirical evaluation of the performance and limitations of these algorithms. This paper proposes standard methods for such empirical evaluation, to act as a foundation for future comparative studies. Two classes of multiobjective reinforcement learning algorithms are identified, and appropriate evaluation metrics and methodologies are proposed for each class. A suite of benchmark problems with known Pareto fronts is described, and future extensions and implementations of this benchmark suite are discussed. The utility of the proposed evaluation methods are demonstrated via an empirical comparison of two example learning algorithms.
---
paper_title: Dynamic preferences in multi-criteria reinforcement learning

paper_content:

The current framework of reinforcement learning is based on maximizing the expected returns based on scalar rewards. But in many real world situations, tradeoffs must be made among multiple objectives. Moreover, the agent's preferences between different objectives may vary with time. In this paper, we consider the problem of learning in the presence of time-varying preferences among multiple objectives, using numeric weights to represent their importance. We propose a method that allows us to store a finite number of policies, choose an appropriate policy for any weight vector and improve upon it. The idea is that although there are infinitely many weight vectors, they may be well-covered by a small number of optimal policies. We show this empirically in two domains: a version of the Buridan's ass problem and network routing.
---
paper_title: Learning all optimal policies with multiple criteria

paper_content:

We describe an algorithm for learning in the presence of multiple criteria. Our technique generalizes previous approaches in that it can learn optimal policies for all linear preference assignments over the multiple reward criteria at once. The algorithm can be viewed as an extension to standard reinforcement learning for MDPs where instead of repeatedly backing up maximal expected rewards, we back up the set of expected rewards that are maximal for some set of linear preferences (given by a weight vector, w). We present the algorithm along with a proof of correctness showing that our solution gives the optimal policy for any linear preference function. The solution reduces to the standard value iteration algorithm for a specific weight vector, w.
---
paper_title: On Finding Compromise Solutions in Multiobjective Markov Decision Processes

paper_content:

A Markov Decision Process (MDP) is a general model for solving planning problems under uncertainty. It has been extended to multiobjective MDP to address multicriteria or multiagent problems in which the value of a decision must be evaluated according to several viewpoints, sometimes conflicting. Although most of the studies concentrate on the determination of the set of Pareto-optimal policies, we focus here on a more specialized problem that concerns the direct determination of policies achieving well-balanced tradeoffs. We first explain why this problem cannot simply be solved by optimizing a linear combination of criteria. This leads us to use an alternative optimality concept which formalizes the notion of best compromise solution, i.e. a policy yielding an expected-utility vector as close as possible (w.r.t. Tchebycheff norm) to a reference point. We show that this notion of optimality depends on the initial state. Moreover, it appears that the best compromise policy cannot be found by a direct adaptation of value iteration. In addition, we observe that in some (if not most) situations, the optimal solution can only be obtained with a randomized policy. To overcome all these problems, we propose a solution method based on linear programming and give some experimental results.
---
paper_title: Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision Processes

paper_content:

This paper is devoted to fair optimization in Multiobjective Markov Decision Processes (MOMDPs). A MOMDP is an extension of the MDP model for planning under uncertainty while trying to optimize several reward functions simultaneously. This applies to multiagent problems when rewards define individual utility functions, or in multicriteria problems when rewards refer to different features. In this setting, we study the determination of policies leading to Lorenz-non-dominated tradeoffs. Lorenz dominance is a refinement of Pareto dominance that was introduced in Social Choice for the measurement of inequalities. In this paper, we introduce methods to efficiently approximate the sets of Lorenz-non-dominated solutions of infinite-horizon, discounted MOMDPs. The approximations are polynomial-sized subsets of those solutions.
---
paper_title: Markov decision processes with multiple objectives

paper_content:

We consider Markov decision processes (MDPs) with multiple discounted reward objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto-optimal point can be achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives.
---
paper_title: Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

paper_content:

We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with k reward functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the single-objective case, both randomization and memory are necessary for strategies, and that finite-memory randomized strategies are sufficient. Under the satisfaction objective, in contrast to the single-objective case, infinite memory is necessary for strategies, and that randomized memoryless strategies are sufficient for epsilon-approximation, for all epsilon>0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be epsilon-approximated in time polynomial in the size of the MDP and 1/epsilon, and exponential in the number of reward functions, for all epsilon>0. Our results also reveal flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, correct the flaws and obtain improved results.
---
paper_title: Informing sequential clinical decision-making through reinforcement learning: an empirical study

paper_content:

This paper highlights the role that reinforcement learning can play in the optimization of treatment policies for chronic illnesses. Before applying any off-the-shelf reinforcement learning methods in this setting, we must first tackle a number of challenges. We outline some of these challenges and present methods for overcoming them. First, we describe a multiple imputation approach to overcome the problem of missing data. Second, we discuss the use of function approximation in the context of a highly variable observation set. Finally, we discuss approaches to summarizing the evidence in the data for recommending a particular action and quantifying the uncertainty around the Q-function of the recommended policy. We present the results of applying these methods to real clinical trial data of patients with schizophrenia.
---
paper_title: Reinforcement Learning for MDPs with Constraints

paper_content:

In this article, I will consider Markov Decision Processes with two criteria, each defined as the expected value of an infinite horizon cumulative return. The second criterion is either itself subject to an inequality constraint, or there is maximum allowable probability that the single returns violate the constraint. I describe and discuss three new reinforcement learning approaches for solving such control problems.
---
paper_title: Constructing Stochastic Mixture Policies for Episodic Multiobjective Reinforcement Learning Tasks

paper_content:

Multiobjective reinforcement learning algorithms extend reinforcement learning techniques to problems with multiple conflicting objectives. This paper discusses the advantages gained from applying stochastic policies to multiobjective tasks and examines a particular form of stochastic policy known as a mixture policy. Two methods are proposed for deriving mixture policies for episodic multiobjective tasks from deterministic base policies found via scalarised reinforcement learning. It is shown that these approaches are an efficient means of identifying solutions which offer a superior match to the user's preferences than can be achieved by methods based strictly on deterministic policies.
---
paper_title: The Steering Approach for Multi-Criteria Reinforcement Learning

paper_content:

We consider the problem of learning to attain multiple goals in a dynamic environment, which is initially unknown. In addition, the environment may contain arbitrarily varying elements related to actions of other agents or to non-stationary moves of Nature. This problem is modelled as a stochastic (Markov) game between the learning agent and an arbitrary player, with a vector-valued reward function. The objective of the learning agent is to have its long-term average reward vector belong to a given target set. We devise an algorithm for achieving this task, which is based on the theory of approachability for stochastic games. This algorithm combines, in an appropriate way, a finite set of standard, scalar-reward learning algorithms. Sufficient conditions are given for the convergence of the learning algorithm to a general target set. The specialization of these results to the single-controller Markov decision problem are discussed as well.
---
paper_title: On Finding Compromise Solutions in Multiobjective Markov Decision Processes

paper_content:

A Markov Decision Process (MDP) is a general model for solving planning problems under uncertainty. It has been extended to multiobjective MDP to address multicriteria or multiagent problems in which the value of a decision must be evaluated according to several viewpoints, sometimes conflicting. Although most of the studies concentrate on the determination of the set of Pareto-optimal policies, we focus here on a more specialized problem that concerns the direct determination of policies achieving well-balanced tradeoffs. We first explain why this problem cannot simply be solved by optimizing a linear combination of criteria. This leads us to use an alternative optimality concept which formalizes the notion of best compromise solution, i.e. a policy yielding an expected-utility vector as close as possible (w.r.t. Tchebycheff norm) to a reference point. We show that this notion of optimality depends on the initial state. Moreover, it appears that the best compromise policy cannot be found by a direct adaptation of value iteration. In addition, we observe that in some (if not most) situations, the optimal solution can only be obtained with a randomized policy. To overcome all these problems, we propose a solution method based on linear programming and give some experimental results.
---
paper_title: Preference-based reinforcement learning: a formal framework and a policy iteration algorithm

paper_content:

This paper makes a first step toward the integration of two subfields of machine learning, namely preference learning and reinforcement learning (RL). An important motivation for a preference-based approach to reinforcement learning is the observation that in many real-world domains, numerical feedback signals are not readily available, or are defined arbitrarily in order to satisfy the needs of conventional RL algorithms. Instead, we propose an alternative framework for reinforcement learning, in which qualitative reward signals can be directly used by the learner. The framework may be viewed as a generalization of the conventional RL framework in which only a partial order between policies is required instead of the total order induced by their respective expected long-term reward. ::: ::: Therefore, building on novel methods for preference learning, our general goal is to equip the RL agent with qualitative policy models, such as ranking functions that allow for sorting its available actions from most to least promising, as well as algorithms for learning such models from qualitative feedback. As a proof of concept, we realize a first simple instantiation of this framework that defines preferences based on utilities observed for trajectories. To that end, we build on an existing method for approximate policy iteration based on roll-outs. While this approach is based on the use of classification methods for generalization and policy learning, we make use of a specific type of preference learning method called label ranking. Advantages of preference-based approximate policy iteration are illustrated by means of two case studies.
---
paper_title: On Minimizing Ordered Weighted Regrets in Multiobjective Markov Decision Processes

paper_content:

In this paper, we propose an exact solution method to generate fair policies in Multiobjective Markov Decision Processes (MMDPs). MMDPs consider n immediate reward functions, representing either individual payoffs in a multiagent problem or rewards with respect to different objectives. In this context, we focus on the determination of a policy that fairly shares regrets among agents or objectives, the regret being defined on each dimension as the opportunity loss with respect to optimal expected rewards. To this end, we propose to minimize the ordered weighted average of regrets (OWR). The OWR criterion indeed extends the minimax regret, relaxing egalitarianism for a milder notion of fairness. After showing that OWR-optimality is state-dependent and that the Bellman principle does not hold for OWR-optimal policies, we propose a linear programming reformulation of the problem. We also provide experimental results showing the efficiency of our approach.
---
paper_title: Constrained Markov Decision Processes

paper_content:

INTRODUCTION Examples of Constrained Dynamic Control Problems On Solution Approaches for CMDPs with Expected Costs Other Types of CMDPs Cost Criteria and Assumptions The Convex Analytical Approach and Occupation Measures Linear Programming and Lagrangian Approach for CMDPs About the Methodology The Structure of the Book PART ONE: FINITE MDPS MARKOV DECISION PROCESSES The Model Cost Criteria and the Constrained Problem Some Notation The Dominance of Markov Policies THE DISCOUNTED COST Occupation Measure and the Primal LP Dynamic Programming and Dual LP: the Unconstrained Case Constrained Control: Lagrangian Approach The Dual LP Number of Randomizations THE EXPECTED AVERAGE COST Occupation Measure and the Primal LP Equivalent Linear Program The Dual Program Number of Randomizations FLOW AND SERVICE CONTROL IN A SINGLE-SERVER QUEUE The Model The Lagrangian The Original Constrained Problem Structure of Randomization and Implementation Issues On Coordination Between Controllers Open Questions PART TWO: INFINITE MDPS MDPS WITH INFINITE STATE AND ACTION SPACES The Model Cost Criteria Mixed Policies, and Topologic Structures The Dominance of Markov Policies Aggregation of States Extra Randomization in the Policies Equivalent Quasi-Markov Model and Quasi-Markov Policies THE TOTAL COST: CLASSIFICATION OF MDPS Transient and Absorbing MDPs MDPs With Uniform Lyapunov Functions Equivalence of MDP With Unbounded and bounded costs Properties of MDPs With Uniform Lyapunov Functions Properties for Fixed Initial Distribution Examples of Uniform Lyapunov Functions Contracting MDPs THE TOTAL COST: OCCUPATION MEASURES AND THE PRIMAL LP Occupation Measure Continuity of Occupation Measures More Properties of MDPs Characterization of Achievable Sets of Occupation Measure Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program THE TOTAL COST: DYNAMIC AND LINEAR PROGRAMMING Non-Constrained Control: Dynamic and Linear Programming Superharmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP State Truncation A Second LP Approach for Optimal Mixed Policies More on Unbound Costs THE DISCOUNTED COST The Equivalent Total Cost Model Occupation Measure and LP Non-negative Immediate Cost Weak Contracting Assumptions and Lyapunov Functions Example: Flow and Service Control THE EXPECTED AVERAGE COST Occupation Measures Completeness Properties of Stationary Policies Relation Between Cost and Occupation Measure Dominating Classes of Policies Equivalent Linear Program The Dual Program The Contracting Framework Other Conditions for the Uniform Integrability The Case of Uniform Lyapunov Conditions EXPECTED AVERAGE COST: DYNAMIC PROGRAMMING AND LP The Non-Constrained Case: Optimality Inequality Non-Constrained Control: Cost Bounded Below Dynamic Programming and Uniform Lyapunov Function Super-Harmonic Functions and Linear Programming Set of Achievable Costs Constrained Control: Lagrangian Approach The Dual LP A Second LP Approach for Optimal Mixed Policies PART THREE: ASYMPTOTIC METHODS AND APPROXIMATIONS SENSITIVITY ANALYSIS Introduction Approximation of the Values Approximation and Robustness of the Policies CONVERGENCE OF DISCOUNTED CONSTRAINED MDPS Convergence in the Discount Factor Convergence to the Expected Average Cost The Case of Uniform Lyapunov Function CONVERGENCE AS THE HORIZON TENDS TO INFINITY The Discounted Cost The Expected Average Cost: Stationary Policies The Expected Average Cost: General Policies STATE TRUNCATION AND APPROXIMATION The Approximating sets of States Scheme I: the Total Cost Scheme II: the Total Cost Scheme III: the Total Cost The Expected Average Cost Infinite MDPs: on the Number of Randomizations APPENDIX: CONVERGENCE OF PROBABILITY MEASURES REFERENCES LIST OF SYMBOLS AND NOTATION INDEX
---
paper_title: Constrained Markov Decision Models With Weighted Discounted Rewards

paper_content:

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...
---
paper_title: The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs

paper_content:

This paper treats the discounted cost, optimal control problem for Markov processes with incomplete state information. The optimization approach for these partially observable Markov processes is a generalization of the well-known policy iteration technique for finding optimal stationary policies for completely observable Markov processes. The state space for the problem is the space of state occupancy probability distributions the unit simplex. The development of the algorithm introduces several new ideas, including the class of finitely transient policies, which are shown to possess piecewise linear cost functions. The paper develops easily implemented approximations to stationary policies based on these finitely transient policies and shows that the concave hull of an approximation can be included in the well-known Howard policy improvement algorithm with subsequent convergence. The paper closes with a detailed example illustrating the application of the algorithm to the two-state partially observable Markov process.
---
paper_title: Linear fitted-q iteration with multiple reward functions

paper_content:

We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a realworld decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.
---
paper_title: Planning and Acting in Partially Observable Stochastic Domains

paper_content:

In this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (mdps) and partially observable MDPs (pomdps). We then outline a novel algorithm for solving pomdps off line and show how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP. We conclude with a discussion of how our approach relates to previous work, the complexity of finding exact solutions to pomdps, and of some possibilities for finding approximate solutions.
---
paper_title: Perseus: Randomized Point-based Value Iteration for POMDPs

paper_content:

Partially observable Markov decision processes (POMDPs) form an attractive and principled framework for agent planning under uncertainty. Point-based approximate techniques for POMDPs compute a policy based on a finite set of points collected in advance from the agent's belief space. We present a randomized point-based value iteration algorithm called PERSEUS. The algorithm performs approximate value backup stages, ensuring that in each backup stage the value of each point in the belief set is improved; the key observation is that a single backup may improve the value of many belief points. Contrary to other point-based methods, PERSEUS backs up only a (randomly selected) subset of points in the belief set, sufficient for improving the value of each belief point in the set. We show how the same idea can be extended to dealing with continuous action spaces. Experimental results show the potential of PERSEUS in large scale POMDP problems.
---
paper_title: Anytime Point-Based Approximations for Large POMDPs

paper_content:

The Partially Observable Markov Decision Process has long been recognized as a rich framework for real-world planning and control problems, especially in robotics. However exact solutions in this framework are typically computationally intractable for all but the smallest problems. A well-known technique for speeding up POMDP solving involves performing value backups at specific belief points, rather than over the entire belief simplex. The efficiency of this approach, however, depends greatly on the selection of points. This paper presents a set of novel techniques for selecting informative belief points which work well in practice. The point selection procedure is combined with point-based value backups to form an effective anytime POMDP algorithm called Point-Based Value Iteration (PBVI). The first aim of this paper is to introduce this algorithm and present a theoretical analysis justifying the choice of belief selection technique. The second aim of this paper is to provide a thorough empirical comparison between PBVI and other state-of-the-art POMDP methods, in particular the Perseus algorithm, in an effort to highlight their similarities and differences. Evaluation is performed using both standard POMDP domains and realistic robotic tasks.
---
paper_title: On the Undecidability of Probabilistic Planning and Infinite-Horizon Partially Observable Markov Decision Problems

paper_content:

We investigate the computability of problems in probabilistic planning and partially observable infinite-horizon Markov decision processes. The undecidability of the string-existence problem for probabilistic finite automata is adapted to show that the following problem of plan existence in probabilistic planning is undecidable: given a probabilistic planning problem, determine whether there exists a plan with success probability exceeding a desirable threshold. Analogous policy-existence problems for partially observable infinite-horizon Markov decision processes under discounted and undiscounted total reward models, average-reward models, and state-avoidance models are all shown to be undecidable. The results apply to corresponding approximation problems as well.
---
paper_title: Learning all optimal policies with multiple criteria

paper_content:

We describe an algorithm for learning in the presence of multiple criteria. Our technique generalizes previous approaches in that it can learn optimal policies for all linear preference assignments over the multiple reward criteria at once. The algorithm can be viewed as an extension to standard reinforcement learning for MDPs where instead of repeatedly backing up maximal expected rewards, we back up the set of expected rewards that are maximal for some set of linear preferences (given by a weight vector, w). We present the algorithm along with a proof of correctness showing that our solution gives the optimal policy for any linear preference function. The solution reduces to the standard value iteration algorithm for a specific weight vector, w.
---
paper_title: The Optimal Control of Partially Observable Markov Processes over a Finite Horizon

paper_content:

This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem.
---
paper_title: Online Planning Algorithms for POMDPs

paper_content:

Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.
---
paper_title: Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes

paper_content:

Most exact algorithms for general partially observable Markov decision processes (POMDPs) use a form of dynamic programming in which a piecewise-linear and convex representation of one value function is transformed into another. We examine variations of the "incremental pruning" method for solving this problem and compare them to earlier algorithms from theoretical and empirical perspectives. We find that incremental pruning is presently the most efficient exact method for solving POMDPS.
---
paper_title: Markov decision processes with multiple long-run average objectives

paper_content:

We consider Markov decision processes (MDPs) with multiple long-run average objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto optimal point can be Ɛ-approximated by a memoryless strategy, for all Ɛ > 0. In contrast to the single-objective case, the memoryless strategy may require randomization. We show that the Pareto curve can be approximated (a) in polynomial time in the size of the MDP for irreducible MDPs; and (b) in polynomial space in the size of the MDP for all MDPs. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time for irreducible MDPs and in NP for all MDPs. These results provide algorithms for design exploration in MDP models with multiple long-run average objectives.
---
paper_title: Markov decision processes with multiple objectives

paper_content:

We consider Markov decision processes (MDPs) with multiple discounted reward objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto-optimal point can be achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives.
---
paper_title: Multiobjective dynamic programming for forest resource management

paper_content:

Abstract Two important properties of most forest resource management problems, i.e. multiple objectives and uncertainty, have received much attention in recent decades. Various methods, such as multiobjective optimization techniques, stochastic dynamic programming, etc., have been introduced to address these two issues, respectively. The Multiobjective Dynamic Programming (MODP) method is introduced in this paper to take the two issues into account simultaneously. The MODP problem is formulated as a Multiobjective Linear Programming (MOLP) problem and solved using the multicriteria simplex method. The relation between the set of non-dominated extreme point solutions of the MOLP and the set of non-dominated stationary policies is discussed. A numerical example is used to illustrate this method.
---
paper_title: Performance Assessment of Multiobjective Optimizers: An Analysis and Review

paper_content:

An important issue in multiobjective optimization is the quantitative comparison of the performance of different algorithms. In the case of multiobjective evolutionary algorithms, the outcome is usually an approximation of the Pareto-optimal set, which is denoted as an approximation set, and therefore the question arises of how to evaluate the quality of approximation sets. Most popular are methods that assign each approximation set a vector of real numbers that reflect different aspects of the quality. Sometimes, pairs of approximation sets are also considered. In this study, we provide a rigorous analysis of the limitations underlying this type of quality assessment. To this end, a mathematical framework is developed which allows one to classify and discuss existing techniques.
---
paper_title: Hypervolume indicator and dominance reward based multi-objective Monte-Carlo Tree Search

paper_content:

Concerned with multi-objective reinforcement learning (MORL), this paper presents MOMCTS, an extension of Monte-Carlo Tree Search to multi-objective sequential decision making, embedding two decision rules respectively based on the hypervolume indicator and the Pareto dominance reward. The MOMCTS approaches are firstly compared with the MORL state of the art on two artificial problems, the two-objective Deep Sea Treasure problem and the three-objective Resource Gathering problem. The scalability of MOMCTS is also examined in the context of the NP-hard grid scheduling problem, showing that the MOMCTS performance matches the (non-RL based) state of the art albeit with a higher computational cost.
---
paper_title: Computing Optimal Stationary Policies for Multi-Objective Markov Decision Processes

paper_content:

This paper describes a novel algorithm called CON-MODP for computing Pareto optimal policies for deterministic multi-objective sequential decision problems. CON-MODP is a value iteration based multi-objective dynamic programming algorithm that only computes stationary policies. We observe that for guaranteeing convergence to the unique Pareto optimal set of deterministic stationary policies, the algorithm needs to perform a policy evaluation step on particular policies that are inconsistent in a single state that is being expanded. We prove that the algorithm converges to the Pareto optimal set of value functions and policies for deterministic infinite horizon discounted multi-objective Markov decision processes. Experiments show that CON-MODP is much faster than previous multi-objective value iteration algorithms.
---
paper_title: Bandit Based Monte-Carlo Planning

paper_content:

For large state-space Markovian Decision Problems Monte-Carlo planning is one of the few viable approaches to find near-optimal solutions. In this paper we introduce a new algorithm, UCT, that applies bandit ideas to guide Monte-Carlo planning. In finite-horizon or discounted MDPs the algorithm is shown to be consistent and finite sample bounds are derived on the estimation error due to sampling. Experimental results show that in several domains, UCT is significantly more efficient than its alternatives.
---
paper_title: Monte-Carlo tree search and rapid action value estimation in computer Go

paper_content:

A new paradigm for search, based on Monte-Carlo simulation, has revolutionised the performance of computer Go programs. In this article we describe two extensions to the Monte-Carlo tree search algorithm, which significantly improve the effectiveness of the basic algorithm. When we applied these two extensions to the Go program MoGo, it became the first program to achieve dan (master) level in 9x9 Go. In this article we survey the Monte-Carlo revolution in computer Go, outline the key ideas that led to the success of MoGo and subsequent Go programs, and provide for the first time a comprehensive description, in theory and in practice, of this extended framework for Monte-Carlo tree search.
---
paper_title: Note on Multiple Objective Dynamic Programming

paper_content:

A technique for finding MINSUM and MINMAX solutions to multi-criteria decision problems, called Multi Objective Dynamic Programming, capable of handling a wide range of linear, nonlinear, deterministic and stochastic multi-criteria decision problems, is presented and illustrated. Multiple objectives are considered by defining an adjoint state space and solving a (N + 1) terminal optimisation problem. The method efficiently generates both individual (criterion) optima and multiple criteria solutions in a single pass. Sensitivity analysis on weights over the various objectives is easily performed.
---
paper_title: Linear fitted-q iteration with multiple reward functions

paper_content:

We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a realworld decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.
---
paper_title: Introduction to Reinforcement Learning

paper_content:

From the Publisher: ::: In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability.
---
paper_title: Off-policy temporal-difference learning with function approximation

paper_content:

We introduce the first algorithm for off-policy temporal-difference learning that is stable with linear function approximation. Off-policy learning is of interest because it forms the basis for popular reinforcement learning methods such as Q-learning, which has been known to diverge with linear function approximation, and because it is critical to the practical utility of multi-scale, multi-goal, learning frameworks such as options, HAMs, and MAXQ. Our new algorithm combines TD(λ) over state–action pairs with importance sampling ideas from our previous work. We prove that, given training under any -soft policy, the algorithm converges w.p.1 to a close approximation (as in Tsitsiklis and Van Roy, 1997; Tadic, 2001) to the action-value function for an arbitrary target policy. Variations of the algorithm designed to reduce variance introduce additional bias but are also guaranteed convergent. We also illustrate our method empirically on a small policy evaluation problem. Our current results are limited to episodic tasks with episodes of bounded length. 1Although Q-learning remains the most popular of all reinforcement learning algorithms, it has been known since about 1996 that it is unsound with linear function approximation (see Gordon, 1995; Bertsekas and Tsitsiklis, 1996). The most telling counterexample, due to Baird (1995) is a seven-state Markov decision process with linearly independent feature vectors, for which an exact solution exists, yet This is a re-typeset version of an article published in the Proceedings of the 18th International Conference on Machine Learning (2001). It differs from the original in line and page breaks, is crisper for electronic viewing, and has this funny footnote, but otherwise it is identical to the published article. for which the approximate values found by Q-learning diverge to infinity. This problem prompted the development of residual gradient methods (Baird, 1995), which are stable but much slower than Q-learning, and fitted value iteration (Gordon, 1995, 1999), which is also stable but limited to restricted, weaker-than-linear function approximators. Of course, Q-learning has been used with linear function approximation since its invention (Watkins, 1989), often with good results, but the soundness of this approach is no longer an open question. There exist non-pathological Markov decision processes for which it diverges; it is absolutely unsound in this sense. A sensible response is to turn to some of the other reinforcement learning methods, such as Sarsa, that are also efficient and for which soundness remains a possibility. An important distinction here is between methods that must follow the policy they are learning about, called on-policy methods, and those that can learn from behavior generated by a different policy, called off-policy methods. Q-learning is an off-policy method in that it learns the optimal policy even when actions are selected according to a more exploratory or even random policy. Q-learning requires only that all actions be tried in all states, whereas on-policy methods like Sarsa require that they be selected with specific probabilities. Although the off-policy capability of Q-learning is appealing, it is also the source of at least part of its instability problems. For example, in one version of Baird’s counterexample, the TD(λ) algorithm, which underlies both Qlearning and Sarsa, is applied with linear function approximation to learn the action-value function Q for a given policy π. Operating in an on-policy mode, updating state– action pairs according to the same distribution they would be experienced under π, this method is stable and convergent near the best possible solution (Tsitsiklis and Van Roy, 1997; Tadic, 2001). However, if state-action pairs are updated according to a different distribution, say that generated by following the greedy policy, then the estimated values again diverge to infinity. This and related counterexamples suggest that at least some of the reason for the instability of Q-learning is that it is an off-policy method; they also make it clear that this part of the problem can be studied in a purely policy-evaluation context. Despite these problems, there remains substantial reason for interest in off-policy learning methods. Several researchers have argued for an ambitious extension of reinforcement learning ideas into modular, multi-scale, and hierarchical architectures (Sutton, Precup & Singh, 1999; Parr, 1998; Parr & Russell, 1998; Dietterich, 2000). These architectures rely on off-policy learning to learn about multiple subgoals and multiple ways of behaving from the singular stream of experience. For these approaches to be feasible, some efficient way of combining off-policy learning and function approximation must be found. Because the problems with current off-policy methods become apparent in a policy evaluation setting, it is there that we focus in this paper. In previous work we considered multi-step off-policy policy evaluation in the tabular case. In this paper we introduce the first off-policy policy evaluation method consistent with linear function approximation. Our mathematical development focuses on the episodic case, and in fact on a single episode. Given a starting state and action, we show that the expected offpolicy update under our algorithm is the same as the expected on-policy update under conventional TD(λ). This, together with some variance conditions, allows us to prove convergence and bounds on the error in the asymptotic approximation identical to those obtained by Tsitsiklis and Van Roy (1997; Bertsekas and Tsitsiklis, 1996). 1. Notation and Main Result We consider the standard episodic reinforcement learning framework (see, e.g., Sutton & Barto, 1998) in which a learning agent interacts with a Markov decision process (MDP). Our notation focuses on a single episode of T time steps, s0, a0, r1, s1, a1, r2, . . . , rT , sT , with states st ∈ S, actions at ∈ A, and rewards rt ∈ <. We take the initial state and action, s0 and a0, to be given arbitrarily. Given a state and action, st and at, the next reward, rt+1, is a random variable with mean rt st and the next state, st+1, is chosen with probabilities pt stst+1 . The final state is a special terminal state that may not occur on any preceding time step. Given a state, st, 0 < t < T , the action at is selected according to probability π(st, at) or b(st, at) depending on whether policy π or policy b is in force. We always use π to denote the target policy, the policy that we are learning about. In the on-policy case, π is also used to generate the actions of the episode. In the off-policy case, the actions are instead generated by b, which we call the behavior policy. In either case, we seek an approximation to the action-value function Q : S ×A 7→ < for the target policy π: Q(s, a) = Eπ { rt+1 + · · ·+ γrT | st = s, at = a } , where 0 ≤ γ ≤ 1 is a discount-rate parameter. We consider approximations that are linear in a set of feature vectors {φsa}, s ∈ S, a ∈ A: Q(s, a) ≈ θφsa = n ∑
---
paper_title: Constrained reinforcement learning from intrinsic and extrinsic rewards

paper_content:

The main objective of a standard reinforcement learner is usually defined as maximization of a scalar reward function given externally from the environment. On the other hand, an intrinsically motivated reinforcement learner creates an intrinsic reward function from its own criteria such as curiosity, prediction error, and learning progress. This paper proposes a novel approach to deal with both intrinsic and extrinsic rewards for reinforcement learning from a viewpoint of constrained optimization problem. The extrinsic rewards construct inequality constraints to the stochastic policy while the intrinsic reward determines the current objective function for the learning agent. By integrating policy gradient reinforcement learning algorithms and techniques used in nonlinear programming, our proposed method, named the constrained policy gradient reinforcement learning (CPGRL), maximizes the long-term average intrinsic reward under the inequality constraints induced by the extrinsic rewards. The CPGRL is successfully applied to a simple MDP problem and a control task of a robot arm.
---
paper_title: Reinforcement Learning for MDPs with Constraints

paper_content:

In this article, I will consider Markov Decision Processes with two criteria, each defined as the expected value of an infinite horizon cumulative return. The second criterion is either itself subject to an inequality constraint, or there is maximum allowable probability that the single returns violate the constraint. I describe and discuss three new reinforcement learning approaches for solving such control problems.
---
paper_title: REINFORCEMENT LEARNING IN THE OPERATIONAL MANAGEMENT OF A WATER SYSTEM

paper_content:

In this paper we present a variant of the classic Q-learning algorithm to design an operating policy for the management of a multi-purpose water reservoir. The model-free approach is applied only to a part of the model of the water system, the catchment, while the remainder, the reservoir, is described by mathematical models based on physical characteristics. This algorithm has been tested on the case of the regulation of Lake Como.
---
paper_title: Constructing Stochastic Mixture Policies for Episodic Multiobjective Reinforcement Learning Tasks

paper_content:

Multiobjective reinforcement learning algorithms extend reinforcement learning techniques to problems with multiple conflicting objectives. This paper discusses the advantages gained from applying stochastic policies to multiobjective tasks and examines a particular form of stochastic policy known as a mixture policy. Two methods are proposed for deriving mixture policies for episodic multiobjective tasks from deterministic base policies found via scalarised reinforcement learning. It is shown that these approaches are an efficient means of identifying solutions which offer a superior match to the user's preferences than can be achieved by methods based strictly on deterministic policies.
---
paper_title: Q-Decomposition for Reinforcement Learning Agents

paper_content:

The paper explores a very simple agent design method called Q-decomposition, wherein a complex agent is built from simpler subagents. Each subagent has its own reward function and runs its own reinforcement learning process. It supplies to a central arbitrator the Q-values (according to its own reward function) for each possible action. The arbitrator selects an action maximizing the sum of Q-values from all the subagents. This approach has advantages over designs in which subagents recommend actions. It also has the property that if each subagent runs the Sarsa reinforcement learning algorithm to learn its local Q-function, then a globally optimal policy is achieved. (On the other hand, local Q-learning leads to globally suboptimal behavior.) In some cases, this form of agent decomposition allows the local Q-functions to be expressed by much-reduced state and action spaces. These results are illustrated in two domains that require effective coordination of behaviors.
---
paper_title: Policy Search for Motor Primitives in Robotics

paper_content:

Many motor skills in humanoid robotics can be learned using parametrized motor primitives as done in imitation learning. However, most interesting motor learning problems are high-dimensional reinforcement learning problems often beyond the reach of current methods. In this paper, we extend previous work on policy learning from the immediate reward case to episodic reinforcement learning. We show that this results in a general, common framework also connected to policy gradient methods and yielding a novel algorithm for policy learning that is particularly well-suited for dynamic motor primitives. The resulting algorithm is an EM-inspired algorithm applicable to complex motor learning tasks. We compare this algorithm to several well-known parametrized policy search methods and show that it outperforms them. We apply it in the context of motor learning and show that it can learn a complex Ball-in-a-Cup task using a real Barrett WAM™ robot arm.
---
paper_title: A Reinforcement Learning Approach to Setting Multi-Objective Goals for Energy Demand Management

paper_content:

In order to cope with the unpredictability of the energy market and provide rapid response when supply is strained by demand, an emerging technology, called energy demand management, enables appliances to manage and defer their electricity consumption when price soars. Initial experiments with our multi-agent, power load management simulator, showed a marked reduction in energy consumption when price-based constraints were imposed on the system. However, these results also revealed an unforeseen, negative effect: that reducing consumption for a bounded time interval decreases system stability. The reason is that price-driven control synchronizes the energy consumption of individual agents. Hence price, alone, is an insufficient measure to define global goals in a power load management system. In this article we explore the effectiveness of a multi-objective, system-level goal which combines both price and system stability. We apply the commonly known reinforcement learning framework, enabling the energy distribution system to be both cost saving and stable.
---
paper_title: Multi-criteria reinforcement learning

paper_content:

Ve cOllf:iider multi- criteria f:iequent,ial decision making problems where the vcctor-"valucd evaluations arc compared by a given, fixed total ordering. Condit.ions for the opt.irnality of statiOIl<-l,r}' p()lichs ;-weI the Bellman opti­ malit,y equatio n a re given for a. speci al, but. important class of problems ''v hell the eval­ uation of policies can be computed for the criteria, independently of each other. The anal)'sis requires special cafC as t.he t.opol­ ag,Y int.roduced by polnL\visc convergence a.ncl the or<1cr- topology introduced by the prefer­ ence order arc in general incompatible. Re­ inf orcement. learning algorithms are proposed and analY7,ed.
---
paper_title: On the Limitations of Scalarisation for Multi-objective Reinforcement Learning of Pareto Fronts

paper_content:

Multiobjective reinforcement learning (MORL) extends RL to problems with multiple conflicting objectives. This paper argues for designing MORL systems to produce a set of solutions approximating the Pareto front, and shows that the common MORL technique of scalarisation has fundamental limitations when used to find Pareto-optimal policies. The work is supported by the presentation of three new MORL benchmarks with known Pareto fronts.
---
paper_title: Learning to predict by the methods of temporal differences

paper_content:

This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior. Whereas conventional prediction-learning methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions. Although such temporal-difference methods have been used in Samuel's checker player, Holland's bucket brigade, and the author's Adaptive Heuristic Critic, they have remained poorly understood. Here we prove their convergence and optimality for special cases and relate them to supervised-learning methods. For most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods and they produce more accurate predictions. We argue that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage.
---
paper_title: Multi-objective reinforcement learning algorithm for MOSDMP in unknown environment

paper_content:

In this paper, a new multi-objective reinforcement learning algorithm for multi-objective sequential decision making problems in unknown environment is proposed. The salient characters of the algorithm are: 1) decision maker's objective preference is introduced to guide learning direction; 2) a new measure of comparing action decisions under several objectives based on the fuzzy inference system is defined; 3) fast learning speed can be achieved. Simulation results demonstrate that the proposed algorithm has a good learning performance.
---
paper_title: Policy gradient reinforcement learning for fast quadrupedal locomotion

paper_content:

This paper presents a machine learning approach to optimizing a quadrupedal trot gait for forward speed. Given a parameterized walk designed for a specific robot, we propose using a form of policy gradient reinforcement learning to automatically search the set of possible parameters with the goal of finding the fastest possible walk. We implement and test our approach on a commercially available quadrupedal robot platform, namely the Sony Aibo robot. After about three hours of learning, all on the physical robots and with no human intervention other than to change the batteries, the robots achieved a gait faster than any previously known gait known for the Aibo, significantly outperforming a variety of existing hand-coded and learned solutions.
---
paper_title: Responsive elastic computing

paper_content:

Two production models are candidates for e-science computing: grids enable hardware and software sharing; clouds propose dynamic resource provisioning (elastic computing). Organized sharing is a fundamental requirement for large scientific collaborations; responsiveness, the ability to provide good response time, is a fundamental requirement for seamless integration of the large scale computing resources into everyday use. This paper focuses on a model-free resource provisioning strategy supporting both scenarios. The provisioning problem is modeled as a continuous action-state space, multi-objective reinforcement learning problem, under realistic hypotheses; the high level goals of users, administrators, and shareholders are captured through simple utility functions. We propose an implementation of this reinforcement learning framework, including an approximation of the value function through an Echo State Network, and we validate it on a real dataset.
---
paper_title: Managing power consumption and performance of computing systems using reinforcement learning

paper_content:

Electrical power management in large-scale IT systems such as commercial data-centers is an application area of rapidly growing interest from both an economic and ecological perspective, with billions of dollars and millions of metric tons of CO2 emissions at stake annually. Businesses want to save power without sacrificing performance. This paper presents a reinforcement learning approach to simultaneous online management of both performance and power consumption. We apply RL in a realistic laboratory testbed using a Blade cluster and dynamically varying HTTP workload running on a commercial web applications middleware platform. We embed a CPU frequency controller in the Blade servers' firmware, and we train policies for this controller using a multi-criteria reward signal depending on both application performance and CPU power consumption. Our testbed scenario posed a number of challenges to successful use of RL, including multiple disparate reward functions, limited decision sampling rates, and pathologies arising when using multiple sensor readings as state variables. We describe innovative practical solutions to these challenges, and demonstrate clear performance improvements over both hand-designed policies as well as obvious "cookbook" RL implementations.
---
paper_title: Tree-based reinforcement learning for optimal water reservoir operation

paper_content:

[1] Although being one of the most popular and extensively studied approaches to design water reservoir operations, Stochastic Dynamic Programming is plagued by a dual curse that makes it unsuitable to cope with large water systems: the computational requirement grows exponentially with the number of state variables considered (curse of dimensionality) and an explicit model must be available to describe every system transition and the associated rewards/costs (curse of modeling). A variety of simplifications and approximations have been devised in the past, which, in many cases, make the resulting operating policies inefficient and of scarce relevance in practical contexts. In this paper, a reinforcement-learning approach, called fitted Q-iteration, is presented: it combines the principle of continuous approximation of the value functions with a process of learning off-line from experience to design daily, cyclostationary operating policies. The continuous approximation, performed via tree-based regression, makes it possible to mitigate the curse of dimensionality by adopting a very coarse discretization grid with respect to the dense grid required to design an equally performing policy via Stochastic Dynamic Programming. The learning experience, in the form of a data set generated combining historical observations and model simulations, allows us to overcome the curse of modeling. Lake Como water system (Italy) is used as study site to infer general guidelines on the appropriate setting for the algorithm parameters and to demonstrate the advantages of the approach in terms of accuracy and computational effectiveness compared to traditional Stochastic Dynamic Programming.
---
paper_title: A reinforcement neuro-fuzzy combiner for multiobjective control

paper_content:

This paper proposes a neuro-fuzzy combiner (NFC) with reinforcement learning capability for solving multiobjective control problems. The proposed NFC can combine n existing low-level controllers in a hierarchical way to form a multiobjective fuzzy controller. It is assumed that each low-level (fuzzy or nonfuzzy) controller has been well designed to serve a particular objective. The role of the NFC is to fuse the n actions decided by the n low-level controllers and determine a proper action acting on the environment (plant) at each time step. Hence, the NFC can combine low-level controllers and achieve multiple objectives (goals) at once. The NFC acts like a switch that chooses a proper action from the actions of low-level controllers according to the feedback information from the environment. In fact, the NFC is a soft switch; it allows more than one low-level actions to be active with different degrees through fuzzy combination at each time step. An NFC can be designed by the trial-and-error approach if enough a priori knowledge is available, or it can be obtained by supervised learning if precise input/output training data are available. In the more practical cases when there is no instructive teaching information available, the NFC can learn by itself using the proposed reinforcement learning scheme. Adopted with reinforcement learning capability, the NFC can learn to achieve desired multiobjectives simultaneously through the rough reinforcement feedback from the environment, which contains only critic information such as "success (good)" or "failure (bad)" for each desired objective. Computer simulations have been conducted to illustrate the performance and applicability of the proposed architecture and learning scheme.
---
paper_title: An empirical comparison of two common multiobjective reinforcement learning algorithms

paper_content:

In this paper we provide empirical data of the performance of the two most commonly used multiobjective reinforcement learning algorithms against a set of benchmarks. First, we describe a methodology that was used in this paper. Then, we carefully describe the details and properties of the proposed problems and how those properties influence the behavior of tested algorithms. We also introduce a testing framework that will significantly improve future empirical comparisons of multiobjective reinforcement learning algorithms. We hope this testing environment eventually becomes a central repository of test problems and algorithms The empirical results clearly identify features of the test problems which impact on the performance of each algorithm, demonstrating the utility of empirical testing of algorithms on problems with known characteristics.
---
paper_title: Policy Gradient Methods for Reinforcement Learning with Function Approximation

paper_content:

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable. In this paper we explore an alternative approach in which the policy is explicitly represented by its own function approximator, independent of the value function, and is updated according to the gradient of expected reward with respect to the policy parameters. Williams's REINFORCE method and actor-critic methods are examples of this approach. Our main new result is to show that the gradient can be written in a form suitable for estimation from experience aided by an approximate action-value or advantage function. Using this result, we prove for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy.
---
paper_title: Tree-based batch mode reinforcement learning

paper_content:

Reinforcement learning aims to determine an optimal control policy from interaction with a system or from observations gathered from a system. In batch mode, it can be achieved by approximating the so-called Q-function based on a set of four-tuples (xt, ut , rt, xt+1) where xt denotes the system state at time t, ut the control action taken, rt the instantaneous reward obtained and xt+1 the successor state of the system, and by determining the control policy from this Q-function. The Q-function approximation may be obtained from the limit of a sequence of (batch mode) supervised learning problems. Within this framework we describe the use of several classical tree-based supervised learning methods (CART, Kd-tree, tree bagging) and two newly proposed ensemble algorithms, namely extremely and totally randomized trees. We study their performances on several examples and find that the ensemble methods based on regression trees perform well in extracting relevant information about the optimal control policy from sets of four-tuples. In particular, the totally randomized trees give good results while ensuring the convergence of the sequence, whereas by relaxing the convergence constraint even better accuracy results are provided by the extremely randomized trees.
---
paper_title: Multi-agent Multi-objective Learning Using Heuristically Accelerated Reinforcement Learning

paper_content:

This paper introduces two new algorithms aimed at solving multi-agent multi-objective reinforcement learning problems in which the learning agent must not only interact with multiples agents but also consider various objectives (or criteria) in order to solve the problem. The main concept behind the proposed algorithms is a modular approach that is used to divide the multiple objectives in modules, and making each one of these modules learn a different objective with different Action-Value and reinforcement functions. Besides the decomposition of objectives, both algorithms use a heuristic function to accelerate the learning process. The first algorithm learns one objective at a time, iterating along the objectives, while the second proposed algorithm also divides the problem in sub-problems but learns every objective simultaneously. The Predator-Prey problem was chosen to compare the performance of both proposed solutions with well known algorithms. In this problem, the learning agent plays the role of the prey and must learn to find food in a fixed position of a grid world while being pursued by the predator. The considered objectives are finding food and avoiding the predator. As the results shows, decomposing a multi-objective problem in sub-problems and using heuristics makes the learning process faster and easier to implement. We notice that the first algorithm introduced in this paper learns faster, but it is more difficult to implement in a real world environment.
---
paper_title: Linear fitted-q iteration with multiple reward functions

paper_content:

We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a realworld decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.
---
paper_title: Parallel reinforcement learning for weighted multi-criteria model with adaptive margin

paper_content:

Reinforcement learning (RL) for a linear family of tasks is described in this paper. The key of our discussion is nonlinearity of the optimal solution even if the task family is linear; we cannot obtain the optimal policy using a naive approach. Although an algorithm exists for calculating the equivalent result to Q-learning for each task simultaneously, it presents the problem of explosion of set sizes. We therefore introduce adaptive margins to overcome this difficulty.
---
paper_title: REINFORCEMENT LEARNING IN THE OPERATIONAL MANAGEMENT OF A WATER SYSTEM

paper_content:

In this paper we present a variant of the classic Q-learning algorithm to design an operating policy for the management of a multi-purpose water reservoir. The model-free approach is applied only to a part of the model of the water system, the catchment, while the remainder, the reservoir, is described by mathematical models based on physical characteristics. This algorithm has been tested on the case of the regulation of Lake Como.
---
paper_title: Dynamic preferences in multi-criteria reinforcement learning

paper_content:

The current framework of reinforcement learning is based on maximizing the expected returns based on scalar rewards. But in many real world situations, tradeoffs must be made among multiple objectives. Moreover, the agent's preferences between different objectives may vary with time. In this paper, we consider the problem of learning in the presence of time-varying preferences among multiple objectives, using numeric weights to represent their importance. We propose a method that allows us to store a finite number of policies, choose an appropriate policy for any weight vector and improve upon it. The idea is that although there are infinitely many weight vectors, they may be well-covered by a small number of optimal policies. We show this empirically in two domains: a version of the Buridan's ass problem and network routing.
---
paper_title: Learning all optimal policies with multiple criteria

paper_content:

We describe an algorithm for learning in the presence of multiple criteria. Our technique generalizes previous approaches in that it can learn optimal policies for all linear preference assignments over the multiple reward criteria at once. The algorithm can be viewed as an extension to standard reinforcement learning for MDPs where instead of repeatedly backing up maximal expected rewards, we back up the set of expected rewards that are maximal for some set of linear preferences (given by a weight vector, w). We present the algorithm along with a proof of correctness showing that our solution gives the optimal policy for any linear preference function. The solution reduces to the standard value iteration algorithm for a specific weight vector, w.
---
paper_title: Multi-objective reinforcement learning method for acquiring all pareto optimal policies simultaneously

paper_content:

This paper studies multi-objective reinforcement learning problems in which an agent gains multiple rewards. In ordinary multi-objective reinforcement learning methods, only a single Pareto optimal policy is acquired by the scalarizing method which uses the weighted sum of the reward vector, and therefore different Pareto optimal policies are acquired by changing the weight vector and by performing the methods again. On the other hand, a method in which all Pareto optimal policies are acquired simultaneously is proposed for problems whose environment model is known. By using the idea of the method, we propose a method that acquires all Pareto optimal policies simultaneously for the multi-objective reinforcement learning problems whose environment model is unknown. Furthermore, we show theoretically and experimentally that the proposed method can find the Pareto optimal policies.
---
paper_title: Tree-based batch mode reinforcement learning

paper_content:

Reinforcement learning aims to determine an optimal control policy from interaction with a system or from observations gathered from a system. In batch mode, it can be achieved by approximating the so-called Q-function based on a set of four-tuples (xt, ut , rt, xt+1) where xt denotes the system state at time t, ut the control action taken, rt the instantaneous reward obtained and xt+1 the successor state of the system, and by determining the control policy from this Q-function. The Q-function approximation may be obtained from the limit of a sequence of (batch mode) supervised learning problems. Within this framework we describe the use of several classical tree-based supervised learning methods (CART, Kd-tree, tree bagging) and two newly proposed ensemble algorithms, namely extremely and totally randomized trees. We study their performances on several examples and find that the ensemble methods based on regression trees perform well in extracting relevant information about the optimal control policy from sets of four-tuples. In particular, the totally randomized trees give good results while ensuring the convergence of the sequence, whereas by relaxing the convergence constraint even better accuracy results are provided by the extremely randomized trees.
---
paper_title: Multi-objective fitted Q-iteration: Pareto frontier approximation in one single run

paper_content:

We present a novel batch-mode Reinforcement Learning approach for the design of optimal controllers in the presence of multiple objectives. The algorithm is an extension of Fitted Q-iteration (FQI) that enables to design the controller for all the linear combinations of preferences (weights) assigned to the objectives in a single run. The key idea of multi-objective FQI (MOFQI) is to enlarge the continuos approximation of the value function, which is performed by single-objective FQI over the state-control space, also to the weight space. The bacth-mode nature of the algorithm makes it possible the enrichment of the learning data with nearly no additional computational cost with respect to a single-objective formulation on the same system. The approach was tested on a simple test case study concerning the optimal operation of a two-objective water reservoir, where MOFQI algorithm proved to be computationally preferable over repeatedly running FQI for different weight values when more than five points on the Pareto frontier are considered.
---
paper_title: Solving Multi-objective Reinforcement Learning Problems by EDA-RL - Acquisition of Various Strategies

paper_content:

EDA-RL, Estimation of Distribution Algorithms for Reinforcement Learning Problems, have been proposed by us recently. The EDA-RL can improve policies by EDA scheme: First, select better episodes. Secondly, estimate probabilistic models, i.e., policies, and finally, interact with the environment for generating new episodes. In this paper, the EDA-RL is extended for Multi-Objective Reinforcement Learning Problems, where reward is given by several criteria. By incorporating the notions in Evolutionary Multi-Objective Optimization, the proposed method is enable to acquire various strategies by a single run.
---
paper_title: EDA-RL: estimation of distribution algorithms for reinforcement learning problems

paper_content:

By making use of probabilistic models, (EDAs) can outperform conventional evolutionary computations. In this paper, EDAs are extended to solve reinforcement learning problems which arise naturally in a framework for autonomous agents. In reinforcement learning problems, we have to find out better policies of agents such that the rewards for agents in the future are increased. In general, such a policy can be represented by conditional probabilities of the agents' actions, given the perceptual inputs. In order to estimate such a conditional probability distribution, Conditional Random Fields (CRFs) by Lafferty et al. is newly introduced into EDAs in this paper. The reason for adopting CRFs is that CRFs are able to learn conditional probabilistic distributions from a large amount of input-output data, i.e., episodes in the case of reinforcement learning problems. On the other hand, conventional reinforcement learning algorithms can only learn incrementally. Computer simulations of Probabilistic Transition Problems and Perceptual Aliasing Maze Problems show the effectiveness of EDA-RL.
---
paper_title: An Evolutionary Algorithm with Advanced Goal and Priority Specification for Multi-objective Optimization

paper_content:

This paper presents an evolutionary algorithm with a new goal-sequence domination scheme for better decision support in multi-objective optimization. The approach allows the inclusion of advanced hard/soft priority and constraint information on each objective component, and is capable of incorporating multiple specifications with overlapping or non-overlapping objective functions via logical 'OR' and 'AND' connectives to drive the search towards multiple regions of trade-off. In addition, we propose a dynamic sharing scheme that is simple and adaptively estimated according to the on-line population distribution without needing any a priori parameter setting. Each feature in the proposed algorithm is examined to show its respective contribution, and the performance of the algorithm is compared with other evolutionary optimization methods. It is shown that the proposed algorithm has performed well in the diversity of evolutionary search and uniform distribution of non-dominated individuals along the final trade-offs, without significant computational effort. The algorithm is also applied to the design optimization of a practical servo control system for hard disk drives with a single voice-coil-motor actuator. Results of the evolutionary designed servo control system show a superior closed-loop performance compared to classical PID or RPT approaches.
---
paper_title: Evolutionary Algorithms for Solving Multi-Objective Problems

paper_content:

List of Figures. List of Tables. Preface. Foreword. 1. Basic Concepts. 2. Evolutionary Algorithm MOP Approaches. 3. MOEA Test Suites. 4. MOEA Testing and Analysis. 5. MOEA Theory and Issues. 3. MOEA Theoretical Issues. 6. Applications. 7. MOEA Parallelization. 8. Multi-Criteria Decision Making. 9. Special Topics. 10. Epilog. Appendix A: MOEA Classification and Technique Analysis. Appendix B: MOPs in the Literature. Appendix C: Ptrue & PFtrue for Selected Numeric MOPs. Appendix D: Ptrue & PFtrue for Side-Constrained MOPs. Appendix E: MOEA Software Availability. Appendix F: MOEA-Related Information. Index. References.
---
paper_title: Multi-criteria reinforcement learning

paper_content:

Ve cOllf:iider multi- criteria f:iequent,ial decision making problems where the vcctor-"valucd evaluations arc compared by a given, fixed total ordering. Condit.ions for the opt.irnality of statiOIl<-l,r}' p()lichs ;-weI the Bellman opti­ malit,y equatio n a re given for a. speci al, but. important class of problems ''v hell the eval­ uation of policies can be computed for the criteria, independently of each other. The anal)'sis requires special cafC as t.he t.opol­ ag,Y int.roduced by polnL\visc convergence a.ncl the or<1cr- topology introduced by the prefer­ ence order arc in general incompatible. Re­ inf orcement. learning algorithms are proposed and analY7,ed.
---
paper_title: Evolutionary computation for reinforcement learning

paper_content:

Algorithms for evolutionary computation, which simulate the process of natural selection to solve optimization problems, are an effective tool for discovering high-performing reinforcement-learning policies. Because they can automatically find good representations, handle continuous action spaces, and cope with partial observability, evolutionary reinforcement-learning approaches have a strong empirical track record, sometimes significantly outperforming temporal-difference methods. This chapter surveys research on the application of evolutionary computation to reinforcement learning, overviewing methods for evolving neural-network topologies and weights, hybrid methods that also use temporal-difference methods, coevolutionary methods for multi-agent settings, generative and developmental systems, and methods for on-line evolutionary reinforcement learning.
---
paper_title: Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies

paper_content:

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.
---
paper_title: Empirical evaluation methods for multiobjective reinforcement learning algorithms

paper_content:

While a number of algorithms for multiobjective reinforcement learning have been proposed, and a small number of applications developed, there has been very little rigorous empirical evaluation of the performance and limitations of these algorithms. This paper proposes standard methods for such empirical evaluation, to act as a foundation for future comparative studies. Two classes of multiobjective reinforcement learning algorithms are identified, and appropriate evaluation metrics and methodologies are proposed for each class. A suite of benchmark problems with known Pareto fronts is described, and future extensions and implementations of this benchmark suite are discussed. The utility of the proposed evaluation methods are demonstrated via an empirical comparison of two example learning algorithms.
---
paper_title: Learning controllers for human-robot interaction

paper_content:

In order for robots to assist and interact with humans, they must be socially intelligent. Social intelligence is the ability to communicate and understand meaning through social interaction. Artificial intelligence can be broadly described, as an effort to describe and simulate the property of human intelligence inside of a computational model. In most cases, this simulation happens in a vacuum. An agent, such as a robot, maintains a computational model which includes all information required to make decisions. This internal computational representation is what we consider its intellect. Information may enter this model through perception, and be expressed in the form of action. This separation of knowing and doing can be quite effective for representing certain types of intelligence. However it does not lend itself to simulating social cognition. ::: In order to communicate socially, an agent must be able to affect change in the mental representation of other agents, as well as the physical world. However, social interaction and the creation of meaning is inherently different than interactions with the physical world. Because there are no mathematical models which describe how actions and perceptions affect the mental representations of a human, we cannot hope to build an interactive agent by directly simulating this process. For this reason, when building artificial social intelligence, we need to pay attention to prevailing theories on how humans learn. Many popular theories from cognitive science, social psychology and language development suggest that action and perception are not subordinate to mental representations. Instead, mental representations are a result of action and perception that results from an agent's interaction with an environment and other agents. In particular, social learning theory says that the process which allows agents to understand one another happens from the ground up, starting with action and perception, and resulting in the shared mental representations, and understanding of how to affect change in the representations of others. ::: This thesis addresses the problem of building social intelligence into robotic systems using computational learning and adaptive control. We focus on the problem of how to use decision theoretic planning for learning to interact with humans from the bottom up. We first examine the use of affect recognition in designing human-friendly control strategies. Next, we address the problem of defining subjective measures of interactivity by leveraging human expertise. Finally, we define and evaluate a method for participating in the process of socially situated cognition. We emphasize learning to predict and modulate observable responses of the human rather than attempting to directly infer their mental or emotional states. The effectiveness of this method is demonstrated experimentally using custom robotic systems.
---
paper_title: Linear fitted-q iteration with multiple reward functions

paper_content:

We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a realworld decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.
---
paper_title: GIS and Intelligent Agents for Multiobjective Natural Resource Allocation: A Reinforcement Learning Approach

paper_content:

An important component of natural resource management is determining how to allocate resources within a landscape to different stakeholders in a manner that satisfies multiple objectives. Developing decision making tools for assisting natural resource allocation is a challenging endeavor as stakeholders' objectives typically exist at varying spatial scales, their actions are defined by the spatial constraints in which they operate, and the spatial distribution of resources can be altered due to system disturbances. The nature of such challenges suggests the need for a geographic approach that can investigate these spatial complexities in order to generate a suitable set of solutions. The objective of this study is to develop and evaluate an Intelligent Agent Model for multiobjective natural resource allocation. The model integrates agent-based modeling in a GIS environment with reinforcement learning – a heuristic method for generating, evaluating, and improving multiobjective decision making solutions. The model is implemented by simulating a forest management scenario in which agents that represent forest companies learn how to harvest trees in a manner that maximizes economic return while minimizing the adverse ecological impact to the surrounding landscape. In addition, the model simulates forest disturbances of varying frequencies and intensities to determine how disturbance events affect the decision-making ability of agents. The model is validated to demonstrate that it can provide practical solutions to natural resource decision making.
---
paper_title: Collision avoidance in a behavior-based mobile robot design

paper_content:

The collision avoidance behavior in a recursive nested control structure design is discussed. A formulation of a repulsion force based on measurements of ultrasonic range and tactile force and moment is given. The avoidance behavior adapts to the dynamics of the mobile robot. The realization details emphasize the importance of keeping the system bandwidth as large as possible to increase the reflexiveness of the avoidance behavior. Real-world experiments confirm the effectiveness and robustness of the proposed procedure. >
---
paper_title: Local episode-based learning of multi-objective behavior coordination for a mobile robot in dynamic environments

paper_content:

This paper is concerned with a local learning method of a multi-objective behavior coordination for a mobile robot. The multiobjective behavior coordination plays a role in integrating outputs of basic behavioral modules. A behavioral weight is assigned to each behavioral module represented by fuzzy rules, production rules, and so on. By updating these behavioral weights, the mobile robot can take a multi-objective situated action. However, the coordination rule is designed suitably static environments and the mobile robot must learn or update coordination rule in dynamic environments with moving obstacles. Therefore, we propose a local episode-based learning which is a learning method using self-reference of the relationship between previous perception and action in short-term memory.
---
paper_title: A Reinforcement Learning Approach to Setting Multi-Objective Goals for Energy Demand Management

paper_content:

In order to cope with the unpredictability of the energy market and provide rapid response when supply is strained by demand, an emerging technology, called energy demand management, enables appliances to manage and defer their electricity consumption when price soars. Initial experiments with our multi-agent, power load management simulator, showed a marked reduction in energy consumption when price-based constraints were imposed on the system. However, these results also revealed an unforeseen, negative effect: that reducing consumption for a bounded time interval decreases system stability. The reason is that price-driven control synchronizes the energy consumption of individual agents. Hence price, alone, is an insufficient measure to define global goals in a power load management system. In this article we explore the effectiveness of a multi-objective, system-level goal which combines both price and system stability. We apply the commonly known reinforcement learning framework, enabling the energy distribution system to be both cost saving and stable.
---
paper_title: Multiobjective dynamic programming for forest resource management

paper_content:

Abstract Two important properties of most forest resource management problems, i.e. multiple objectives and uncertainty, have received much attention in recent decades. Various methods, such as multiobjective optimization techniques, stochastic dynamic programming, etc., have been introduced to address these two issues, respectively. The Multiobjective Dynamic Programming (MODP) method is introduced in this paper to take the two issues into account simultaneously. The MODP problem is formulated as a Multiobjective Linear Programming (MOLP) problem and solved using the multicriteria simplex method. The relation between the set of non-dominated extreme point solutions of the MOLP and the set of non-dominated stationary policies is discussed. A numerical example is used to illustrate this method.
---
paper_title: Multi-objective optimization of freeway traffic flow via a fuzzy reinforcement learning method

paper_content:

A fuzzy approach to reinforcement learning in multi-objective optimization problem of freeway traffic flow control and dynamic route guidance is presented. The problem domain, a freeway network integration management application considers the efficiency and equity of system, is formulated as a distributed fuzzy reinforcement learning problem. The Gini coefficient is adopted in this study as an indicator of equity. The DFRL approach was implemented via a multi-agent control architecture where the decision agent was assigned to each of the on-ramp or VMS. The reward of each agent is simultaneously updating a single shared policy. The control strategy's effect is demonstrated through its application to the simple freeway network. Analyses of simulation results using this approach show the equity of the system have a significant improvement over traditional control, especially for the case of large traffic demand. Using the DFRL approach, Compared with traditional methods, the network's Gini coefficient has fallen by 30% or more.
---
paper_title: Multi-criteria reinforcement learning

paper_content:

Ve cOllf:iider multi- criteria f:iequent,ial decision making problems where the vcctor-"valucd evaluations arc compared by a given, fixed total ordering. Condit.ions for the opt.irnality of statiOIl<-l,r}' p()lichs ;-weI the Bellman opti­ malit,y equatio n a re given for a. speci al, but. important class of problems ''v hell the eval­ uation of policies can be computed for the criteria, independently of each other. The anal)'sis requires special cafC as t.he t.opol­ ag,Y int.roduced by polnL\visc convergence a.ncl the or<1cr- topology introduced by the prefer­ ence order arc in general incompatible. Re­ inf orcement. learning algorithms are proposed and analY7,ed.
---
paper_title: SAVES: A sustainable multiagent application to conserve building energy considering occupants

paper_content:

This paper describes an innovative multiagent system called SAVES with the goal of conserving energy in commercial buildings. We specifically focus on an application to be deployed in an existing university building that provides several key novelties: (i) jointly performed with the university facility management team, SAVES is based on actual occupant preferences and schedules, actual energy consumption and loss data, real sensors and hand-held devices, etc.; (ii) it addresses novel scenarios that require negotiations with groups of building occupants to conserve energy; (iii) it focuses on a non-residential building, where human occupants do not have a direct financial incentive in saving energy and thus requires a different mechanism to effectively motivate occupants; and (iv) SAVES uses a novel algorithm for generating optimal MDP policies that explicitly consider multiple criteria optimization (energy and personal comfort) as well as uncertainty over occupant preferences when negotiating energy reduction -- this combination of challenges has not been considered in previous MDP algorithms. In a validated simulation testbed, we show that SAVES substantially reduces the overall energy consumption compared to the existing control method while achieving comparable average satisfaction levels for occupants. As a real-world test, we provide results of a trial study where SAVES is shown to lead occupants to conserve energy in real buildings.
---
paper_title: Responsive elastic computing

paper_content:

Two production models are candidates for e-science computing: grids enable hardware and software sharing; clouds propose dynamic resource provisioning (elastic computing). Organized sharing is a fundamental requirement for large scientific collaborations; responsiveness, the ability to provide good response time, is a fundamental requirement for seamless integration of the large scale computing resources into everyday use. This paper focuses on a model-free resource provisioning strategy supporting both scenarios. The provisioning problem is modeled as a continuous action-state space, multi-objective reinforcement learning problem, under realistic hypotheses; the high level goals of users, administrators, and shareholders are captured through simple utility functions. We propose an implementation of this reinforcement learning framework, including an approximation of the value function through an Echo State Network, and we validate it on a real dataset.
---
paper_title: Managing power consumption and performance of computing systems using reinforcement learning

paper_content:

Electrical power management in large-scale IT systems such as commercial data-centers is an application area of rapidly growing interest from both an economic and ecological perspective, with billions of dollars and millions of metric tons of CO2 emissions at stake annually. Businesses want to save power without sacrificing performance. This paper presents a reinforcement learning approach to simultaneous online management of both performance and power consumption. We apply RL in a realistic laboratory testbed using a Blade cluster and dynamically varying HTTP workload running on a commercial web applications middleware platform. We embed a CPU frequency controller in the Blade servers' firmware, and we train policies for this controller using a multi-criteria reward signal depending on both application performance and CPU power consumption. Our testbed scenario posed a number of challenges to successful use of RL, including multiple disparate reward functions, limited decision sampling rates, and pathologies arising when using multiple sensor readings as state variables. We describe innovative practical solutions to these challenges, and demonstrate clear performance improvements over both hand-designed policies as well as obvious "cookbook" RL implementations.
---
paper_title: Safe physical human robot interaction-past, present and future

paper_content:

When a robot physically interacts with a human user, the requirements should be drastically changed. The most important requirement is the safety of the human user in the sense that robot should not harm the human in any situation. During the last few years, research has been focused on various aspects of safe physical human robot interaction. This paper provides a review of the work on safe physical interaction of robotic systems sharing their workspace with human users (especially elderly people). Three distinct areas of research are identified: interaction safety assessment, interaction safety through design, and interaction safety through planning and control. The paper then highlights the current challenges and available technologies and points out future research directions for realization of a safe and dependable robotic system for human users.
---
paper_title: Water reservoir control under economic, social and environmental constraints

paper_content:

Although great progress has been made in the last 40 years, efficient operation of water reservoir systems still remains a very active research area. The combination of multiple water uses, non-linearities in the model and in the objectives, strong uncertainties in inputs and high dimensional state make the problem challenging and intriguing. The purpose of this paper is to review, in a strict Control Theory perspective, recent and significant advances in designing management policies for water reservoir networks, under economic, social and environmental constraints. A general and thorough problem formulation is provided, along with a description of traditional solution techniques, their limitations and possible alternative approaches.
---
paper_title: Improving wet clutch engagement with reinforcement learning

paper_content:

A common approach when applying reinforcement learning to address control problems is that of first learning a policy based on an approximated model of the plant, whose behavior can be quickly and safely explored in simulation; and then implementing the obtained policy to control the actual plant. Here we follow this approach to learn to engage a transmission clutch, with the aim of obtaining a rapid and smooth engagement, with a small torque loss. Using an approximated model of a wet clutch, which simulates a portion of the whole engagement, we first learn an open loop control signal, which is then transferred on the actual wet clutch, and improved by further learning with a different reward function, based on the actual torque loss observed.
---
paper_title: Multi Objective Resource Scheduling in LTE Networks Using Reinforcement Learning

paper_content:

The use of the intelligent packet scheduling process is absolutely necessary in order to make the radio resources usage more efficient in recent high-bit-rate demanding radio access technologies such as Long Term Evolution LTE. Packet scheduling procedure works with various dispatching rules with different behaviors. In the literature, the scheduling disciplines are applied for the entire transmission sessions and the scheduler performance strongly depends on the exploited discipline. The method proposed in this paper aims to discuss how a straightforward schedule can be provided within the transmission time interval TTI sub-frame using a mixture of dispatching disciplines per TTI instead of a single rule adopted across the whole transmission. This is to maximize the system throughput while assuring the best user fairness. This requires adopting a policy of how to mix the rules and a refinement procedure to call the best rule each time. Two scheduling policies are proposed for how to mix the rules including use of Q learning algorithm for refining the policies. Simulation results indicate that the proposed methods outperform the existing scheduling techniques by maximizing the system throughput without harming the user fairness performance.
---
paper_title: Enhanced Q-learning algorithm for dynamic power management with performance constraint

paper_content:

This paper presents a novel power management techniques based on enhanced Q-learning algorithms. By exploiting the submodularity and monotonic structure in the cost function of a power management system, the enhanced Q-learning algorithm is capable of exploring ideal trade-offs in the power-performance design space and converging to a better power management policy. We further propose a linear adaption algorithm that adapts the Lagrangian multiplier ? to search for the power management policy that minimizes the power consumption while delivering the exact required performance. Experimental results show that, comparing to the existing expert-based power management, the proposed Q-learning based power management achieves up to 30% and 60% reduction in power saving for synthetic workload and real workload, respectively while in average maintain a performance within 7% variation of the given constraint.
---
paper_title: Dynamic scheduling of maintenance tasks in the petroleum industry: A reinforcement approach

paper_content:

Petroleum industry production systems are highly automatized. Maintenance of such systems is vital, not only to maintain production efficiency but also to insure minimal safety levels. Maintenance task scheduling is difficult since some tasks are already identified because they must be done repeatedly, and other tasks need to be identified dynamically. In this paper, we present a multi-agent approach for the dynamic maintenance task scheduling for a petroleum industry production system. Agents simultaneously insure effective maintenance scheduling and the continuous improvement of the solution quality by means of reinforcement learning, using the SARSA algorithm. Reinforcement learning allows the agents to adapt, learning the best behaviors for their various roles without reducing the performance or reactivity. To demonstrate the innovation of our approach, we include a computer simulation of our model and the results of experimentation applying our model to an Algerian petroleum refinery.
---
paper_title: Reinforcement Learning for Call Admission Control and Routing under Quality of Service Constraints in Multimedia Networks

paper_content:

In this paper, we solve the call admission control and routing problem in multimedia networks via reinforcement learning (RL). The problem requires that network revenue be maximized while simultaneously meeting quality of service constraints that forbid entry into certain states and use of certain actions. The problem can be formulated as a constrained semi-Markov decision process. We show that RL provides a solution to this problem and is able to earn significantly higher revenues than alternative heuristics.
---
paper_title: Multi-objective fitted Q-iteration: Pareto frontier approximation in one single run

paper_content:

We present a novel batch-mode Reinforcement Learning approach for the design of optimal controllers in the presence of multiple objectives. The algorithm is an extension of Fitted Q-iteration (FQI) that enables to design the controller for all the linear combinations of preferences (weights) assigned to the objectives in a single run. The key idea of multi-objective FQI (MOFQI) is to enlarge the continuos approximation of the value function, which is performed by single-objective FQI over the state-control space, also to the weight space. The bacth-mode nature of the algorithm makes it possible the enrichment of the learning data with nearly no additional computational cost with respect to a single-objective formulation on the same system. The approach was tested on a simple test case study concerning the optimal operation of a two-objective water reservoir, where MOFQI algorithm proved to be computationally preferable over repeatedly running FQI for different weight values when more than five points on the Pareto frontier are considered.
---
paper_title: A multiobjective reinforcement learning approach to water resources systems operation: Pareto frontier approximation in a single run

paper_content:

[1] The operation of large-scale water resources systems often involves several conflicting and noncommensurable objectives. The full characterization of tradeoffs among them is a necessary step to inform and support decisions in the absence of a unique optimal solution. In this context, the common approach is to consider many single objective problems, resulting from different combinations of the original problem objectives, each one solved using standard optimization methods based on mathematical programming. This scalarization process is computationally very demanding as it requires one optimization run for each trade-off and often results in very sparse and poorly informative representations of the Pareto frontier. More recently, bio-inspired methods have been applied to compute an approximation of the Pareto frontier in one single run. These methods allow to acceptably cover the full extent of the Pareto frontier with a reasonable computational effort. Yet, the quality of the policy obtained might be strongly dependent on the algorithm tuning and preconditioning. In this paper we propose a novel multiobjective Reinforcement Learning algorithm that combines the advantages of the above two approaches and alleviates some of their drawbacks. The proposed algorithm is an extension of fitted Q-iteration (FQI) that enables to learn the operating policies for all the linear combinations of preferences (weights) assigned to the objectives in a single training process. The key idea of multiobjective FQI (MOFQI) is to enlarge the continuous approximation of the value function, that is performed by single objective FQI over the state-decision space, also to the weight space. The approach is demonstrated on a real-world case study concerning the optimal operation of the HoaBinh reservoir on the Da river, Vietnam. MOFQI is compared with the reiterated use of FQI and a multiobjective parameterization-simulation-optimization (MOPSO) approach. Results show that MOFQI provides a continuous approximation of the Pareto front with comparable accuracy as the reiterated use of FQI. MOFQI outperforms MOPSO when no a priori knowledge on the operating policy shape is available, while produces slightly less accurate solutions when MOPSO can exploit such knowledge.
---
paper_title: Distributed W-Learning: Multi-Policy Optimization in Self-Organizing Systems

paper_content:

Large-scale agent-based systems are required to self-optimize towards multiple, potentially conflicting, policies of varying spatial and temporal scope. As a result, not all agents may be implementing all policies at all times, resulting in agent heterogeneity. As agents share their operating environment, significant dependencies can arise between agents and therefore between policy implementations. To address self-optimization in the presence of agent heterogeneity, policy dependency and the lack of global knowledge that is inherent in large-scale decentralized environments, we propose Distributed W-Learning (DWL). DWL is a reinforcement learning (RL)-based algorithm for collaborative agent-based self-optimization towards multiple policies, which relies only on local interactions and learning. We have evaluated the DWL algorithm in a simulation of a self-organizing urban traffic control (UTC) system and show that using DWL can improve the performance of multiple policies deployed simultaneously, even over corresponding single-policy deployments. For example, in UTC, optimizing simultaneously for cars and public transport vehicles reduces the waiting times of cars to 78% of their waiting times in the best-performing single-policy deployment that optimizes for cars only, while also outperforming the widely-deployed round-robin and saturation balancing traffic controllers that we used as baselines.
---
paper_title: Multi-objective reinforcement learning based routing in cognitive radio networks: Walking in a random maze

paper_content:

The routing procedure in cognitive radio networks with dynamic spectrum activities is studied. The spectrum statistics are assumed to be unknown. Moreover, the performance is measured using multiple metrics like average delay and packet loss rate. To address the challenges of randomness, uncertainty and multiple metrics, the multi-objective reinforcement learning algorithm is applied for the routing in cognitive radio networks. The effectiveness of the learning procedure is demonstrated by numerical simulations.
---
paper_title: Risk-Sensitive Reinforcement Learning Applied to Control under Constraints

paper_content:

In this paper, we consider Markov Decision Processes (MDPs) with error states. Error states are those states entering which is undesirable or dangerous. We define the risk with respect to a policy as the probability of entering such a state when the policy is pursued. We consider the problem of finding good policies whose risk is smaller than some user-specified threshold, and formalize it as a constrained MDP with two criteria. The first criterion corresponds to the value function originally given. We will show that the risk can be formulated as a second criterion function based on a cumulative return, whose definition is independent of the original value function. We present a model free, heuristic reinforcement learning algorithm that aims at finding good deterministic policies. It is based on weighting the original value function and the risk. The weight parameter is adapted in order to find a feasible solution for the constrained problem that has a good performance with respect to the value function. The algorithm was successfully applied to the control of a feed tank with stochastic inflows that lies upstream of a distillation column. This control task was originally formulated as an optimal control problem with chance constraints, and it was solved under certain assumptions on the model to obtain an optimal solution. The power of our learning algorithm is that it can be used even when some of these restrictive assumptions are relaxed.
---
paper_title: A Theory of Goal-Oriented MDPs with Dead Ends

paper_content:

Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI, especially in probabilistic planning. They describe a wide range of scenarios but make the restrictive assumption that the goal is reachable from any state, i.e., that dead-end states do not exist. Because of this, SSPs are unable to model various scenarios that may have catastrophic events (e.g., an airplane possibly crashing if it flies into a storm). Even though MDP algorithms have been used for solving problems with dead ends, a principled theory of SSP extensions that would allow dead ends, including theoretically sound algorithms for solving such MDPs, has been lacking. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.
---
paper_title: Stochastic safest and shortest path problems

paper_content:

Optimal solutions to Stochastic Shortest Path Problems (SSPs) usually require that there exists at least one policy that reaches the goal with probability 1 from the initial state. This condition is very strong and prevents from solving many interesting problems, for instance where all possible policies reach some dead-end states with a positive probability. We introduce a more general and richer dual optimization criterion, which minimizes the average (undiscounted) cost of only paths leading to the goal among all policies that maximize the probability to reach the goal. We present policy update equations in the form of dynamic programming for this new dual criterion, which are different from the standard Bellman equations. We demonstrate that our equations converge in infinite horizon without any condition on the structure of the problem or on its policies, which actually extends the class of SSPs that can be solved. We experimentally show that our dual criterion provides wellfounded solutions to SSPs that can not be solved by the standard criterion, and that using a discount factor with the latter certainly provides solution policies but which are not optimal considering our well-founded criterion.
---
paper_title: Markov decision processes and regular events

paper_content:

Desirable properties of the infinite histories of a finite-state Markov decision process are specified in terms of a finite number of events represented as /spl omega/-regular sets. An infinite history of the process produces a reward which depends on the properties it satisfies. The authors investigate the existence of optimal policies and provide algorithms for the construction of such policies.
---
paper_title: Pareto Curves for Probabilistic Model Checking

paper_content:

Multi-objective probabilistic model checking provides a way to verify several, possibly conflicting, quantitative properties of a stochastic system. It has useful applications in controller synthesis and compositional probabilistic verification. However, existing methods are based on linear programming, which limits the scale of systems that can be analysed and makes verification of time-bounded properties very difficult. We present a novel approach that addresses both of these shortcomings, based on the generation of successive approximations of the Pareto curve for a multi-objective model checking problem. We illustrate dramatic improvements in efficiency on a large set of benchmarks and show how the ability to visualise Pareto curves significantly enhances the quality of results obtained from current probabilistic verification tools.
---
paper_title: Multi-policy optimization in self-organizing systems

paper_content:

Self-organizing systems are often implemented as collections of collaborating agents. Such agents may need to optimize their own performance according to multiple policies as well as contribute to the optimization of overall system performance towards a potentially different set of policies. These policies can be heterogeneous, i.e., be implemented on different sets of agents, be active at different times and have different levels of priority, leading to the heterogeneity of the agents of which the system is composed. Numerous biologically-inspired techniques as well as techniques from artificial intelligence have been used to implement such self-organizing systems. In this paper we review the most commonly used techniques for multi-policy optimization in such systems, specifically, those based on ant colony optimization, evolutionary algorithms, particle swarm optimization and reinforcement learning (RL). We analyze the characteristics and existing applications of the reviewed algorithms, assessing their suitability for particular types of optimization problems, based on the environment and policy characteristics. We focus on RL, as it is considered particularly suitable for large-scale self-organizing systems due to its ability to take into account the long-term consequences of the actions executed. Therefore, RL enables the system to learn not only the immediate payoffs of its actions, but also the best actions for the long-term performance of the system. Existing RL implementations mostly focus on optimization towards a single system policy, while most multi-policy RL-based optimization techniques have so far been implemented only on a single agent. We argue that, in order to be more widely utilized as a technique for self-optimization, RL needs to address both multiple policies and multiple agents simultaneously, and analyze the challenges associated with extending existing or developing new RL optimization techniques.
---
paper_title: Collective Multi-Objective Planning

paper_content:

Multi-Objective Multi-Agent Planning addresses the problem of resolving conflicts between individual agent interests and the group interests. In this paper, we address this problem using a Vector-Valued Decentralized Markov Decision Process (2V-DEC-MDP). The formal framework of a Vector-Valued MDP considered uses the value function which returns a vector representing the individual and the group interests. Indeed, local decisions of each agent are guided by the local reward of the agent, the opportunity gain to the group and the opportunity cost of its nuisance. An optimal policy in such contextes is not clear but in this approach we develop a regret-based technique to find a good tradeoff between the group and induvidual interests. To do that, the approach we present uses Egalitarian Social Welfare orderings that allow an agent to consider during its local optimization the satisfaction of all criteria and reducing their differences. The obtained result is an equilibrium of individual and group satisfactions where the local policies can lead to more global satisfying behaviors in some settings. This result is illustrated in an example and compared to alternate local policies.
---
paper_title: Distributed W-Learning: Multi-Policy Optimization in Self-Organizing Systems

paper_content:

Large-scale agent-based systems are required to self-optimize towards multiple, potentially conflicting, policies of varying spatial and temporal scope. As a result, not all agents may be implementing all policies at all times, resulting in agent heterogeneity. As agents share their operating environment, significant dependencies can arise between agents and therefore between policy implementations. To address self-optimization in the presence of agent heterogeneity, policy dependency and the lack of global knowledge that is inherent in large-scale decentralized environments, we propose Distributed W-Learning (DWL). DWL is a reinforcement learning (RL)-based algorithm for collaborative agent-based self-optimization towards multiple policies, which relies only on local interactions and learning. We have evaluated the DWL algorithm in a simulation of a self-organizing urban traffic control (UTC) system and show that using DWL can improve the performance of multiple policies deployed simultaneously, even over corresponding single-policy deployments. For example, in UTC, optimizing simultaneously for cars and public transport vehicles reduces the waiting times of cars to 78% of their waiting times in the best-performing single-policy deployment that optimizes for cars only, while also outperforming the widely-deployed round-robin and saturation balancing traffic controllers that we used as baselines.
---
paper_title: Evolutionary Algorithms for Solving Multi-Objective Problems

paper_content:

List of Figures. List of Tables. Preface. Foreword. 1. Basic Concepts. 2. Evolutionary Algorithm MOP Approaches. 3. MOEA Test Suites. 4. MOEA Testing and Analysis. 5. MOEA Theory and Issues. 3. MOEA Theoretical Issues. 6. Applications. 7. MOEA Parallelization. 8. Multi-Criteria Decision Making. 9. Special Topics. 10. Epilog. Appendix A: MOEA Classification and Technique Analysis. Appendix B: MOPs in the Literature. Appendix C: Ptrue & PFtrue for Selected Numeric MOPs. Appendix D: Ptrue & PFtrue for Side-Constrained MOPs. Appendix E: MOEA Software Availability. Appendix F: MOEA-Related Information. Index. References.
---
paper_title: A New Approach for the Solution of Multiple Objective Optimization Problems Based on Reinforcement Learning

paper_content:

Many problems can be characterized by several competing objectives. Multiple objective optimization problems have recently received considerable attention specially by the evolutionary algorithms community. Their proposals, however, require an adequate codification of the problem into strings, which is not always easy to do. This paper introduces a new algorithm, called MDQL, for multiple objective optimization problems which does not suffer from previous limitations. MDQL is based on a new distributed Q-learning algorithm, called DQL, which is also introduced in this paper. Furthermore, an extension for applying reinforcement learning to continuos functions is also given. Successful results of MDQL on a continuos non restricted problem whose Pareto front is convex and on a continuos non-convex problem with restrictions are described.
---
paper_title: MOAQ an Ant-Q algorithm for multiple objective optimization problems

paper_content:

This paper describes an Ant-Q algorithm for the solution of multiple objective optimization problems (MOAQ). The algorithm uses families to represent the objectives in the problem. The problem definition considers that each family finds solutions that depend on solutions found by the rest of the families, creating a negotiation mechanism and finding compromise solutions for all the objectives involved. The compromise solutions are domination evaluated in the Pareto sense, assigning rewards to the non-dominated solutions fitting all problem constraints, and punishments to the solutions violating any of them. MOAQ incrementally learns during the optimization process how to generate the compromise solutions. It is shown how MOAQ is used to design water distribution networks which are non-linear multiple objective optimization problems.
---
paper_title: A New Distributed Reinforcement Learning Algorithm for Multiple Objective Optimization Problems

paper_content:

This paper describes a new algorithm, called MDQL, for the solution of multiple objective optimization problems. MDQL is based on a new distributed Q-learning algorithm, called DQL, which is also introduced in this paper. In DQL a family of independent agents, exploring different options, finds a common policy in a common environment. Information about action goodness is transmitted using traces over state-action pairs. MDQL extends this idea to multiple objectives, assigning a family of agents for each objective involved. A non-dominant criterion is used to construct Pareto fronts and by delaying adjustments on the rewards MDQL achieves better distributions of solutions. Furthermore, an extension for applying reinforcement learning to continuous functions is also given. Successful results of MDQL on several test-bed problems suggested in the literature are described.
---
paper_title: Multi-objective optimization by reinforcement learning for power system dispatch and voltage stability

paper_content:

This paper presents a new method called Multi-objective Optimization by Reinforcement Learning (MORL), to solve the optimal power system dispatch and voltage stability problem. In MORL, the search is undertaken on individual dimension in a high-dimensional space via a path selected by an estimated path value which represents the potential of finding a better solution. MORL is compared with multi-objective evolutionary algorithm based on decomposition (MOEA/D) to solve the multi-objective optimal power flow problems in power systems. The simulation results have demonstrated that MORL is superior over MOEA/D, as MORL can find wider and more evenly distributed Pareto fronts, obtain more accurate Pareto optimal solutions, and require less computation time.
---
paper_title: APPLYING MACHINE LEARNING TO LOW-KNOWLEDGE CONTROL OF OPTIMIZATION ALGORITHMS

paper_content:

This paper addresses the question of allocating computational resources among a set of algorithms to achieve the best performance on scheduling problems. Our primary motivation in addressing this problem is to reduce the expertise needed to apply optimization technology. Therefore, we investigate algorithm control techniques that make decisions based only on observations of the improvement in solution quality achieved by each algorithm. We call our approach “low knowledge” since it does not rely on complex prediction models, either of the problem domain or of algorithm behavior. We show that a low-knowledge approach results in a system that achieves significantly better performance than all of the pure algorithms without requiring additional human expertise. Furthermore the low-knowledge approach achieves performance equivalent to a perfect high-knowledge classification approach.
---
paper_title: Linear fitted-q iteration with multiple reward functions

paper_content:

We present a general and detailed development of an algorithm for finite-horizon fitted-Q iteration with an arbitrary number of reward signals and linear value function approximation using an arbitrary number of state features. This includes a detailed treatment of the 3-reward function case using triangulation primitives from computational geometry and a method for identifying globally dominated actions. We also present an example of how our methods can be used to construct a realworld decision aid by considering symptom reduction, weight gain, and quality of life in sequential treatments for schizophrenia. Finally, we discuss future directions in which to take this work that will further enable our methods to make a positive impact on the field of evidence-based clinical decision support.
---
paper_title: Constructing Stochastic Mixture Policies for Episodic Multiobjective Reinforcement Learning Tasks

paper_content:

Multiobjective reinforcement learning algorithms extend reinforcement learning techniques to problems with multiple conflicting objectives. This paper discusses the advantages gained from applying stochastic policies to multiobjective tasks and examines a particular form of stochastic policy known as a mixture policy. Two methods are proposed for deriving mixture policies for episodic multiobjective tasks from deterministic base policies found via scalarised reinforcement learning. It is shown that these approaches are an efficient means of identifying solutions which offer a superior match to the user's preferences than can be achieved by methods based strictly on deterministic policies.
---
paper_title: A note on the structure of value spaces in vector-valued Markov decision processes

paper_content:

For a vector-valued Markov decision process with discounted reward criterion, we study the structure of its value spaces defined for all initial states. At first we discuss the relationship between the value spaces, i.e. we verify a linking property for optimality. We next show that if the values of deterministic stationary policies generate a face of the value space, any point of that face can be represented as the value of a randomization of these policies. We also examine whether the value of a randomization of deterministic stationary policies lies on the face generated by the values of these policies.
---
paper_title: Computing Optimal Stationary Policies for Multi-Objective Markov Decision Processes

paper_content:

This paper describes a novel algorithm called CON-MODP for computing Pareto optimal policies for deterministic multi-objective sequential decision problems. CON-MODP is a value iteration based multi-objective dynamic programming algorithm that only computes stationary policies. We observe that for guaranteeing convergence to the unique Pareto optimal set of deterministic stationary policies, the algorithm needs to perform a policy evaluation step on particular policies that are inconsistent in a single state that is being expanded. We prove that the algorithm converges to the Pareto optimal set of value functions and policies for deterministic infinite horizon discounted multi-objective Markov decision processes. Experiments show that CON-MODP is much faster than previous multi-objective value iteration algorithms.
---
paper_title: Many-Objective Optimization : An Engineering Design Perspective

paper_content:

Evolutionary multicriteria optimization has traditionally concentrated on problems comprising 2 or 3 objectives. While engineering design problems can often be conveniently formulated as multiobjective optimization problems, these often comprise a relatively large number of objectives. Such problems pose new challenges for algorithm design, visualisation and implementation. Each of these three topics is addressed. Progressive articulation of design preferences is demonstrated to assist in reducing the region of interest for the search and, thereby, simplified the problem. Parallel coordinates have proved a useful tool for visualising many objectives in a two-dimensional graph and the computational grid and wireless Personal Digital Assistants offer technological solutions to implementation difficulties arising in complex system design.
---
paper_title: Empirical evaluation methods for multiobjective reinforcement learning algorithms

paper_content:

While a number of algorithms for multiobjective reinforcement learning have been proposed, and a small number of applications developed, there has been very little rigorous empirical evaluation of the performance and limitations of these algorithms. This paper proposes standard methods for such empirical evaluation, to act as a foundation for future comparative studies. Two classes of multiobjective reinforcement learning algorithms are identified, and appropriate evaluation metrics and methodologies are proposed for each class. A suite of benchmark problems with known Pareto fronts is described, and future extensions and implementations of this benchmark suite are discussed. The utility of the proposed evaluation methods are demonstrated via an empirical comparison of two example learning algorithms.
---

Title: A Survey of Multi-Objective Sequential Decision-Making

Section 1: Introduction
Description 1: Write an introductory section that provides an overview of sequential decision problems, Markov decision processes (MDPs), and the significance of multi-objective decision-making in various applications. Briefly outline the structure of the survey.

Section 2: Background
Description 2: Describe the foundational concepts of MDPs and MOMDPs, covering definitions, key properties, and the state-action-reward dynamic.

Section 3: Motivating Scenarios
Description 3: Discuss why explicitly modeling problems as multi-objective is beneficial by outlining scenarios where multi-objective decision-making is crucial—specifically unknown weights, decision support, and known weights scenarios.

Section 4: Problem Taxonomy
Description 4: Introduce a taxonomy to categorize multi-objective problems based on assumptions about scalarization functions, policies, and the nature of optimal solutions.

Section 5: Planning in MOMDPs
Description 5: Survey key methods for planning in MOMDPs, organized according to the taxonomy. Discuss approaches for both single-policy and multiple-policy planning under different scalarization functions.

Section 6: Learning in MOMDPs
Description 6: Review multi-objective reinforcement learning (MORL) methods, both model-based and model-free, organized by whether they focus on single-policy or multiple-policy learning and by scalarization functions.

Section 7: MOMDP Applications
Description 7: Survey specific applications of MOMDP methods in various fields, such as environmental management, energy, communications, industry, robotics, and traffic control. Also, discuss broader application classes like probabilistic planning and multi-agent systems.

Section 8: Future Work
Description 8: Enumerate potential areas for future research in multi-objective planning and learning, including model-based methods, learning with monotonically increasing scalarization functions, and many-objective sequential decision-making.

Section 9: Conclusions
Description 9: Summarize the survey, emphasizing the importance of multi-objective methods, the utility-based approach, and the relevance of the explored research areas. Highlight key observations and future research directions.