0
$\begingroup$

I am trying to implement TD(0) among other RL Policy Evaluation techniques.

I have also implemented the dynamic programming approach for a given model of the world and FV Monte Carlo and EV Monte Carlo for the unknown case. It seems that my implementation for TD(0) does not converge to the right state-values for my value_fuction. The other approaches work, so I don't think it is a problem of data stuctures in my case. I let TD(0) also work on pre-sampled episodes, but no matter how many episodes I use and how simple the state and action spaces are, it just does not yield the same results as MC. Here is my implementation:

def td_0(
    episodes: list[Episode],
    states: set[State],
    reward_function: RewardFunction,
    gamma: float = 0.9,
    alpha: float = 0.1,
):
    value_function = ValueFunction({s: 0 for s in states})

    # Episodes are lists of [state, action, reward, state, action, reward, ... , state]
    for epi in episodes:
        state_index = 0
        while state_index < len(epi):
            state = epi[state_index]
            if state_index == len(epi) - 1: # for terminal state value is reward
                value_function.set_value(state, reward_function.get_reward(state))
                break

            next_state = epi[state_index + 3]
            # compute new value
            new_value = value_function.get_value(state) + alpha * (
                reward_function.get_reward(state)
                + gamma * value_function.get_value(next_state)
                - value_function.get_value(state)
            )

            value_function.set_value(state, new_value)  
 
            # set next state index
            state_index += 3

    return value_function

Or is it simply a question of how to set the learning rate? For example, I use the following model to sample the episodes:

# define some states
s1 = State(1)
s2 = State(2)
s3 = State(3)
states = {s1, s2, s3}

# define some actions
a1 = Action(1)
a2 = Action(2)
actions = {a1, a2}

# dynamics model syntax: (current_state, action, next_state, probability)
dynamics_model = Dynamics(
    [
        (s1, a1, s2, 1),
        (s1, a2, s3, 1),
    ]
)

# policy syntax: (state, action, probability)
pi = Policy(
    [
        (s1, a2, 0.5),
        (s1, a1, 0.5),
    ]
)

# reward function syntax: {state: reward}
reward_function = RewardFunction({s1: 1, s2: -1, s3: 1})

It is a very simple example with terminal states s2 and s3 and it is clear that the Value function should converge to: V(s1) = 1, V(s2) = -1, V(s3) = 1 which my implementations of MC and DP do, so whats wrong with my TD?

Here are some outputs of some runs:

Nr. Episodes: 10000
Dynamic Programming
{State_1: 1.0, State_2: -1.0, State_3: 1.0}
First visit Monte Carlo
{State_1: 1.0134, State_2: -1.0, State_3: 1.0}
Every visit Monte Carlo
{State_1: 1.0134, State_2: -1.0, State_3: 1.0}
Temporal Difference (0)
{State_1: 1.5552992453591237, State_2: -1, State_3: 1}
Nr. Episodes: 10000
Dynamic Programming
{State_1: 1.0, State_2: -1.0, State_3: 1.0}
First visit Monte Carlo
{State_1: 1.0114, State_2: -1.0, State_3: 1.0}
Every visit Monte Carlo
{State_1: 1.0114, State_2: -1.0, State_3: 1.0}
Temporal Difference (0)
{State_1: 0.07098345716518928, State_2: -1, State_3: 1}
$\endgroup$
8
  • $\begingroup$ I made an answer, but I'm not 100% sure of it yet. I need to understand how rewards are granted in the environment. In the TD(0) code, following the step, you assign the reward value from the state you are leaving. That would always be 1 for leaving state $s_1$. But then no action could be taken in states $s_2$ and $s_3$, so their associated rewards make no sense at all. You are using them (incorrectly) in the TD(0) code, which may be part of your problem there. But there's more than that going wrong, and I suspect all your value estimators are incorrect. $\endgroup$ Oct 1, 2023 at 20:56
  • $\begingroup$ So could you please explain when the rewards associated with each state are being observed/received by the agent? Typically rewards associated with a state are granted either for leaving each state, or for arriving in each state. Your code sort of assumes both, but which did you intend? $\endgroup$ Oct 1, 2023 at 20:58
  • $\begingroup$ @NeilSlater Rewards are granted when you leave a state and get to the next state. But for my terminal states, you get the reward when you reach them. You are right that is kinda weird, but I think it still makes sense doesn't it? The value of $s1$ for my policy should be $V(s1) = R(s1) + 1/2*V(s2) + 1/2*V(s3)$. So why can't I say that $V(s2) = R(s2)$? It should give me the correct result that $V(s1) = 1 + 1/2 * 1 + 1/2 * (-1) = 1$. Value function is defined as immediate reward + dicounted sum of future rewards, but for terminal states there are no future rewards. $\endgroup$
    – mavex857
    Oct 2, 2023 at 8:11
  • $\begingroup$ Well, it would be part of my answer. You have got the MDP model a bit muddled. But just to be clear for me, you have only two possible trajectories in your environment, and each will grant a single reward - could you clarify what the numerical reward is in each case, and why? First trajectory is $s_1, a_1, r_a, s_2$ - what is $r_a$ and why? Second trajectory is $s_1, a_2, r_b, s_3$ - what is $r_b$ and why? $\endgroup$ Oct 2, 2023 at 9:32
  • $\begingroup$ @NeilSlater Actually, the way I implemented the sampling of episodes, $r_{a}$ and $r_{b}$ would be $-1$ and $1$ respectively, so actually you obtain the reward when you enter a state. The sampled episodes are $s_{1}$, $a_{1}$, $-1$, $s_{2}$ and $s_{1}$, $a_{2}$, $1$, $s_{3}$. But still I don't even use the $r$ values from the episode in my TD(0) implementation. I just iterate over the states, skipping actions and rewards, and compute the rewards from my reward_function. So the implementation would also work with just a list of states that does not contain the rewards. You know what I mean? $\endgroup$
    – mavex857
    Oct 2, 2023 at 12:50

