# Markov Decision Process (MDP)

## Infinite Horizon Dynamic Programming

### Overview

In dynamic programming an agent finds a policy (an action given their current state) that maximizes their present discounted award given

\begin{align*} \beta &\quad\text{discount rate}\\ R_{ik} &\quad\text{reward from transitioning to $i$ using control $k$} \\ P_{ijk} &\quad\text{probability of transitioning from state $i$ to $j$ using control $k$} \\ V_{i} &\quad\text{present discounted value of being in state $i$} \end{align*}

### Value Iteration

Value iteration is a simple way to estimate discrete infinite horizon dynamic programs. In value iteration we set our present discounted value of being in a particular state to arbitrary values and iterate on the Bellman equation until convergence

\begin{align*} &\text{do} \\ &\quad i += 1\\ &\quad V_{i+1} = \max (R + \beta PV_i) \\ &\text{until}\quad || V_{i+1} - V_i || < \epsilon \end{align*}

### Policy Iteration

In policy iteration we start with an initial policy and then find the present discounted value $V$ of the policy. Then the policy that greedily maximizes the payoff for next period is taken.

### Examples

#### Ex. 1

Following an example given in Foundations of Machine Learning suppose we have a infinite horizon dynamic program identical to the one given in the graph shown below:

Notice the edges in the graph correspond have probabilities and rewards. For instance, if you choose to play $a$ in state 1 there is a 75% chance that you will end up in state 1 (with a reward of 2) and 25% percent chance that you will end up in state 2 (also with a reward of 2).

In Julia this problem can be represented using arrays



In [4]:

using MDP

I = [1,1,2,3,4]
J = [1,2,2,2,1]
R = sparse(I, J, Float64[2,2,2,2,3])
P = sparse(I,J,[.75,.25,1.00,1.00,1.00])
SA = [
((1,),('a',)),
((1,),('b',)),
((2,),('c',)),
((2,),('d',))
]
R = Float64[2,2,2,3]
indvec = [2,4]
# indvec describes what choices correspond to each state
# the "2" says that the first to second elements of R correspond to playing "a" or "b" in state 1
# the "4" says that the third to fourth elements of R correspond to playing "c" or "d" in state 2
V0 = Float64[-1; 1]
β=0.5

mdp = SimpleMDP(R,P,SA,indvec,β,IClock())

valueiteration(mdp; Vstart=V0)




Out[4]:

MDPSolution([4.66614,5.33264],[2,4])



The output of value iteration shows that the optimal policy is to play $b$ in state 1 and $d$ in state 2. The policy makes intuitive sense given the above graph because the agent wants to maximize the chance of getting the high reward choice $d$.



In [5]:

policyiteration(mdp)




V
[4.666666666666666,5.333333333333333]

Out[5]:

MDPSolution([4.66667,5.33333],[2,4])



#### Ex. 2

Consider a deterministic infinite horizon optimal growth problem used by Judd in Numerical Methods for Economists

In the problem the agent maximizes their present discounted utility by changing their consumption. A higher rate of consumption lowers means that less capital is being produced which in turn lowers future consumption.

$$V(k) = \max_c u(c) + \beta V(k^+(k,c))$$

where $u(c) = \frac{c^{1+\gamma}}{1+\gamma}$, $F(k) = k + f(k) = k + \frac{(1-\beta)}{\alpha\beta}k^\alpha$ and $k^+ = F(k) - c$

The problem with this formulation is that it is difficult to discretize $c$ in a way that is compatible with the levels of $k$. In order to circumvent this problem we make control variable the state variable of the next period. This gives

$$V(k) = \max_{k^+} u(F(k) - k^+) + \beta V(k^+)$$

Assuming $\gamma = -2$, $\alpha = 0.25$ and $\beta = 0.96$ the steady state level of capital is one. Since all initial capital values but zero converge to the steady state if a region around the steady state is discretized then the policy will not have an optimal policy go outside the discretized region. In the code below I chose to discretize the capital stock levels into 401 equally sized bins between 0.8 and 1.2.



In [15]:

using MDP
# reward function
util(c; g=-2) = c^(g+1)/(g+1)

# Law of Motion for the capital stock
transition(k; alpha=0.25, beta=0.96) = k + ((1-beta)/(alpha*beta))*k^alpha

# function to determine what actions are feasible in a given state
reachable(c) = c >= 0

