Semi-gradient TD(0) Choosing an Action

Question

I am trying to write an optimal control agent for a simple game that looks like this:

The agent can only move along the x-axis, and has three actions available to it: left, right, and do nothing. A random number of falling rocks are spawned at arbitrary positions along the top row. The goal is to survive as long as possible by avoiding collision on each time step.

Here's what I've done so far:

1) I use a feature vector $Φ$ with $Φ_0(s)$ being the current x-coordinate of the agent and $Φ_1(s)...Φ_n(s)$ taking on a 0 or 1 (1 indicating the presence of a rock).

2) The corresponding weight vector $θ$ is initialized to 0 for all weights. So I have the linear function approximation $$\hat v(s,θ)=\sum_{i=0}^nΦ_i(s)θ_i$$

3) The reward on each time step is 1, and 0 upon collision.

I'm actually trying to implement the algorithm below from Sutton and Barto's 2017 draft.

---

Semi-gradient TD(0) for estimating $\hat{v} \approx v_{\pi}$

Input: the policy ${\pi}$ to be evaluated
Input: a differentiable function $\hat{v} : \mathbf{S^+} \times \mathbb{R}^n \rightarrow \mathbb{R}$ such that $\hat{v}(terminal,·) = 0$

Initialize value-function weights $\theta$ arbitrarily (e.g., $\theta = 0$)
Repeat (for each episode):
$\qquad$Initialize $S$
$\qquad$Repeat (for each step of episode):
$\qquad\qquad$Choose $A \sim \pi(·|S)\qquad$ # Not sure how to choose action here
$\qquad\qquad$Take action $A$, observe $R, S'$
$\qquad\qquad\theta \leftarrow \theta + \alpha[R + \gamma \hat{v}(S',\theta) − \hat{v}(S,\theta)]\nabla\hat{v}(S,\theta)$
$\qquad\qquad S \leftarrow S'$
$\qquad$until $S'$ is terminal

---

My problem is this:

1) Is this even an appropriate algorithm to apply to this sort of task? It feels like a policy gradient approach would be more suitable.

2) If yes to 1), how do I choose an action? In the algorithm above, this appears as "Choose $A \sim \pi(·|S)$" Since the policy is implicit, I compute the approximate value of the state as shown in 2) above and then greedify over the three actions (no ε-greedy, though), but the only thing that changes is $Φ_0(s)$. I'm definitely missing something.

Answer 1

1) Is this even an appropriate algorithm to apply to this sort of task?

No, you have selected an evaluation algorithm from chapter 9 of the book. None of the algorithms in chapter 9 are control algorithms. They are all designed to estimate the value function for a policy supplied as input. The corresponding control algorithms are discussed in chapter 10.

The current draft of the book does not give the corresponding TD(0) control algorithm with linear estimator. However, that algorithm does exist and might be suitable (with caveats). In fact in your case it could even have benefits over action-value based methods, because you reduce the scope of estimates needed by a factor of 3. This is something that you can take advantage of only if you have a full model of the environment, so can look ahead one time step to determine the best action. Without a model of the environment, or if you don't want to use the model in your agent, then you must use an action value based algorithm like Monte Carlo, SARSA or Q Learning.

2) If yes to 1), how do I choose an action?

Well it was a no, but you could use the control version of TD(0). Then you have the problem of using your state value function to figure out the policy. The rule here is that to use state values you need to use a model of the environment. Specifically you need to be able to predict the next state and immediate reward given the current state and action. In the book, this is usually represented by the transition function $p(s′,r|s,a)$ which gives the probability of each possible successor state and reward. In a fully deterministic game, the probability is just 1.0 for one target state and reward caused by each action. In your case you have new rocks appearing randomly at the top. To be complete you would probably have to model this in detail (which would be painfully slow). However, given the very low influence of this top row, and how little planning the agent can do to deal with it, I'd be tempted to just sample it.

Assuming you want to choose the greedy action, then you can find a policy by taking $argmax_a$ over the next step. When you have a state value function, then you have to run the step forward in simulation to figure out the expectation over each action. This is the same calculation for greedy policy as used in dynamic programming (back in chapter 4 of the book):

$\pi(s) = argmax_a \sum_{s'} p(s',r|s,a) (r + \gamma \hat{v}(s',\theta))$

Of course this is a lot simpler if you used action values istead (e.g. in SARSA):

$\pi(s) = argmax_a \hat{q}(s,a,\theta)$

. . . so despite the fact this is less efficient, you might want to use action values for less effort in this part.

---

One additional thing you are likely to have problems with: Your choice of state representation does not have good linear relationship with the true value function. The linear estimator is quite limited in what it can do. A better estimator here would be a neural network with at least one hidden layer.

However, you can probably tweak the representation slightly to get something that will work a little bit with a linear estimator - the trick is to have the rocks part of the state represented relative to the agent - i.e. don't have a grid of absolute positions of rocks, but make the grid relative to the agent. That way, a rock directly above the agent will always contribute the same to the current state value, which is important. Without this tweak, and using a linear approximator, your agent will not learn optimal control, it will instead learn a kind of fatalistic "with these many rocks, I have roughly this long to live" value function and probably just take random actions (if the distribution of rocks is not even it might learn to move to a particular column . . .)