Stochastic dynamic programming
Originally introduced by Richard E. Bellman in , stochastic dynamic programming is a technique for modelling and solving problems of decision making under uncertainty. Closely related to stochastic programming and dynamic programming, stochastic dynamic programming represents the problem under scrutiny in the form of a Bellman equation. The aim is to compute a policy prescribing how to act optimally in the face of uncertainty. A motivating example: Gambling game. A gambler has $2, she is allowed to play a game of chance 4 times and her goal is to maximize her probability of ending up with a  least $6. If the gambler bets $formula_1 on a play of the game, then with probability 0.4 she wins the game, recoup the initial bet, and she increases her capital position by $formula_1; with probability 0.6, she loses the bet amount $formula_1; all plays are pairwise independent. On any play of the game, the gambler may not bet more money than she has available at the beginning of that play. Stochastic dynamic programming can be employed to model this problem and determine a betting strategy that, for instance, maximizes the gambler's probability of attaining a  wealth of at least $6 by the end of the betting horizon. Note that if there is no limit to the number of games that can be played, the problem becomes a variant of the well known St. Petersburg paradox. Formal background. Consider a discrete system defined on formula_4 stages in which each stage formula_5 is characterized by Let formula_20 represent the optimal cost/reward obtained by following an "optimal policy" over stages formula_21. Without loss of generality in what follow we will consider a reward maximisation setting. In deterministic dynamic programming one usually deals with functional equations taking  the following structure where formula_19 and the boundary condition of the system is The aim is to determine the set of optimal actions that maximise formula_25. Given the current state formula_13 and the current action formula_17, we "know with certainty" the reward secured during the current stage and – thanks to the state transition function formula_28 – the future state towards which the system transitions. In practice, however, even if we know the state of the system at the beginning of the current stage as well as the decision taken, the state of the system at the beginning of the next stage  and the current period reward are often random variables that can be observed only at the end of the current stage. Stochastic dynamic programming deals with problems in which the current period reward and/or the next period state are random, i.e. with multi-stage stochastic systems. The decision maker's goal is to maximise expected (discounted) reward over a given planning horizon. In their most general form, stochastic dynamic programs deal with functional equations taking the following structure where Markov decision process represent a special class of stochastic dynamic programs in which the underlying stochastic process is a stationary process  that features the Markov property. Gambling game as a stochastic dynamic program. Gambling game can be formulated as a Stochastic Dynamic Program as follows: there are formula_44 games (i.e. stages) in the planning horizon Let formula_56 be the probability that, by the end of game 4, the gambler has at least $6, given that she has $formula_45 at the beginning of game formula_8. To derive the functional equation, define formula_62 as a bet that attains formula_56, then at the beginning of game formula_64 For formula_74 the functional equation is formula_75, where formula_62 ranges in formula_77; the aim is  to find formula_78. Given the functional equation, an optimal betting policy can be obtained via forward recursion or backward recursion algorithms, as outlined below. Solution methods. Stochastic dynamic programs can be solved to optimality by using backward recursion or forward recursion algorithms. Memoization is typically employed to enhance performance. However, like deterministic dynamic programming also its stochastic variant suffers from the curse of dimensionality. For this reason approximate solution methods are typically employed in practical applications. Backward recursion. Given a bounded state space, "backward recursion" begins by tabulating formula_79 for every possible state formula_80 belonging to the final stage formula_4 . Once these values are tabulated, together with the associated optimal state-dependent actions formula_82, it is possible to move to stage formula_83 and tabulate formula_84 for all possible states belonging to the stage formula_83. The process continues by considering in a "backward" fashion all remaining stages up to the first one. Once this tabulation process is complete, formula_86 – the value of an optimal policy given initial state formula_45 – as well as the associated optimal action formula_88 can be easily retrieved from the table. Since the computation proceeds in a backward fashion, it is clear that backward recursion may lead to  computation of a large number of states that are not necessary for the computation of formula_86. Forward recursion. Given the initial state formula_45 of the system at the beginning of period 1, "forward recursion" computes formula_86 by progressively expanding the functional equation ("forward pass"). This involves recursive calls for all formula_92 that are necessary for computing a given formula_93. The value of an optimal policy and its structure are then retrieved via a ("backward pass") in which these suspended recursive calls are resolved. A key difference from backward recursion is the fact that formula_94 is computed only for states that  are relevant for the computation of formula_86. Memoization is employed to avoid recomputation of states that have been already considered. Example: Gambling game. We shall illustrate forward recursion in the context of the Gambling game instance previously discussed. We begin the "forward pass" by considering formula_96 At this point we have not computed yet formula_97, which are needed to compute formula_78; we proceed and compute these items. Note that formula_99, therefore one can leverage memoization and perform the necessary computations only once. formula_101 formula_102 formula_103 formula_104 formula_105 We have now computed formula_106 for all formula_80 that are needed to compute  formula_78. However, this has led to additional suspended recursions involving formula_109. We proceed and compute these values. formula_111 formula_112 formula_113 formula_114 formula_115 formula_116 Since stage 4 is the last stage in our system, formula_117 represent boundary conditions that are easily computed as follows. formula_118 At this point it is possible to proceed and recover the optimal policy and its value via a "backward pass" involving, at first, stage 3 formula_120 formula_121 formula_122 formula_123 formula_124 formula_125 and, then, stage 2. formula_127 formula_128 formula_129 formula_130 formula_131 We finally recover the value formula_132 of an optimal policy formula_133 This is the optimal policy  that has been previously illustrated. Note that there are multiple optimal policies leading to the same optimal value formula_134; for instance, in the first game one may either bet $1 or $2. Python implementation. The one that follows is a complete Python implementation of this example. from typing import List, Tuple import memoize as mem import functools class memoize: class State: class GamblersRuin: gr, initial_wealth = GamblersRuin(**instance), 2 print("f_1("+str(initial_wealth)+"): " + str(gr.f(initial_wealth))) t, initial_wealth = 1, 1 print("b_"+str(t+1)+"("+str(initial_wealth)+"): " + str(gr.q(t, initial_wealth))) Java implementation. GamblersRuin.java is a standalone Java 8 implementation of the above example. Approximate dynamic programming. An introduction  to Reinforcement learning|approximate dynamic programming is provided by . References. Category:Dynamic programming Category:Optimal control Category:Optimization algorithms and methods Category:Stochastic optimization