1
$\begingroup$

I am working on an application of reinforcement learning in an environment in which the number of possible actions increasing throughout an episode. The first step has only 8 possible actions, which increases to a maximum of 24 towards the end of the episode (increasing with 2 after every valid action taken).

I'm using linear function approximation with a set of weights $w$ to estimate $Q(s,a)$. I'm using the 'dimension scaling trick' proposed here to create a set of feature values (only based on $s$) and place them in feature vector $F$ according to $a$:

$\phi(s,a_1) = \begin{bmatrix} \psi_1(s,a_1) \\ \psi_2(s,a_1) \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} ,\quad \phi(s,a_2) = \begin{bmatrix} 0 \\ 0 \\ \psi_1(s,a_2) \\ \psi_2(s,a_2) \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} ,\quad \phi(s,a_3) = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \psi_1(s,a_3) \\ \psi_2(s,a_3) \\ 0 \\ 0 \\ 1 \end{bmatrix} $

Since only the first 8 actions are available at start, the weights for these features start to rise at the start of the episode. When more actions become available, they are simply never selected since greedy selection always leads to selection of actions from those first 8. I am wondering how to deal with this. I have thought of normalizing the weights with respect to the number of times an actions has been taken, but I have not been able to fully put it together.

$\endgroup$
2
$\begingroup$

When more actions become available, they are simply never selected since greedy selection always leads to selection of actions from those first 8.

Don't use greedy action selection. Use $\epsilon$-greedy, with a moderate version of $\epsilon$ to start with (e.g. 0.5), and reduce $\epsilon$ over time.

Another simple fix for this is ensure your initial weights for all actions are initialised optimistically - predicting a high reward - so that to start with there is more exploration.

There are more sophisticated action selection methods that can do better than either of these simple tricks, such as Gibbs action sampling (a temperature-controlled "softmax") or upper confidence bound action selection (that tracks how often an action has been taken versus the possibility that its estimate is too low). You can look these up (or ask on this site) if the simple ideas don't work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.