I have come across a Google paper that uses the REINFORCE algorithm (a Policy Gradient Method) for a case where the trajectory of the episodes it proposes would be only one step.

When trying to replicate the experiments they propose I found that there are some problems with the stability of the method (maybe that's why it is not accepted by peer review).

Researching on my own I have found something I suspected, and that is that the problem they present could be solved as a multiarmed bandit problem in THIS link. But because of this event, I have the doubt if using methods based on trajectories (such as Policy Gradient Methods) has some mathematical problem in situations where the trajectory is a single step.

PS: I think the problem of this paper may be also that they average only after one execution of a trajectory and not over k trajectories as it is necessary for a Policy Gradient Method, so I would also like to know the opinion of more people about this issue.

  • $\begingroup$ You say that the paper is not accepted by peer review but I see that it's accepted to "Proceedings of the 37th International Conference on Machine Learning". There is nothing wrong with using PG methods when there is only 1 step, the validity of approach does not depend on the length of the episode, whether it is useful or not is another question. $\endgroup$
    – Brale
    Commented Mar 17, 2021 at 17:23
  • $\begingroup$ True, I was mistaken about that. What do you think about averaging k trajectories?Recoding the problem, I face the issue that as I improve the episodes of the process, every data value converges to a value of 0.5 and I cannot figure out why. $\endgroup$
    – Angelo
    Commented Mar 17, 2021 at 19:06
  • $\begingroup$ yes, you can take a batch of samples, average policy gradients and then apply the result, seems reasonable to me $\endgroup$
    – Brale
    Commented Mar 17, 2021 at 19:32

1 Answer 1


The fundamental idea behind policy gradient is just to maximise the return averaged across all probably trajectories, i.e

$$\begin{align} J(\theta) &= E[\sum\limits_{t=1}^{\tau}r(s_t,a_t)]\\ &=E_{\tau\sim p(\tau)}[R(\tau)] \end{align}$$

Where $\tau$ represents the probability of selecting a particular trajectory, if the trajectories all have fixed length then $\tau$ only has non-zero probability for trajectories of the specified length which in this case is 1.

The REINFORCE algorithm takes this expression and with some simplifications (causality to improve variance) and manipulation (log trick) obtains the gradient, pretty much as simple as that.

Intuition of algorithm in paper

In the algorithm they denote the $\pi_\theta$ (which is typically reserved for describing the policy) as the probability of the selection vector. By considering instead that the function $h_{\theta}$ as the policy instead I think it can be seen that they are actually averaging over multiple trajectories.

So we instead think of the data points as state-action pairs that we pass into $h_\theta$ to get the probability of selecting said action for a given state. These probabilities then dictates whether we choose the action or not. An alternative way to interpret this as if we imagine the action space for each state as binary then we can think of the "other action" as not impacting the predictor.

The gradient used for updating the parameters associated with the policy uses the log probability of $\pi_\theta$ which if we expand it, expressing it using $h_\theta$, (as done on page 4) we can see it's the sum of the log probabilities of selecting (or not selecting) each data point.

By considering the return for each data point constant (each data point has the same loss incurred by predictor model on the validation set) and absorbing the average over batch size into the step size $\beta$ it could be interpreted as an average

Stability issues

RL is plagued with stability issues, be it selection of hyper parameters, random seeding etc. It's hard to often pinpoint why results aren't exact but as long as you get something in a similar ball park i'd say thats pretty good going


You must log in to answer this question.

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