ks = 0.8:0.001:1.2 # capital levels at which the
n = length(ks)

# determine the feasible state action pairs
R = Float64[] # rewards for all feasible state action pairs
SA = ((Float64,),(Float64,))[] # enumeration of all feasible state action pairs
indvec = Int64[]

k = 1
for i=1:n
if i>1 push!(indvec, k-1) end
for j=1:n
c = transition(ks[i])-ks[j]
if reachable(c)
push!(SA, ((ks[i],),(ks[j],)))
push!(R, util(c))
k+=1
end
end
end
push!(indvec, k-1)

# build the transition matrix
P = sparse(Int64[],Int64[],Float64[],k-1,n)
P[1:indvec[1], 1:indvec[1]] = eye(indvec[1])
for i=2:length(indvec)
lb = indvec[i-1]+1
ub = indvec[i]
#@printf "lb = %0.0f\n" lb
#@printf "ub = %0.0f\n" ub
P[lb:ub,1:(ub-lb+1)] = eye(ub-lb+1)
end

β = 0.96
dp = SimpleMDP(R,P,SA,indvec,β,IClock())




Out[15]:

SimpleMDP{IClock}([-6.34423,-6.38473,-6.42576,-6.46732,-6.50942,-6.55207,-6.59528,-6.63907,-6.68344,-6.72841  …  -5.4514,-5.48128,-5.51149,-5.54203,-5.57292,-5.60415,-5.63573,-5.66768,-5.69998,-5.73266],132481x401 sparse matrix with 132481 Float64 entries:
[1     ,      1]  =  1.0
[159   ,      1]  =  1.0
[318   ,      1]  =  1.0
[478   ,      1]  =  1.0
[639   ,      1]  =  1.0
[801   ,      1]  =  1.0
[964   ,      1]  =  1.0
[1128  ,      1]  =  1.0
[1293  ,      1]  =  1.0
[1460  ,      1]  =  1.0
⋮
[128471,    401]  =  1.0
[128872,    401]  =  1.0
[129273,    401]  =  1.0
[129674,    401]  =  1.0
[130075,    401]  =  1.0
[130476,    401]  =  1.0
[130877,    401]  =  1.0
[131278,    401]  =  1.0
[131679,    401]  =  1.0
[132080,    401]  =  1.0
[132481,    401]  =  1.0,[((0.8,),(0.8,)),((0.8,),(0.801,)),((0.8,),(0.802,)),((0.8,),(0.803,)),((0.8,),(0.804,)),((0.8,),(0.805,)),((0.8,),(0.806,)),((0.8,),(0.807,)),((0.8,),(0.808,)),((0.8,),(0.809,))  …  ((1.2,),(1.191,)),((1.2,),(1.192,)),((1.2,),(1.193,)),((1.2,),(1.194,)),((1.2,),(1.195,)),((1.2,),(1.196,)),((1.2,),(1.197,)),((1.2,),(1.198,)),((1.2,),(1.199,)),((1.2,),(1.2,))],[158,317,477,638,800,963,1127,1292,1459,1627  …  128872,129273,129674,130075,130476,130877,131278,131679,132080,132481],0.96,IClock())




In [16]:

v = policyiteration(dp; eps=1e-2)




Out[16]:

MDPSolution([-158.288,-158.242,-158.196,-158.15,-158.105,-158.059,-158.013,-157.968,-157.922,-157.877  …  -143.404,-143.372,-143.34,-143.308,-143.276,-143.245,-143.213,-143.181,-143.15,-143.118],[7,166,326,487,649,812,976,1141,1307,1475  …  128857,129259,129661,130063,130465,130867,131269,131671,132073,132474],[158,317,477,638,800,963,1127,1292,1459,1627  …  128872,129273,129674,130075,130476,130877,131278,131679,132080,132481],[((0.8,),(0.8,)),((0.8,),(0.801,)),((0.8,),(0.802,)),((0.8,),(0.803,)),((0.8,),(0.804,)),((0.8,),(0.805,)),((0.8,),(0.806,)),((0.8,),(0.807,)),((0.8,),(0.808,)),((0.8,),(0.809,))  …  ((1.2,),(1.191,)),((1.2,),(1.192,)),((1.2,),(1.193,)),((1.2,),(1.194,)),((1.2,),(1.195,)),((1.2,),(1.196,)),((1.2,),(1.197,)),((1.2,),(1.198,)),((1.2,),(1.199,)),((1.2,),(1.2,))])




