chapter 4 Dynamic Programming Example Car Rental (in-place)
2020. 5. 5. 16:49ㆍ관심있는 주제/RL
728x90
2020/05/01 - [관심있는 주제/RL] - 강화학습 - Dynamic Programming 공부
2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example Grid World
2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example Car Rental (in-place)
2020/05/05 - [관심있는 주제/RL] - chapter 4 Dynamic Programming Example 도박사 문제
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns
from scipy.stats import poisson
In [ ]:
matplotlib.use('Agg')
Page 99¶
자동차 렌탈 잭」adc은 전국적인 자동차 렌탈 회사에서 일하며 두 지점을 관리하고 있 다. 매일 몇 명의 고객이 자동차를 텐트하기 위해 각 지점을 방문한다. 조건에 맞는 차가 있으면 잭은 차를 빌려주고 본乂!•로부터 10달러의 보상을 받는다. 해당 지점에 빌려줄 차가 없으면 거래 는 무산된다. 차는 회수된 다음 날부터 다시 대여가 가능하다. 각 지점에 렌탈 요청을 받은 차량 이 항상 구비되어 있도록 하기 위해 잭은 밤사이 두 곳의 지점에 있는 차량을 한 대당 2달러의 비 용을 들여 교환할 수 있다 한 지점에서 대여되고 회수되는 자동차의 개수가 푸아송Poisson 분포 를 따르는 확률 변수라고 가정한다. 푸아송 분포를 따른다는 것은 자동차의 개수가 n 이 될 확률 이 -A임을 의미한다. 이때 그는 개수의 평균값을 나타낸다. 대여되는 자동차 개수에 대한 A 값이 첫 번째와 두 번째 지점에서 각각 3과 4이고, 회수되는 자동차 개수에 대한 A 값은 각각 3 과 2라고 하자. 문제를 조금 단순화하기 위해，각 지점은 최대 20대까지만 자동차를 보유할 수 있다고 가정한다(2 대를 초과하는 분량은 모두 본사로 회수되기 때문에 이 문제에서 고려할 필요가 없다). 그 리고 하루 밤사이 두 지점 사이에서 교환할 수 있는 자동차의 최대 개수는 5대로 제한된다. 할인률을 $ \gamma $ = 0.9로 하고
이 문제를 연속적인 유한 MDP 문제로 형식화하겠다 이때 시간 단계는 하 루 단위이고，상태는 하루가 끝나는 시점에 각 지점이 보유한 자동차의 개수이며，행동은 밤사이 두 지점 사이에서 교환되는 자동차의 총 개수다.
그림 4.2는 차량을 교환하지 않는 정책을 시작으로 하여 정책 반복을 수행한 결과를 보여준다. 잭의 자동차 렌탈 예제가 보여주듯이，정책 반복이 수렴할 때까지 행해진 반복의 횟수는 종종 놀라울 정도로 작다. 이것은 그림 4.1 의 예제에서도 확인할 수 있다 그림 4.1 의 왼쪽 제일 아래에 있 는 다이어그램은 동일한 확률을 갖는 무작위 정책에 대한 가치 함수를 보여주고, 오른쪽 제일 아 래에 있는 다이어그램은 이 가치 함수에 대한 탐욕적 정책을 보여준다. 정책 향상 정리는 이 최종 정책들이 원래의 무작위 정책보다 더 좋다는 것을 보장한다 하지만 이 경우에는 이 최종 정책들 이 단순히 더 좋은 정책이 아니라 가장 적은 수의 단계를 통해 종단 상태에 도달한 최적 정책이 다. 이 예제에서는 단 한 번의 정책 반복만으로 최적 정책에 도달한다
문제 정의¶
In [ ]:
# maximum # of cars in each location
MAX_CARS = 20
# maximum # of cars to move during night
MAX_MOVE_OF_CARS = 5
# expectation for rental requests in first location
RENTAL_REQUEST_FIRST_LOC = 3
# expectation for rental requests in second location
RENTAL_REQUEST_SECOND_LOC = 4
# expectation for # of cars returned in first location
RETURNS_FIRST_LOC = 3
# expectation for # of cars returned in second location
RETURNS_SECOND_LOC = 2
DISCOUNT = 0.9
# credit earned by a car
RENTAL_CREDIT = 10
# cost of moving a car
MOVE_CAR_COST = 2
In [7]:
# all possible actions
"""
음의 값은 두번째 -> 첫번째 지점으로 이동 (즉 -5면 5개의 차량이 2->1로 이동)
양의 값은 첫번째 -> 두번째 지점으로 이동 (즉 -5면 5개의 차량이 2->1로 이동)
"""
actions = np.arange(-MAX_MOVE_OF_CARS, MAX_MOVE_OF_CARS + 1)
# An up bound for poisson distribution
# If n is greater than this value, then the probability of getting n is truncated to 0
"""
한 지점에 최대 10개만 있게 한다는 의미
한쪽에 쏠리는 것을 방지하기 위한?
"""
POISSON_UPPER_BOUND = 11
# Probability for poisson distribution
# @lam: lambda should be less than 10 for this function
poisson_cache = dict()
"""
poisson 확률값
key의 역할은 2가지가 있는 듯
1.기존에 나온것이 있으면 그대로 사용하기
2.첫번째 위치와 두번째 위치에 대한 중복값의 경우를 없애기 위해
first_location_key : (0,10,20,30,...100)+2
second_location_key : (0,10,20,30,...100)+3
"""
def poisson_probability(n, lam):
global poisson_cache
key = n * 10 + lam
if key not in poisson_cache:
poisson_cache[key] = poisson.pmf(n, lam)
return poisson_cache[key]
In [6]:
actions
Out[6]:
In [8]:
def expected_return(state, action, state_value, constant_returned_cars):
"""
@state: [# of cars in first location, # of cars in second location]
@action: positive if moving cars from first location to second location,
negative if moving cars from second location to first location
@stateValue: state value matrix
@constant_returned_cars: if set True, model is simplified such that
the # of cars returned in daytime becomes constant
rather than a random value from poisson distribution, which will reduce calculation time
and leave the optimal policy/value state matrix almost the same
"""
# initailize total return
returns = 0.0
# cost for moving cars
returns -= MOVE_CAR_COST * abs(action)
# moving cars
NUM_OF_CARS_FIRST_LOC = min(state[0] - action, MAX_CARS)
NUM_OF_CARS_SECOND_LOC = min(state[1] + action, MAX_CARS)
# go through all possible rental requests
for rental_request_first_loc in range(POISSON_UPPER_BOUND):
for rental_request_second_loc in range(POISSON_UPPER_BOUND):
# probability for current combination of rental requests
prob = poisson_probability(rental_request_first_loc, RENTAL_REQUEST_FIRST_LOC) * \
poisson_probability(rental_request_second_loc, RENTAL_REQUEST_SECOND_LOC)
num_of_cars_first_loc = NUM_OF_CARS_FIRST_LOC
num_of_cars_second_loc = NUM_OF_CARS_SECOND_LOC
# valid rental requests should be less than actual # of cars
"""
기존에 있는 차량수보다는 적게 렌탈이 가능하니까 다음과 같이 설정
"""
valid_rental_first_loc = min(num_of_cars_first_loc, rental_request_first_loc)
valid_rental_second_loc = min(num_of_cars_second_loc, rental_request_second_loc)
# get credits for renting
"""
rental 된 수만큼 돈을 벌기때문에 다음과 같은 reward
"""
reward = (valid_rental_first_loc + valid_rental_second_loc) * RENTAL_CREDIT
"""
빌려갔으니 더이상 차가 없다는 의미
"""
num_of_cars_first_loc -= valid_rental_first_loc
num_of_cars_second_loc -= valid_rental_second_loc
if constant_returned_cars:
# get returned cars, those cars can be used for renting tomorrow
returned_cars_first_loc = RETURNS_FIRST_LOC
returned_cars_second_loc = RETURNS_SECOND_LOC
"""
남은 차량과 회수 되는 것 포아송 lambda값 을 이용 (대여되는 자동차의 개수(상수))
"""
num_of_cars_first_loc = min(num_of_cars_first_loc + returned_cars_first_loc,
MAX_CARS)
num_of_cars_second_loc = min(num_of_cars_second_loc + returned_cars_second_loc,
MAX_CARS)
"""
각 지점에서 렌탈이 될 확률 * (보상 + 할인율 * 상태 가치 함수)
"""
returns += prob * (reward + DISCOUNT * state_value[num_of_cars_first_loc,
num_of_cars_second_loc])
else:
"""
대여되는 자동차의 모든 개수를 고려
"""
for returned_cars_first_loc in range(POISSON_UPPER_BOUND):
for returned_cars_second_loc in range(POISSON_UPPER_BOUND):
prob_return =(
poisson_probability(returned_cars_first_loc,
RETURNS_FIRST_LOC) *
poisson_probability(returned_cars_second_loc,
RETURNS_SECOND_LOC))
num_of_cars_first_loc_ = min(num_of_cars_first_loc + returned_cars_first_loc,
MAX_CARS)
num_of_cars_second_loc_ = min(num_of_cars_second_loc + returned_cars_second_loc,
MAX_CARS)
"""
각 경우의 수의 확률의 곱 * 각 지점에서 렌탈이 될 확률
"""
prob_ = prob_return * prob
"""
Bellman Expectation Equation
"""
returns += prob_ * (reward + DISCOUNT *
state_value[num_of_cars_first_loc_,
num_of_cars_second_loc_])
return returns
In [9]:
def figure_4_2(constant_returned_cars=True):
value = np.zeros((MAX_CARS + 1, MAX_CARS + 1))
policy = np.zeros(value.shape, dtype=np.int)
iterations = 0
_, axes = plt.subplots(2, 3, figsize=(40, 20))
plt.subplots_adjust(wspace=0.1, hspace=0.2)
axes = axes.flatten()
while True:
fig = sns.heatmap(np.flipud(policy), cmap="YlGnBu", ax=axes[iterations])
fig.set_ylabel('# cars at first location', fontsize=30)
fig.set_yticks(list(reversed(range(MAX_CARS + 1))))
fig.set_xlabel('# cars at second location', fontsize=30)
fig.set_title('policy {}'.format(iterations), fontsize=30)
"""
policy evaluation (in-place)
Q : 왜 단 한번의 policy iteration이라고 하는 것인지??
A : 이유는 기존 policy iteration 같은 경우 2개의 value function을 유지하지만,
해당 코드에서는 value function 1개만을 가지고 덮어쓰는 방향으로 하고 있는데,
이러한 방법을 in-place라고 한다고 함.
"""
while True:
old_value = value.copy()
for i in range(MAX_CARS + 1):
for j in range(MAX_CARS + 1):
"""
각 지점에서 차량의 개수가 있을 때, 그 상황에서 상태강치 함수 계산하기
ex ) 첫번째는 0 두번째 0일 때,
정책과 현재 상태에서의 k번째 가치 함수를 통해 k+1 가치 함수를 계산함
"""
new_state_value = expected_return([i, j],
policy[i, j],
value,
constant_returned_cars)
value[i, j] = new_state_value
max_value_change = abs(old_value - value).max()
print('max value change {}'.format(max_value_change))
if max_value_change < 1e-4:
break
"""
policy improvement
policy를 update하는 부분
처음에는 행동을 0만 하다가 점점 업데이트
"""
policy_stable = True
for i in range(MAX_CARS + 1):
for j in range(MAX_CARS + 1):
old_action = policy[i, j]
action_returns = []
"""
actions : -5 ~ 5
"""
for action in actions:
"""
행동을 하였을 때 해당하는 지점에 그만큼의 차량이 있어야 하므로
아래와 같은 if문이 생김
"""
if (0 <= action <= i) or (-j <= action <= 0):
action_returns.append(
expected_return([i, j],
action,
value,
constant_returned_cars))
else:
action_returns.append(-np.inf)
"""
각 상태에서의 모든 행동을 고려하여 최고의 값을 action으로 설정
"""
new_action = actions[np.argmax(action_returns)]
policy[i, j] = new_action
"""
기존 행동과 바뀐 행동사이의 변화가 있으면 policy evaluation부터 다시 진행
없으면 멈추는 구조
"""
if policy_stable and old_action != new_action:
policy_stable = False
print('policy stable {}'.format(policy_stable))
if policy_stable:
fig = sns.heatmap(np.flipud(value), cmap="YlGnBu", ax=axes[-1])
fig.set_ylabel('# cars at first location', fontsize=30)
fig.set_yticks(list(reversed(range(MAX_CARS + 1))))
fig.set_xlabel('# cars at second location', fontsize=30)
fig.set_title('optimal value', fontsize=30)
break
iterations += 1
plt.savefig('./images/figure_4_2.png')
plt.close()
In [10]:
if __name__ == '__main__':
figure_4_2()
In [ ]:
728x90
'관심있는 주제 > RL' 카테고리의 다른 글
| Chapter 5 Monte-Carlo Learning 공부 (0) | 2020.05.16 |
|---|---|
| chapter 4 Dynamic Programming Example 도박사 문제 (0) | 2020.05.05 |
| chapter 4 Dynamic Programming Example Grid World (0) | 2020.05.05 |
| 강화학습 - Dynamic Programming 공부 (0) | 2020.05.01 |
| state value / state action value 관련 자료 (0) | 2020.04.27 |