-
Notifications
You must be signed in to change notification settings - Fork 39
/
Jack’s_Car_Rental.py
245 lines (186 loc) · 7 KB
/
Jack’s_Car_Rental.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
# coding: utf-8
# This is the code for programming exercises 4.5 called "Jack’s Car Rental" in book "reinforcement-learning-an-introduction" #
# To better understand the code, please check Figure4.3 in chapter 4 for Pseudocode code #
# The code draw some reference to the code published at https://github.com/ShangtongZhang/reinforcement-learning-an-introduction #
# Author:Xubo Lv(lv_xubo@163.com) 2016.05 #
##################################################################################################################################
import sys,os
import numpy as np
import random
import copy
from math import *
# [1] Initialization
# states num in location 1
num_first = 21
# states num in location 2
num_second = 21
# rent reward per car
rent_reward = 10
# move reward per car
move_reward = -2
#park reward for superflous cars
park_reward = -4
#discount parameter
DISCOUNT = 0.9
#poisson distribution expected value
Poisson_request_first = 3
Poisson_return_first = 3
Poisson_request_second = 4
Poisson_return_second = 2
# Vital!! when n > 11, the probility goes nearly to zero with the respect of the expected value above
# so we don't care about what will happen when n > 11
Poisson_upbound = 11
# max cars limit
Max_cars = 20
# max moves limit
Max_moves = 5
# the number of states
num_states = num_first * num_second
# value matrix for every state
value = np.zeros((num_first,num_second))
# policy matrix for every state
policy = np.zeros((num_first,num_second))
states = []
actions = []
# initializiton of states
for i in range(0,num_first):
for j in range(0,num_second):
states.append([i,j])
# all possible actions
for i in range(-Max_moves,Max_moves+1,1):
actions.append(i)
# arbitrary initial policy
for i in range(0,num_first):
for j in range(0,num_second):
#policy[i][j] = random.randint(-5,5)
policy[i][j] = 0
# store every probability of every possible rent number or return number in avoid of duplicate calculation
poisson_table = dict()
def poisson(n,lam):
global poisson_table
# to make no duplicate keys
key = n * 10 + lam
if key not in poisson_table.keys():
poisson_table[key] = exp(-lam) * pow(lam,n) / factorial(n)
return poisson_table[key]
# core part: calculation of expected return for every possible state with possible actions
# the returns are used for update value matrix
def expect_return(single_state,single_action,value):
returns = 0.0
if (single_action >= 1):
returns += move_reward * (single_action - 1)
else:
returns += move_reward * abs(single_action)
_NumOfCarsFirst = int(min(single_state[0]-single_action,Max_cars))
_NumOfCarsSecond = int(min(single_state[1]+single_action,Max_cars))
if _NumOfCarsFirst > 10:
returns += park_reward
if _NumOfCarsSecond > 10:
returns += park_reward
for rental_request_first in range(0,Poisson_upbound):
for rental_request_second in range(0,Poisson_upbound):
#NumOfCarsFirst = int(min(single_state[0]-single_action,Max_cars))
#NumOfCarsSecond = int(min(single_state[1]+single_action,Max_cars))
NumOfCarsFirst = _NumOfCarsFirst
NumOfCarsSecond = _NumOfCarsSecond
realRentalFirst = min(NumOfCarsFirst,rental_request_first)
realRentalSecond = min(NumOfCarsSecond,rental_request_second)
NumOfCarsFirst -= realRentalFirst
NumOfCarsSecond -= realRentalSecond
reward = (realRentalFirst + realRentalSecond) * rent_reward
prob = poisson(rental_request_first,Poisson_request_first) * \
poisson(rental_request_second,Poisson_request_second)
constant_return = True
if constant_return:
rental_return_first = Poisson_return_first
rental_return_second = Poisson_return_second
NumOfCarsFirst = min(NumOfCarsFirst + rental_return_first,Max_cars)
NumOfCarsSecond = min(NumOfCarsSecond + rental_return_second,Max_cars)
returns += prob * (reward + DISCOUNT * value[NumOfCarsFirst,NumOfCarsSecond])
else:
# vital!! temperary storage in avoid of the NumOfCarsFirst was modified by the following for loop
NumOfCarsFirst_ = NumOfCarsFirst
NumOfCarsSecond_ = NumOfCarsSecond
prob_ = prob
for rental_return_first in range(0,Poisson_upbound):
for rental_return_second in range(0,Poisson_upbound):
NumOfCarsFirst = NumOfCarsFirst_
NumOfCarsSecond = NumOfCarsSecond_
prob = prob_
NumOfCarsFirst = min(NumOfCarsFirst + rental_return_first,Max_cars)
NumOfCarsSecond = min(NumOfCarsSecond + rental_return_second,Max_cars)
prob = poisson(rental_return_first,Poisson_return_first) *\
poisson(rental_return_second,Poisson_return_second) * prob
returns += prob * (reward + DISCOUNT * value[NumOfCarsFirst,NumOfCarsSecond])
return returns
if __name__ == "__main__":
theta = 1e-4
newStateValue = np.zeros((Max_cars + 1, Max_cars + 1))
while True:
# [2] Policy Evaluation
# comment part is in-place version of policy iteration
'''
error = 0
print "policy evaluation ..."
for state in states:
tmp = value[state[0],state[1]]
value[state[0],state[1]] = expect_return(state,policy[state[0],state[1]],value)
error = max(error,abs(tmp-value[state[0],state[1]]))
print ("error:",error)
if error > theta:
continue
'''
for i, j in states:
newStateValue[i,j] = expect_return([i, j], policy[i, j], value)
error = np.sum(np.abs(newStateValue - value))
print ("error:",error)
if error >= 1e-4:
value[:] = newStateValue
continue
value[:] = newStateValue
# [3] policy improvement
# comment part is in-place version of policy iteration
'''
print "evaluation done"
policy_stable = True
print "policy improvement ..."
for state in states:
tmp = policy[state[0],state[1]]
action_seq = []
for a in actions:
if (a >= 0 and a <= state[0]) or (a < 0 and abs(a) <= state[1]):
action_seq.append(expect_return(state,a,value))
else:
action_seq.append(-float('inf'))
best_action_th = np.argmax(action_seq)
policy[state[0],state[1]] = actions[best_action_th]
if tmp != policy[state[0],state[1]]:
policy_stable = False
if policy_stable:
break
else:
print "need evaluation again ..."
'''
print "evaluation done"
print "policy improvement ..."
newPolicy = np.zeros((Max_cars + 1, Max_cars + 1))
for state in states:
action_seq = []
for a in actions:
# here is where the former problem lies: a >= 0
# if you don't be very careful about the conditions,then the ultimate result will contains a little bias
if (a >= 0 and a <= state[0]) or (a < 0 and abs(a) <= state[1]):
action_seq.append(expect_return(state,a,value))
else:
action_seq.append(-float('inf'))
best_action_th = np.argmax(action_seq)
newPolicy[state[0], state[1]] = actions[best_action_th]
policyChanges = np.sum(newPolicy != policy)
print('Policy for', policyChanges, 'states changed')
if policyChanges == 0:
policy = newPolicy
break
policy = newPolicy
print ("need another evaluation...")
print "optimal value function:",value
print "optimal policy:",policy