In [34]:

function computepath(startindx, mdpsol; len=10)
policy = mdpsol.policy
action = copy(policy)
indvec = mdpsol.indvec

for i=2:length(policy)
action[i] -= indvec[i-1]
end
SA = mdpsol.SA

path = Array(Float64,len+1)
indx = startindx
path[1] = SA[policy[indx]][2][1]
for i=1:len
indx = action[indx]
path[i+1] = SA[policy[indx]][2][1]
end
path
end




Out[34]:

101-element Array{Float64,1}:
1.193
1.187
1.181
1.175
1.169
1.163
1.158
1.153
1.148
1.143
1.138
1.133
1.129
⋮
1.008
1.008
1.008
1.008
1.008
1.008
1.008
1.008
1.008
1.008
1.008
1.008




In [42]:

using DataFrames
df = DataFrame(low=computepath(1,v;len=99), high=computepath(401,v; len=99),time=1:100)




Out[42]:

lowhightime10.8061.193120.8121.187230.8181.181340.8241.175450.831.169560.8361.163670.8411.158780.8461.153890.8511.1489100.8561.14310110.8611.13811120.8661.13312130.871.12913140.8741.12514150.8781.12115160.8821.11716170.8861.11317180.891.10918190.8941.10519200.8971.10220210.91.09921220.9031.09622230.9061.09323240.9091.0924250.9121.08725260.9151.08426270.9181.08127280.9211.07828290.9241.07529300.9261.07330⋮⋮⋮⋮




In [46]:

plot(df, layer(x="time", y="low", Geom.line), layer(x="time", y="high", Geom.line),
Guide.xlabel("time (t)"), Guide.ylabel("Capital Stock (k)"))




Out[46]:

