Jack's Car Rental

2019-05-30 本文已影响0人捡个七

Jack's Car Rental 是一个经典的应用马尔可夫决策过程（MDP）的问题。下图来自 Reinforcement Learning: An Introduction 这本书的 98 页。

C 语言编程课的 Term Project 就是解决这个问题，在这里记录一下相关内容。

Jack 租车问题概述如下：

Jack 有 2 个租车点，Location 1 和 Location 2；
每个租车点最多停放 20 辆车；
每租出去一辆车获利 10 美金；
每天租出去的车和收回的车的数量均服从泊松分布：
- Location 1：
  - 租出：λ = 3
  - 回收：λ = 3
- Location 2：
  - 租出：λ = 4
  - 回收：λ = 2
每天夜里 Jack 在两个租车点之间进行车辆调整，每晚最多调度 5 辆车，且每辆车花费 2 美金。
折扣率 γ = 0.9；
试问使用什么调配策略可以使得盈利最优化？

从上面提供的信息中，可以分析出以下内容：

每个租车点最多 20 辆 → 状态数量为 21*21 = 441（包括车辆为 0 的情况）
每晚最多调配 5 辆车，动作集合则有：A= {(-5, 5), (-4, 4),...,(0, 0), (1, -1),...,(5, -5)}，其中 (a1, a2) 表示为 (Location 1 出入的车辆数，Location 2 出入的车辆数)，正好表示入，负号表示出。

描绘成 MDP 如下所示：

MDP JackCarRenral
    states cars[2]
    actions moveCars
    reward r
    discount rate 0.9
    vaild states { 0 <= cars <= 20 } 
    vaild actions {-5 <= moveCars <= 5}
    environment
        random requests [poisson(3); poisson(4)]
        random dropoffs [poisson(3); poisson(2)]
        nextMorn = min(cars + [-moveCars, moveCars], 20)
        satisfied_req = min(requests, nextMorn)
        new_cars = nextMorn + dropoff - satisfied_req
        new_cars = max(new_cars, 0)
        new_cars = min(new_cars, 20)
        r = satisfied_req * 10 - 2 * abs(moveCars)

初始化

一旦指定了 λ 的值，我们就可以计算出两地的 prob 和 reward。

/* Initialization */
void init_probs_rewards(double probs[next_morning][ncar_states], double rewards[next_morning], 
double l_reqsts, double l_drpffs){
    double req_prob;
    double drp_prob;
    int satisfied_req; // the number of satisfied requests
    int new_n;
    for(int req = 0; (req_prob = poisson(req, l_reqsts)) > theta; req++){
        for(int n = 0; n < next_morning; n++){
            satisfied_req = min(req, n); // at most, all the cars avaliable
            rewards[n] += RENTAL_INCOME * req_prob * satisfied_req; 
        }
        for (int drp = 0; (drp_prob = poisson(drp, l_drpffs)) > theta; drp++){
            for (int  m = 0; m < next_morning; m++){
                satisfied_req = min(req, m);
                new_n = m + drp - satisfied_req; 
                new_n = max(new_n, 0); // 0 at least
                new_n = min(20, new_n); // 20 at most
                probs[m][new_n] += req_prob * drp_prob; // add up the joint probability
            }
        }