스탠포드 CS221: 마르코프 결정 과정(MDP) 및 정책 평가 기초

class FlakyTramMDP(MDP):
    def __init__(self, num_locs=10, failure_prob=0.4):
        self.num_locs = num_locs
        self.failure_prob = failure_prob

    def successors(self, state):
        # Walk action
        if state + 1 <= self.num_locs:
            results.append(Step(action='walk', prob=1, reward=-1, state=state + 1))
        # Tram action with failure probability
        if 2 * state <= self.num_locs:
            results.append(Step(action='tram', prob=1 - self.failure_prob, reward=-2, state=2 * state))
            results.append(Step(action='tram', prob=self.failure_prob, reward=-2, state=state))
        return results

def compute_q_value(successors, discount, values):
    q_val = 0
    for step in successors:
        # Q(s, a) = sum(T(s, a, s') * [R(s, a, s') + gamma * V(s')])
        q_val += step.prob * (step.reward + discount * values[step.state])
    return q_val

for iter in range(max_iters):
    new_values = {}
    for state in states:
        if mdp.is_end(state):
            new_values[state] = 0
            continue
        # Policy Evaluation: V(s) = Q(s, pi(s))
        action = policy(state)
        successors = mdp.successors(state, action)
        new_values[state] = compute_q_value(successors, mdp.discount(), values)
    # Check for convergence
    if compute_distance(values, new_values) < tolerance:
        break
    values = new_values