# Semi-gradient TD(0) Choosing an Action

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.

• Can you explain more clearly what your task is? The algorithm you have given is for approximating the value function when you already have a policy - i.e. it is for evaluation. If you want to learn an optimal policy whilst playing the game, you need a control algorithm instead (they look very similar, but do important things such as define $\pi$ and how it is modified - or implied for control if not explicit). There is a control version of TD(0). It looks like you jumped straight into a later chapter of the book, to do with approximate methods - have you read the earlier chapters? – Neil Slater Apr 6 '17 at 9:02
• @NeilSlater I have, I'm afraid, and to little avail, it seems. But come to think of it, you are right -- I am doing evaluation with nothing to evaluate. In short, I want to learn an optimal policy while playing the game, as you put it. So I imagine semi-gradient Sarsa for control would be adequate. Would choosing actions still work by taking the dot product of the features and the weights, in the linear case? Thanks, Neil. – end1dream Apr 6 '17 at 10:00
• The optimal algorithm probably won't use any kind of learning at all; it'll probably be some kind of dynamic programming algorithm. Are you interested in that answer? Or are you only interested in solutions that use machine learning (even if they aren't necessarily as good as a dedicated algorithm that is designed specifically for this application)? – D.W. Apr 6 '17 at 20:25
• @D.W. The OP is working from a book about Reinforcement Learning that includes Dynamic Programming as a foundation, and the algorithm shown is built around DP ideas, extended using sampling and approximations. DP won't work here by itself because the state size is too large (although yes it would work at a theoretical level, just not be practical). I think RL is often considered a type of machine learning, especially when using these approximate methods. – Neil Slater Apr 6 '17 at 20:53

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 . . .)

• How can one choose the argmax of q using a neural network as a representation of q? – zimmerrol Jul 25 '17 at 11:12
• @flashtek That is a different question, why not ask it. There are two main options. But essentially you must make the estimate s before you can take the max. – Neil Slater Jul 25 '17 at 15:29
• I asked a new, seperate question - maybe you can give me there more details. stackoverflow.com/questions/45377404/… – zimmerrol Jul 28 '17 at 17:14