1
$\begingroup$

The code of computing the state-value function $V^{\pi_{n}}$ is

def compute_vpi(mdp, policy, gamma):
    """
    Computes V^pi(s) FOR ALL STATES under given policy.
    :param policy: a dict of currently chosen actions {s : a}
    :returns: a dict {state : V^pi(state) for all states}
    """
    all_states, n = mdp.get_all_states(), len(mdp.get_all_states())
    state_index = {s: i for i, s in enumerate(all_states)}
    a, b = np.zeros((n, n)), np.zeros(n)
    for i, state in enumerate(all_states):
        vs = [1] + [0] * (n-1)  # current line of state
        next_state = mdp.get_next_states(state, policy[state])
        b[i] = sum([mdp.get_transition_prob(state, policy[state], next_s) * 
                    mdp.get_reward(state, policy[state], next_s)
                    for next_s in next_state])
        for next_s in next_state:
            vs[state_index[next_s]]  = - mdp.get_transition_prob(state, policy[state], next_s)
        a[i] = vs
    return {state: v for v, state in zip(np.linalg.solve(a, b), all_states)}

And I found that some states are the terminal state that if agent steps into these states, current episode ends. But in the policy, I don't konw how to set actions, since in mdp, there are no possible actions in the terminal state.

How can I taking into consideration the terminal state when computing the state-value function $V^{\pi_{n}}$ at each iteration?

$\endgroup$
4
  • 1
    $\begingroup$ I suspect the down vote is for the code, as Cross Validated likes to have questions closer to stats and maths theory. You may find this sort of practical "how do I address code issue in machine learning" question works better in Data Science or Stack Overflow. Regarding the code, it would be a good idea to explain what actually goes wrong - does the code run but give incorrect results, or is there an error? $\endgroup$ Apr 19, 2018 at 7:19
  • $\begingroup$ To me, this looks like a practical coding concern in Python, and not really to do with reinforcement learning (although understanding RL allows reader to understand the purpose of the code). $\endgroup$ Apr 19, 2018 at 7:20
  • $\begingroup$ @NeilSlater, Thank you, the question is a practical coding concern of policy iteration. Thank you for your suggestion. $\endgroup$
    – GoingMyWay
    Apr 19, 2018 at 10:09
  • $\begingroup$ @NeilSlater, hi, I answered my question. $\endgroup$
    – GoingMyWay
    May 15, 2018 at 2:35

1 Answer 1

2
$\begingroup$

Answer my question

Recall that $V^{\pi}$ satisfies the following linear equation: $$V^{\pi}(s) = \sum_{s'} P(s,\pi(s),s')[ R(s,\pi(s),s') + \gamma V^{\pi}(s')]$$

the code can be

def compute_vpi(mdp, policy, gamma, num_iter=1000, min_difference=1e-5):
    """
    Computes V^pi(s) FOR ALL STATES under given policy.
    :param policy: a dict of currently chosen actions {s : a}
    :returns: a dict {state : V^pi(state) for all states}
    """
    # YOUR CODE HERE
    index_s = {i: s for i, s in enumerate(mdp.get_all_states())}
    s_index = {s: i for i, s in enumerate(mdp.get_all_states())}

    ns = len(mdp.get_all_states())
    a, b = np.zeros((ns, ns)), np.zeros(ns)
    for i in range(ns):
        b_v = 0
        state = index_s[i]
        a[i][i] = 1 - mdp.get_transition_prob(state, policy[state], state) * gamma
        for s_prime in mdp.get_next_states(state, policy[state]):
            if s_prime == state: continue
            a[i][s_index[s_prime]] = \
                -mdp.get_transition_prob(state, policy[state], s_prime) * gamma
            b_v += mdp.get_transition_prob(state, policy[state], s_prime) *\
                mdp.get_reward(state, policy[state], s_prime)
        b[i] = b_v

    solution = np.linalg.solve(a, b)
    return {index_s[i]: v for i, v in enumerate(solution)}

The best practice to solve the equation is to build a matrix a and b and loop in each state and each entry of the matrix a, and b to update corresponding values.

$\endgroup$
2
  • $\begingroup$ To me it was a bit tricky to see what should be in a matrix and b vector. I think it's worth noting that the aforementioned equation should be transformed such that all V is on the left side and constants (P * R) on the right side. Then unroll it into matrices. $\endgroup$
    – Lubiluk
    Feb 17, 2020 at 13:31
  • $\begingroup$ @Lubiluk It is a working code for solving policy iteration via solving a linear equation. That is what I exactly did in the code by creating matrice a and b. $\endgroup$
    – GoingMyWay
    Feb 18, 2020 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.