(function (module) {
function draw_with_data(data, parent_id) {
var g = d3.select(parent_id)
.append("svg")
.attr("width", "120mm")
.attr("height", "80mm")
.attr("viewBox", "0 0 120 80")
.attr("stroke-width", "0.5")
.attr("style", "stroke:black;fill:black");
g.append("defs");
var ctx = {
"scale": 1.0,
"tx": 0.0,
"ty": 0.0
};
(function (g) {
g.attr("stroke", "none")
.attr("fill", "#000000")
.attr("stroke-width", 0.3)
.attr("font-family", "Helvetic,Arial,sans")
.style("font-size", "3.88px");
(function (g) {
g.attr("class", "plotroot xscalable yscalable");
(function (g) {
g.attr("stroke", "none")
.attr("fill", "#4C404B")
.attr("font-family", "'PT Sans','Helvetica Neue','Helvetica',sans-serif")
.style("font-size", "3.18px")
.attr("class", "guide ylabels");
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", -47.11)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.6");
})
;
}(g.append("g")));
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 33.47)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.0");
})
;
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 114.05)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.4");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", -33.68)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.5");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 100.62)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.5");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", -6.82)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.3");
})
;
}(g.append("g")));
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 60.33)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.8");
})
;
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", -60.54)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.7");
})
;
}(g.append("g")));
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 46.9)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.9");
})
;
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 20.04)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.1");
})
;
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", -20.25)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.4");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 87.19)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.6");
})
;
}(g.append("g")));
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 6.61)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("1.2");
})
;
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 73.76)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.7");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 16.29)
.attr("y", 127.48)
.attr("text-anchor", "end")
.style("dominant-baseline", "central")
.call(function(text) {
text.text("0.3");
})
;
}(g.append("g")));
}(g.append("g")));
(function (g) {
g.attr("stroke", "none")
.attr("fill", "#362A35")
.attr("font-family", "'PT Sans','Helvetica Neue','Helvetica',sans-serif")
.style("font-size", "3.88px");
g.append("svg:text")
.attr("x", 7.94)
.attr("y", 33.47)
.attr("text-anchor", "middle")
.style("dominant-baseline", "central")
.attr("transform", "rotate(-90, 7.94, 33.47)")
.call(function(text) {
text.text("Capital Stock (k)");
})
;
}(g.append("g")));
(function (g) {
g.attr("stroke", "none")
.attr("fill", "#4C404B")
.attr("font-family", "'PT Sans','Helvetica Neue','Helvetica',sans-serif")
.style("font-size", "3.18px")
.attr("class", "guide xlabels");
g.append("svg:text")
.attr("x", 66.15)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("50");
})
;
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", -72.11)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("-100");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", -118.2)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("-150");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", -26.03)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("-50");
})
;
}(g.append("g")));
g.append("svg:text")
.attr("x", 112.23)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("100");
})
;
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 204.41)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("200");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 158.32)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("150");
})
;
}(g.append("g")));
(function (g) {
g.attr("visibility", "hidden");
g.append("svg:text")
.attr("x", 250.5)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("250");
})
;
}(g.append("g")));
g.append("svg:text")
.attr("x", 20.06)
.attr("y", 66.12)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("0");
})
;
}(g.append("g")));
(function (g) {
g.attr("stroke", "none")
.attr("fill", "#362A35")
.attr("font-family", "'PT Sans','Helvetica Neue','Helvetica',sans-serif")
.style("font-size", "3.88px");
g.append("svg:text")
.attr("x", 66.15)
.attr("y", 73)
.attr("text-anchor", "middle")
.call(function(text) {
text.text("time (t)");
})
;
}(g.append("g")));
(function (g) {
g.on("mouseover", guide_background_mouseover("#C6C6C9"))
.on("mouseout", guide_background_mouseout("#F0F0F3"))
.call(zoom_behavior(ctx))
;
(function (g) {
d3.select("defs")
.append("svg:clipPath")
.attr("id", parent_id + "_clippath0")
.append("svg:path")
.attr("d", " M17.29,5 L 115 5 115 61.94 17.29 61.94 z");g.attr("clip-path", "url(#" + parent_id + "_clippath0)");
(function (g) {
g.attr("class", "guide background")
.attr("stroke", "#F1F1F5")
.attr("fill", "#FAFAFA")
.attr("opacity", 1.00);
g.append("svg:path")
.attr("d", "M17.29,5 L 115 5 115 61.94 17.29 61.94 z");
}(g.append("g")));
(function (g) {
g.attr("stroke", "#F0F0F3")
.attr("stroke-width", 0.2)
.attr("class", "guide ygridlines xfixed");
g.append("svg:path")
.attr("d", "M17.29,33.47 L 115 33.47");
g.append("svg:path")
.attr("d", "M17.29,-33.68 L 115 -33.68");
g.append("svg:path")
.attr("d", "M17.29,-6.82 L 115 -6.82");
g.append("svg:path")
.attr("d", "M17.29,-60.54 L 115 -60.54");
g.append("svg:path")
.attr("d", "M17.29,20.04 L 115 20.04");
g.append("svg:path")
.attr("d", "M17.29,87.19 L 115 87.19");
g.append("svg:path")
.attr("d", "M17.29,73.76 L 115 73.76");
g.append("svg:path")
.attr("d", "M17.29,127.48 L 115 127.48");
g.append("svg:path")
.attr("d", "M17.29,6.61 L 115 6.61");
g.append("svg:path")
.attr("d", "M17.29,-20.25 L 115 -20.25");
g.append("svg:path")
.attr("d", "M17.29,46.9 L 115 46.9");
g.append("svg:path")
.attr("d", "M17.29,60.33 L 115 60.33");
g.append("svg:path")
.attr("d", "M17.29,100.62 L 115 100.62");
g.append("svg:path")
.attr("d", "M17.29,114.05 L 115 114.05");
g.append("svg:path")
.attr("d", "M17.29,-47.11 L 115 -47.11");
}(g.append("g")));
(function (g) {
g.attr("stroke", "#F0F0F3")
.attr("stroke-width", 0.2)
.attr("class", "guide xgridlines yfixed");
g.append("svg:path")
.attr("d", "M-72.11,5 L -72.11 61.94");
g.append("svg:path")
.attr("d", "M-26.03,5 L -26.03 61.94");
g.append("svg:path")
.attr("d", "M204.41,5 L 204.41 61.94");
g.append("svg:path")
.attr("d", "M250.5,5 L 250.5 61.94");
g.append("svg:path")
.attr("d", "M20.06,5 L 20.06 61.94");
g.append("svg:path")
.attr("d", "M158.32,5 L 158.32 61.94");
g.append("svg:path")
.attr("d", "M112.23,5 L 112.23 61.94");
g.append("svg:path")
.attr("d", "M-118.2,5 L -118.2 61.94");
g.append("svg:path")
.attr("d", "M66.15,5 L 66.15 61.94");
}(g.append("g")));
}(g.append("g")));
(function (g) {
d3.select("defs")
.append("svg:clipPath")
.attr("id", parent_id + "_clippath1")
.append("svg:path")
.attr("d", " M17.29,5 L 115 5 115 61.94 17.29 61.94 z");g.attr("clip-path", "url(#" + parent_id + "_clippath1)");
(function (g) {
g.attr("class", "plotpanel");
(function (g) {
g.attr("fill", "none")
.attr("stroke-width", 0.3);
(function (g) {
g.attr("stroke", "#00BFFF")
.attr("class", "geometry");
g.append("svg:path")
.attr("d", "M20.98,7.55 L 21.9 8.36 22.83 9.16 23.75 9.97 24.67 10.78 25.59 11.58 26.51 12.25 27.43 12.92 28.36 13.6 29.28 14.27 30.2 14.94 31.12 15.61 32.04 16.15 32.96 16.68 33.89 17.22 34.81 17.76 35.73 18.3 36.65 18.83 37.57 19.37 38.49 19.77 39.42 20.18 40.34 20.58 41.26 20.98 42.18 21.38 43.1 21.79 44.03 22.19 44.95 22.59 45.87 23 46.79 23.4 47.71 23.67 48.63 23.94 49.56 24.21 50.48 24.47 51.4 24.74 52.32 25.01 53.24 25.28 54.16 25.55 55.09 25.82 56.01 26.09 56.93 26.35 57.85 26.62 58.77 26.89 59.7 27.16 60.62 27.43 61.54 27.7 62.46 27.83 63.38 27.97 64.3 28.1 65.23 28.23 66.15 28.37 67.07 28.5 67.99 28.64 68.91 28.77 69.83 28.91 70.76 29.04 71.68 29.17 72.6 29.31 73.52 29.44 74.44 29.58 75.36 29.71 76.29 29.85 77.21 29.98 78.13 30.11 79.05 30.25 79.97 30.38 80.9 30.52 81.82 30.65 82.74 30.79 83.66 30.92 84.58 31.05 85.5 31.19 86.43 31.32 87.35 31.46 88.27 31.59 89.19 31.73 90.11 31.86 91.03 31.99 91.96 32.13 92.88 32.26 93.8 32.4 94.72 32.4 95.64 32.4 96.57 32.4 97.49 32.4 98.41 32.4 99.33 32.4 100.25 32.4 101.17 32.4 102.1 32.4 103.02 32.4 103.94 32.4 104.86 32.4 105.78 32.4 106.7 32.4 107.63 32.4 108.55 32.4 109.47 32.4 110.39 32.4 111.31 32.4 112.23 32.4");
}(g.append("g")));
}(g.append("g")));
(function (g) {
g.attr("fill", "none")
.attr("stroke-width", 0.3);
(function (g) {
g.attr("stroke", "#00BFFF")
.attr("class", "geometry");
g.append("svg:path")
.attr("d", "M20.98,59.53 L 21.9 58.72 22.83 57.92 23.75 57.11 24.67 56.3 25.59 55.5 26.51 54.83 27.43 54.15 28.36 53.48 29.28 52.81 30.2 52.14 31.12 51.47 32.04 50.93 32.96 50.39 33.89 49.86 34.81 49.32 35.73 48.78 36.65 48.25 37.57 47.71 38.49 47.31 39.42 46.9 40.34 46.5 41.26 46.1 42.18 45.69 43.1 45.29 44.03 44.89 44.95 44.49 45.87 44.08 46.79 43.68 47.71 43.41 48.63 43.14 49.56 42.87 50.48 42.6 51.4 42.34 52.32 42.07 53.24 41.8 54.16 41.53 55.09 41.26 56.01 40.99 56.93 40.72 57.85 40.46 58.77 40.19 59.7 39.92 60.62 39.65 61.54 39.38 62.46 39.25 63.38 39.11 64.3 38.98 65.23 38.84 66.15 38.71 67.07 38.58 67.99 38.44 68.91 38.31 69.83 38.17 70.76 38.04 71.68 37.9 72.6 37.77 73.52 37.64 74.44 37.5 75.36 37.37 76.29 37.23 77.21 37.1 78.13 36.96 79.05 36.83 79.97 36.7 80.9 36.56 81.82 36.43 82.74 36.29 83.66 36.16 84.58 36.02 85.5 35.89 86.43 35.76 87.35 35.62 88.27 35.49 89.19 35.35 90.11 35.22 91.03 35.08 91.96 34.95 92.88 34.82 93.8 34.68 94.72 34.55 95.64 34.55 96.57 34.55 97.49 34.55 98.41 34.55 99.33 34.55 100.25 34.55 101.17 34.55 102.1 34.55 103.02 34.55 103.94 34.55 104.86 34.55 105.78 34.55 106.7 34.55 107.63 34.55 108.55 34.55 109.47 34.55 110.39 34.55 111.31 34.55 112.23 34.55");
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
(function (g) {
d3.select("defs")
.append("svg:clipPath")
.attr("id", parent_id + "_clippath2")
.append("svg:path")
.attr("d", " M17.29,5 L 115 5 115 61.94 17.29 61.94 z");g.attr("clip-path", "url(#" + parent_id + "_clippath2)");
(function (g) {
g.attr("stroke", "none")
.attr("class", "guide zoomslider")
.attr("opacity", 0.00);
(function (g) {
g.attr("stroke", "#6A6A6A")
.attr("stroke-opacity", 0.00)
.attr("stroke-width", 0.3)
.attr("fill", "#EAEAEA")
.on("click", zoomin_behavior(ctx))
.on("dblclick", function() { d3.event.stopPropagation(); })
.on("mouseover", zoomslider_button_mouseover("#cd5c5c"))
.on("mouseout", zoomslider_button_mouseover("#6a6a6a"))
;
g.append("svg:path")
.attr("d", "M108,8 L 112 8 112 12 108 12 z");
(function (g) {
g.attr("fill", "#6A6A6A")
.attr("class", "button_logo");
g.append("svg:path")
.attr("d", "M108.8,9.6 L 109.6 9.6 109.6 8.8 110.4 8.8 110.4 9.6 111.2 9.6 111.2 10.4 110.4 10.4 110.4 11.2 109.6 11.2 109.6 10.4 108.8 10.4 z");
}(g.append("g")));
}(g.append("g")));
(function (g) {
g.attr("fill", "#EAEAEA")
.on("click", zoomslider_track_behavior(ctx, 82, 99));
g.append("svg:path")
.attr("d", "M88.5,8 L 107.5 8 107.5 12 88.5 12 z");
}(g.append("g")));
(function (g) {
g.attr("fill", "#6A6A6A")
.attr("class", "zoomslider_thumb")
.call(zoomslider_behavior(ctx, 82, 99))
.on("mouseover", zoomslider_thumb_mouseover("#cd5c5c"))
.on("mouseout", zoomslider_thumb_mouseover("#6a6a6a"))
;
g.append("svg:path")
.attr("d", "M97,8 L 99 8 99 12 97 12 z");
}(g.append("g")));
(function (g) {
g.attr("stroke", "#6A6A6A")
.attr("stroke-opacity", 0.00)
.attr("stroke-width", 0.3)
.attr("fill", "#EAEAEA")
.on("click", zoomout_behavior(ctx))
.on("dblclick", function() { d3.event.stopPropagation(); })
.on("mouseover", zoomslider_button_mouseover("#cd5c5c"))
.on("mouseout", zoomslider_button_mouseover("#6a6a6a"))
;
g.append("svg:path")
.attr("d", "M84,8 L 88 8 88 12 84 12 z");
(function (g) {
g.attr("fill", "#6A6A6A")
.attr("class", "button_logo");
g.append("svg:path")
.attr("d", "M84.8,9.6 L 87.2 9.6 87.2 10.4 84.8 10.4 z");
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
}(g.append("g")));
d3.select(parent_id)
.selectAll("path")
.each(function() {
var sw = parseFloat(window.getComputedStyle(this).getPropertyValue("stroke-width"));
d3.select(this)
.attr("vector-effect", "non-scaling-stroke")
.style("stroke-width", sw + "mm");
});
}

var data = [
];

var draw = function(parent_id) {
draw_with_data(data, parent_id);
};

if ('undefined' !== typeof module) {
module.exports = draw;
} else if ('undefined' !== typeof window) {
window.draw = draw
}

return module;



Plots of the states chosen by the optimal policy over time given an initial capital somewhere in the discretized region show that their is global convergence to around the steady state value. It also shows that the discretization results in values close to the true steady state also being steady states values because the current cost of increasing decreasing capital stock by a whole bin is more than the future reward.