1
$\begingroup$

Temporal difference algorithms (TD($\lambda$)) are tabular solutions to reinforcement learning problems. That is, they create a table of all the states in the problem, and estimate the expected long-term reward that can be obtained from each state.

The policy used in these situations is: "in your current state, choose to transition to the state that maximises the long-term reward". I observe that the "long-term reward" of a terminal state is precisely 0, by definition (see here).

So, if the greedy policy is to "choose the state which maximises the long-term reward", and the "long-term reward" of a terminal state is 0, doesn't that mean that the policy should never choose it, even if it has an immediate reward of 1 million points?


Minimally, practically, my query can be observed in a 3x1 gridworld. The agent starts at 0, and the goal/positive reward is in 2.

The update rule for TD(0) is:

$$ V(S_t) \leftarrow V(S_t) + \alpha\left[R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right] $$

Where $R_{t+1}$ is the immediate reward for transitioning to $S_{t+1}$.

Running this in python, I get something like $V=[0.784, 0.895, 0]$. According to my understanding of what $V(S)$ should be, this is roughly the correct result. However, if I now try to apply the greedy policy ($\epsilon=0$), it will result in the agent swapping between state=0 and state=1 forever, and never opt to go to state=2, because the long-term expected reward of that state is, by definition, 0.

Clearly there is something very fundamental that I am not understanding or missing, but I don't know what it is, or how to find it.

import random

def random_policy(V, S):
   # At the edges - immediate return
   if S == 0:
      return S+1
   if S == len(V)-1:
      return S-1
   # In the middle - choose randomly
   if random.random() > 0.5:
      return state+1
   else:
      return state-1

def greedy_policy(V, S):
   # At the edges - immediate return
   if S == 0:
      return S+1
   if S == len(V)-1:
      return S-1
   # In the middle - choose the highest estimated V(S_{t+1})
   a = V[S-1]
   b = V[S+1]
   if a < b:
      return S+1
   else:
      return S-1


gridworld = [0, 0, 1]
V =         [0, 0, 0]
ALPHA = 0.1
GAMMA = 0.9

for x in range(1000): # episodes
   state = 0
   while state != 2:
      next_state = random_policy(V, state)
      reward = gridworld[next_state]
      V[state] += ALPHA*(reward + GAMMA*V[next_state] - V[state])

      state = next_state

print(V)

$\endgroup$
1
  • $\begingroup$ Value function of terminal state being 0 is also consistent with biology when it's modeled for mesolimbic dopaminergic system responsible for reward signaling which really contains reward prediction error magically, not reward itself (the reward is originated in some other areas of brain such as OFC). Otherwise if it only contains reward thus not 0 at terminal state of episodic/continuing task, then cerebral cortex will continue to learn that have been already mastered and lead to many bad consequences such as synaptic weights growing ever stronger and interference with other newer learning. $\endgroup$
    – mohottnad
    Nov 28, 2022 at 5:53

1 Answer 1

2
$\begingroup$

Your greedy policy function is wrong.

It should be:

def greedy_policy(V, S):
   # At the edges - immediate return
   if S == 0:
      return S+1
   if S == len(V)-1:
      # Technically you should never reach here, because termination
      return S-1
   # In the middle - choose the highest estimated future return
   a = gridworld[S-1] + GAMMA * V[S-1]
   b = gridworld[S+1] + GAMMA * V[S+1]
   if a < b:
      return S+1
   else:
      return S-1

This makes sense, your state value function assumes you will follow this rule - if the greedy policy that you were evaluating really did step backwards and forwards between states 0 and 1, then the values of both those states would be $0$ because a reward is never realised.

In general, when working from a state value table $v(s)$, the greedy policy with respect to those values is given by:

$$\pi(s) = \text{argmax}_a \sum_{r,s'} p(r, s'|s,a)(r + \gamma v(s'))$$

Note this does not have to be the same policy as used to calculate $v(s)$, but in the special case of optimal value function (and therefore an optimal policy) it is.

If you want to avoid using the MDP model for transition and reward probabilities $p(r, s'|s,a)$, then you will need to work with action value estimates and use a method like SARSA($\lambda$) or Q($\lambda$). If you use an action value table $q(s,a)$ then the greedy policy is much simpler:

$$\pi(s) = \text{argmax}_a q(s,a)$$

In that case, you can select max values from your action values table.

$\endgroup$
5
  • $\begingroup$ That certainly results in expected behaviour. But why is it acceptable that the policy can depend on knowing the immediate reward for any state at all times? I thought the point of reinforcement learning was that that information is supposed to be learned through experience. $\endgroup$ Nov 24, 2022 at 0:49
  • $\begingroup$ And, if I understand the equation you shared correctly, it is choosing the action which maximises the expected reward (immediate + long-term), after accounting for rewards that only aren't always there? e.g. If it only rewards 50% of the time at state=2, then $p(r,s'|s,a)=0.5$ when considering moving (s=1, a=+1). Does that mean that $p(r,s'|s,a)$ is also somehow also estimated during training? $\endgroup$ Nov 24, 2022 at 1:08
  • 1
    $\begingroup$ @Multihunter: The TD($\lambda$) using state values that you have implemented is a (unnamed) baseline explanatory method that relies on knowing the MDP model (which is what $p(r,s'|s,a)$ is effectively). Usually you would learn about the approach on the way to implement SARSA($\lambda$) or Q($\lambda$), which don't have this limitation. In general, model-free approaches require learning action values $Q(S,A)$, not state values, for this reason. You could ask a separate question if you like why this is the case theoretically. $\endgroup$ Nov 24, 2022 at 8:02
  • $\begingroup$ Thanks. Can you update your answer to include this extra information? I got this definition from Chapter 6 of Reinforcement Learning by R. Sutton and A. Barto. I think that the most salient error I made was in my assumption of what the TD($\lambda$) algorithms are for. I assumed that they were complete solutions to reinforcement learning in their own right (even if a bit slow). It seems odd to me that it wasn't just defined as using $R_t$ instead to estimate the MDP model at the same time... $\endgroup$ Nov 25, 2022 at 8:22
  • 1
    $\begingroup$ @Multihunter Sutton & Barto introduce methods in prediction then control. When performing prediction against a fixed policy, the state value function can be more useful than the action value function. I.e. you can observe the state and make an estimate of the expected return going forward. However, you don't really want to use "raw" TD($\lambda$) against the state value function as a control method $\endgroup$ Nov 25, 2022 at 9:01

You must log in to answer this question.

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