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)