1 Answer 1

1
$\begingroup$

It is a very simple example with terminal states s2 and s3 and it is clear that the Value function should converge to: V(s1) = 1, V(s2) = -1, V(s3) = 1 which my implementations of MC and DP do, so whats wrong with my TD?

It is not 100% clear whether you are trying to learn optimal control, or learn policy evaluation. I don't see any control logic in your TD example code though, and you specify an equiprobable policy. So I think you are coding policy evaluation.

The correct state values for this environment and the equiprobable policy are:

$$v(s_1) = 0, v(s_2) = 0, v(s_3) = 0$$

None of your implementations are getting this correct.

The correct state values for this environment and the optimal policy (choose $a_2$ in $s_1$) are:

$$v(s_1) = 1, v(s_2) = 0, v(s_3) = 0$$

The discount factor will have no impact for a single-step environment, it is only the immediate reward that will be taken into consideration.

I suspect you have some off-by-one errors in how you are thinking about assigning reward and calculating value, in all of your agent implementations. You seem to be missing that the state value of a state is the expected future reward and are including the reward for arriving in the state as part of the state's value. Whilst the value of all terminal states has to be $0$ by definition since no reward can be received once the episode has terminated.

Without seeing your DP and MC implementations, it is also possible that you have implemented a control method for those (Value Iteration and Policy Iteration are usually presented as control methods by default), and a prediction method (calculate value function for a provided policy) for the TD(0), and that might explain some of the difference you are seeing. In Sutton & Barto's book, TD is split into prediction and control methods with prediction being explained with pseudocode first, and TD(0) is very rarely used for control because it needs access to the MDP model in order to be used that way - it is more common to implement e.g. SARSA or Q-learning for TD control.

From a coding perspective, your TD(0) learning loop is poorly structured in that it mixes processing data parameters from the environment (incorrectly) with the TD learning logic. What would probably help you most is separating the environment step function from the TD loop, and having a more formally-defined environment class. To support both model-free and model-based agents, you will need both a env.step(action) method, returning a tuple of (reward, next_state, done) - for model-free methods - and a env.transitions(action) which returns a transitions array of tuples [(probability, reward, next_state, done),...] that dynamic programming and TD(0) control can work through. You could also do something similar for the policy, although it is more common to make that a simple function in the agent's code as opposed to part of a separate class.

$\endgroup$
2
  • $\begingroup$ So by that definition, that $V(s)$ only contains the discounted future rewards and does not contain the immediate reward for $s$, it doesn't make sense at all to assign a reward to the start states, right? Because that reward will never be represented in any value (only if we have a loop and enter the start state again) $\endgroup$
    – mavex857
    Oct 3, 2023 at 18:09
  • $\begingroup$ @mavex857 In your case, probably no point in having that extra s1: 1 in the data. However, the way you are assigning rewards to state is not the only possibility for MDP definition. The most general reward function is a distribution of real numbers returned by $r(s,a,s')$. So you could be determining reward with some combination of start and end state if you wished. It's part of the environment definition, so you would do it if it made sense for your environment. That's why I needed to ask earlier. $\endgroup$ Oct 3, 2023 at 18:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .