To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
This book offers a comprehensive introduction to Markov decision process and reinforcement learning fundamentals using common mathematical notation and language. Its goal is to provide a solid foundation that enables readers to engage meaningfully with these rapidly evolving fields. Topics covered include finite and infinite horizon models, partially observable models, value function approximation, simulation-based methods, Monte Carlo methods, and Q-learning. Rigorous mathematical concepts and algorithmic developments are supported by numerous worked examples. As an up-to-date successor to Martin L. Puterman's influential 1994 textbook, this volume assumes familiarity with probability, mathematical notation, and proof techniques. It is ideally suited for students, researchers, and professionals in operations research, computer science, engineering, and economics.
In this paper, we provide a general framework for dynamic macroeconomic models that incorporate history and context dependencies. Such features arise in several strands in the economic literature including habit formation based on consumption or other economic variables, decision theory, health economics, sports economics, environmental economics, and law and economics. Our approach introduces a memory function to account for how history is formed. This allows us to encompass a wide range of standard economic models while adapting to emerging modelings such as circular economy models. We establish the corresponding optimization results and develop dynamic programming tools so that the standard machinery can still be applied directly despite the specific difficulties induced by history-dependence.
Shie Mannor, Technion - Israel Institute of Technology, Haifa,Yishay Mansour, Tel-Aviv University,Aviv Tamar, Technion - Israel Institute of Technology, Haifa
This chapter introduces reinforcement learning (RL) as the discipline of learning and acting in environments where sequential decisions are made. It traces the origins of RL across multiple disciplines including optimal control, operations research, neuroscience and psychology. The chapter motivates the field through landmark successes in game playing (checkers, backgammon, go, chess), Atari video games, robotics and language model fine-tuning. The primary mathematical model – the Markov Decision Process (MDP) – is introduced as the framework for handling uncertainty in dynamics, actions and knowledge. The chapter outlines the book’s organization into two main themes: planning (optimal decision making with known models) and learning (decision making with unknown models), and presents the key tradeoff between exploitation and exploration inherent to RL problems.
Shie Mannor, Technion - Israel Institute of Technology, Haifa,Yishay Mansour, Tel-Aviv University,Aviv Tamar, Technion - Israel Institute of Technology, Haifa
This appendix provides a rigorous treatment of dynamic programming (DP) as a computational and optimization paradigm. The fundamental principle of optimality is formalized. Classical DP problem structures are covered. Backward recursion algorithms are developed systematically. Computational complexity analysis demonstrates how DP achieves polynomial time for problems that appear exponential via naive enumeration.
Shie Mannor, Technion - Israel Institute of Technology, Haifa,Yishay Mansour, Tel-Aviv University,Aviv Tamar, Technion - Israel Institute of Technology, Haifa
This chapter introduces optimal planning in deterministic sequential decision problems. The deterministic dynamic system framework is presented with state transitions, encompassing both finite discrete models and continuous systems. Two fundamental problem settings are covered: finite-horizon decision problems solved via backward dynamic programming, and average cost criteria. Classic graph-theoretic algorithms are developed including Bellman–Ford, Dijkstra’s algorithm and A* search. The chapter extends to continuous optimal control, presenting the linear quadratic regulator (LQR) and iterative LQR.
Lifetime pension pools—also known as group self-annuitization plans, pooled annuity funds, and variable payment life annuities in the literature—offer retirees lifelong income by collectively managing mortality risk and adjusting benefits based on the investment performance and the mortality experience within the pool. The benefit structure hinges on two key design parameters: the investment policy and the hurdle rate. However, past research offers limited guidance on optimal asset allocation in such settings, often relying on overly simplistic strategies. Furthermore, the choice of hurdle rate has received virtually no attention in the literature. This study addresses this gap by jointly analyzing optimal hurdle rates and investment strategies using a dynamic programming approach that allows for varying degrees of risk aversion via a hyperbolic absolute risk aversion utility function. Our findings reveal that, as risk aversion increases, the model favours more conservative portfolios and lower hurdle rates; conversely, lower risk aversion supports riskier allocations and higher hurdle rates. The threshold parameter—which reflects the minimum acceptable level of consumption—plays a critical role in shaping the hurdle rate behaviour.
Designing efficient and rigorous numerical methods for sequential decision-making under uncertainty is a difficult problem that arises in many applications frameworks. In this paper we focus on the numerical solution of a subclass of impulse control problems for the piecewise deterministic Markov process (PDMP) when the jump times are hidden. We first state the problem as a partially observed Markov decision process (POMDP) on a continuous state space and with controlled transition kernels corresponding to some specific skeleton chains of the PDMP. We then proceed to build a numerically tractable approximation of the POMDP by tailor-made discretizations of the state spaces. The main difficulty in evaluating the discretization error comes from the possible random jumps of the PDMP between consecutive epochs of the POMDP and requires special care. Finally, we discuss the practical construction of discretization grids and illustrate our method on simulations.
In this chapter, the reader learns about the main ideas developed by analytics scientists in problem solving that requires decision-making over time. The reader realizes that various decision-making problems, including those made in everyday life such as which parking spot to take or which job offer to accept, can be addressed using these main ideas. The chapter also illustrates how the same ideas have been used to improve the world around us by citing various examples, including assisting policymakers to gain insights into the impact of different social mobility policies or to find better lockdown policies during a pandemic such as COVID-19.
This paper examines an insurer’s optimal asset allocation and reinsurance policies. The financial market framework includes one risk-free and one risky asset. The insurer has two business lines, where the ordinary claim process is modeled by a compound Poisson process and catastrophic claims follow a compound dynamic contagion process. The dynamic contagion process, which is a generalization of the externally exciting Cox process with shot-noise intensity and the self-exciting Hawkes process, is enhanced by accommodating the dependency structure between the magnitude of contribution to intensity after initial events for catastrophic insurance products and its claim/loss size. We also consider the dependency structure between the positive effect on the intensity and the negative crashes on the risky financial asset when initial events occur. Our objective is to maximize the insurer’s expected utility of terminal surplus. We construct the extended Hamilton–Jacobi–Bellman (HJB) equation using dynamic programming principles to derive an explicit optimal reinsurance policy for ordinary claims. We further develop an iterative scheme for solving the value function and the optimal asset allocation policy and the reinsurance policy for catastrophic claims numerically, providing a rigorous convergence proof. Finally, we present numerical examples to demonstrate the impact of key parameters.
Risk was incorporated into monetary aggregation over thirty-five years ago, using a stochastic version of the workhorse money-in-the-utility-function model. Nevertheless, the mathematical foundations of this stochastic model remain shaky. To firm the foundations, this paper employs richer probability concepts than Borel-measurability, enabling me to prove the existence of a well-behaved solution and to derive stochastic Euler equations. This measurability approach is less common in economics, possibly because the derivation of stochastic Euler equations is new. Importantly, the problem’s economics are not restricted by the approach. The results provide firm footing for the growing monetary aggregation under risk literature, which integrates monetary and finance theory. As crypto-currencies and stable coins garner attention, solidifying the foundations of risky money becomes more critical. The method also supports deriving stochastic Euler equations for any dynamic economics problem that features contemporaneous uncertainty about prices, including asset pricing models like capital asset pricing models and stochastic consumer choice models.
Dynamic programming methods for matrix permutation problems in combinatorial data analysis can produce globally-optimal solutions for matrices up to size 30×30, but are computationally infeasible for larger matrices because of enormous computer memory requirements. Branch-and-bound methods also guarantee globally-optimal solutions, but computation time considerations generally limit their applicability to matrix sizes no greater than 35×35. Accordingly, a variety of heuristic methods have been proposed for larger matrices, including iterative quadratic assignment, tabu search, simulated annealing, and variable neighborhood search. Although these heuristics can produce exceptional results, they are prone to converge to local optima where the permutation is difficult to dislodge via traditional neighborhood moves (e.g., pairwise interchanges, object-block relocations, object-block reversals, etc.). We show that a heuristic implementation of dynamic programming yields an efficient procedure for escaping local optima. Specifically, we propose applying dynamic programming to reasonably-sized subsequences of consecutive objects in the locally-optimal permutation, identified by simulated annealing, to further improve the value of the objective function. Experimental results are provided for three classic matrix permutation problems in the combinatorial data analysis literature: (a) maximizing a dominance index for an asymmetric proximity matrix; (b) least-squares unidimensional scaling of a symmetric dissimilarity matrix; and (c) approximating an anti-Robinson structure for a symmetric dissimilarity matrix.
Common outputs of software programs for network estimation include association matrices containing the edge weights between pairs of symptoms and a plot of the symptom network. Although such outputs are useful, it is sometimes difficult to ascertain structural relationships among symptoms from these types of output alone. We propose that matrix permutation provides a simple, yet effective, approach for clarifying the order relationships among the symptoms based on the edge weights of the network. For directed symptom networks, we use a permutation criterion that has classic applications in electrical circuit theory and economics. This criterion can be used to place symptoms that strongly predict other symptoms at the beginning of the ordering, and symptoms that are strongly predicted by other symptoms at the end. For undirected symptom networks, we recommend a permutation criterion that is based on location theory in the field of operations research. When using this criterion, symptoms with many strong ties tend to be placed centrally in the ordering, whereas weakly-tied symptoms are placed at the ends. The permutation optimization problems are solved using dynamic programming. We also make use of branch-search algorithms for extracting maximum cardinality subsets of symptoms that have perfect structure with respect to a selected criterion. Software for implementing the dynamic programming algorithms is available in MATLAB and R. Two networks from the literature are used to demonstrate the matrix permutation algorithms.
There are two well-known methods for obtaining a guaranteed globally optimal solution to the problem of least-squares unidimensional scaling of a symmetric dissimilarity matrix: (a) dynamic programming, and (b) branch-and-bound. Dynamic programming is generally more efficient than branch-and-bound, but the former is limited to matrices with approximately 26 or fewer objects because of computer memory limitations. We present some new branch-and-bound procedures that improve computational efficiency, and enable guaranteed globally optimal solutions to be obtained for matrices with up to 35 objects. Experimental tests were conducted to compare the relative performances of the new procedures, a previously published branch-and-bound algorithm, and a dynamic programming solution strategy. These experiments, which included both synthetic and empirical dissimilarity matrices, yielded the following findings: (a) the new branch-and-bound procedures were often drastically more efficient than the previously published branch-and-bound algorithm, (b) when computationally feasible, the dynamic programming approach was more efficient than each of the branch-and-bound procedures, and (c) the new branch-and-bound procedures require minimal computer memory and can provide optimal solutions for matrices that are too large for dynamic programming implementation.
This paper proposes an order-constrained K-means cluster analysis strategy, and implements that strategy through an auxiliary quadratic assignment optimization heuristic that identifies an initial object order. A subsequent dynamic programming recursion is applied to optimally subdivide the object set subject to the order constraint. We show that although the usual K-means sum-of-squared-error criterion is not guaranteed to be minimal, a true underlying cluster structure may be more accurately recovered. Also, substantive interpretability seems generally improved when constrained solutions are considered. We illustrate the procedure with several data sets from the literature.
The book starts out with a motivating chapter to answer the question: Why is it worthwhile to develop system theory? To do so, we jump fearlessly in the very center of our methods, using a simple and straight example in optimization: optimal tracking. Although optimization is not our leading subject– which is system theory– it provides for one of the main application areas, namely the optimization of the performance of a dynamical system in a time-variant environment (for example, driving a car or sending a rocket to the moon). The chapter presents a recursive matrix algebra approach to the optimization problem, known as dynamic programming. Optimal tracking is based on a powerful principle called “dynamic programming,” which lies at the very basis of what ”dynamical” means.
Deals with reservoir operation, including rule curves, methods of mathematical programming, optimization of reservoir operations, simulation models, reservoir operation modeling with HEC-ResSim, mass curves, and reservoir siltation.
This chapter introduces the medium-term hydrothermal planning problem. Two-stage stochastic linear programs are introduced first, and subsequently generalized to multi-stage stochastic linear programs. Various representations of multi-stage stochastic linear programs are presented, including representations on scenario trees, representations on lattices (for Markov processes), as well as representations with stagewise independent uncertainty. These models are applied to a running example of hydrothermal planning, which is used as the basis for introducing the notion of dynamic programming value functions. The value of water is defined, and demonstrated on a hydrothermal planning problem. The chapter then proceeds to focus on the performance of stochastic programs. The wait-and-see and here-and-now value are introduced for two-stage stochastic programs. These are used to define the expected value of perfect information. The expected value solution is also defined, and used in order to introduce the value of the stochastic solution. Sampling is discussed briefly in the context of sample average approximation and importance sampling.
The rapid development of new technologies such as electrification, autonomy, and other contextual factors pose significant challenges to development teams in balancing competing aspects while developing value-robust solutions. One approach for achieving value robustness is designing for changeability. This paper presents a tradespace exploration from a Systems-of-Systems perspective to facilitate changeability assessment during early design stages. The approach is further demonstrated on a fleet of haulers operating in a mining site.
This study examines the economic performance of rainfed cropping systems endemic to the Southern Great Plains under weed competition. Cropping systems include tilled and no-till wheat-fallow, wheat-soybean, and wheat-sorghum rotations. Net returns from systems are compared under different levels of weed pressure. Producers operating over longer planning horizons would choose to double-crop regardless of the tillage method used and weed pressure level. Producers operating under shorter planning horizons would implement wheat-fallow systems when weed pressure is high and double crop when weed pressure is low.
We study the time-consistent investment and contribution policies in a defined benefit stochastic pension fund where the manager discounts the instantaneous utility over a finite planning horizon and the final function at constant but different instantaneous rates of time preference. This difference, which can be motivated for some uncertainties affecting payoffs at the end of the planning horizon, will induce a variable bias between the relative valuation of the final function and the previous payoffs and will lead the manager to show time-inconsistent preferences. Both the benefits and the contribution rate are proportional to the total wage of the workers that we suppose is stochastic. The aim is to maximize a CRRA utility function of the net benefit relative to salary in a bounded horizon and to maximize a CRRA final utility of the fund level relative to the salary. The problem is solved by means of dynamic programming techniques, and main results are illustrated numerically.