# Tag Info

16

Just ignore the invalid moves. For exploration, it is likely that you won't just execute the move with the highest probability, but instead choose moves randomly based on the outputted probability. If you only punish illegal moves they will still retain some probability (however small) and therefore will be executed from time to time (however seldom). So you ...

14

Usually softmax methods in policy gradient methods using linear function approximation use the following formula to calculate the probability of choosing action $a$. Here, weights are $\theta$, and the features $\phi$ is a function of the current state $s$ and an action from the set of actions $A$. $$\pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \... 11 That can be done. For example, Chapter 13 of the 2nd edition of Sutton and Barto's Reinforcement Learning book (page 332) has pseudocode for "Actor Critic with Eligibility Traces". It's using G_t^{\lambda} returns for the critic (value function estimator), but also for the actor's policy gradients. Note that you do not explicitly see the G_t^{\lambda} ... 9 The discount factor does appear twice, and this is correct. This is because the function you are trying to maximise in REINFORCE for an episodic problem (by taking the gradient) is the expected return from a given (distribution of) start state:$$J(\theta) = \mathbb{E}_{\pi(\theta)}[G_t|S_t = s_0, t=0]$$Therefore, during the episode, when you sample the ... 8 Recent actor-critic algorithms do use \lambda-returns, but they are disguised as something called the Generalized Advantage Estimator defined as A^{GAE}_t = \sum_{i=0}^{\infty} (\gamma\lambda)^i \delta_{t+i} where \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t). This turns out to be identically equal to [G^\lambda_t - V(s_t)], i.e. the \lambda-return ... 7 I faced a similar issue recently with Minesweeper. The way I solved it was by ignoring the illegal/invalid moves entirely. Use the Q-network to predict the Q-values for all of your actions (valid and invalid) Pre-process the Q-values by setting all of the invalid moves to a Q-value of zero/negative number (depends on your scenario) Use a policy of your ... 6 IMHO the idea of invalid moves is itself invalid. Imagine placing an "X" at coordinates (9, 9). You could consider it to be an invalid move and give it a negative reward. Absurd? Sure! But in fact your invalid moves are just a relic of the representation (which itself is straightforward and fine). The best treatment of them is to exclude them completely ... 6 The first part of this answer is a little background that might bolster your intuition for what's going on. The second part is the more practical and direct answer to your question. The gradient is just the generalization of the derivative to multivariable functions. The gradient of a function at a certain point is a vector that points in the direction of ... 6 Neil's answer already provides some intuition as to why the pseudocode (with the extra \gamma^t term) is correct. I'd just like to additionally clarify that you do not seem to be misunderstanding anything, Equation (13.6) in the book is indeed different from the pseudocode. Now, I don't have the edition of the book that you mentioned right here, but I ... 5 MDPs are strict generalisations of contextual bandits, adding time steps and state transitions, plus the concept of return as a measure of agent performance. Therefore, methods used in RL to solve MDPs will work to solve contextual bandits. You can either treat a contextual bandit as a series of 1-step episodes (with start state chosen randomly), or as a ... 4 My first question is whether the following "implementation" of the 𝑇𝐷(0) algorithm for the first two of the above observed trajectories correct? V(a)\leftarrow0 + 0.1(1+0-0)= 0.1; \quad V(b)\leftarrow0+0.1(1+0-0)=0.1 V(b)\leftarrow0.1+(0.1)(1+0-0.1)= 0.19 Your calculations for the first trajectory (A,1,B,0) is incorrect for either TD or ... 4 The key to REINFORCE working is the way the parameters are shifted towards G \nabla \log \pi(a|s, \theta). Note that  \nabla \log \pi(a|s, \theta) = \frac{ \nabla \pi(a|s, \theta)}{\pi(a|s, \theta)}. This makes the update quite intuitive - the numerator shifts the parameters in the direction that gives the highest increase in probability that the action ... 3 The loss function you are looking for is cross entropy loss. The 'label' that you use is the action you took at the time point you are updating for. 3 It's a subtle issue. If you look at the A3C algorithm in the original paper (p.4 and appendix S3 for pseudo-code), their actor-critic algorithm (same algorithm both episodic and continuing problems) is off by a factor of gamma relative to the actor-critic pseudo-code for episodic problems in the Sutton and Barto book (p.332 of January 2019 edition of http://... 3 How does the neural network learn to differentiate between good and bad actions? Good actions - in context of a given state - have higher return than bad actions on average, taken over many examples where the actions occur in different combinations. In REINFORCE, when training the neural network, all actions are effectively treated as ground truth "... 2 An experimental paper exist in arxiv about the effect of whether to mask or to give negative rewards to invalid actions. There are some references in this paper which also discuss the effects and the mechanism to handle invalid actions. However, those main references are still only pre-prints in the arxiv (not published and presumably not peer-reviewed yet). ... 2 You cannot do this: \mathop{\mathbb{E}_\pi }[r(\tau )\bigtriangledown log \pi (\tau )] \\= \mathop{\mathbb{E}_\pi }[r(\tau )] \,\, \mathop{\mathbb{E}_\pi }[\bigtriangledown log \pi (\tau )] That is because r(\tau ) and \bigtriangledown log \pi (\tau ) are correlated by their dependence on \tau. In a simpler concrete example, if your expectation ... 2 Hi Seewoo Lee and welcome to our community! The essence of your observation is that Sutton's version of REINFORCE is taking into consideration all of the trajectory to compute the returns while in the pytorch version only the future is taken into consideration, hence going in reverse to sum the future rewards and ignore the previous rewards. The consequence ... 2 About the first question, you are right. The i denotes a sample trajectory corresponding to a whole episode. However, Sutton's version is exactly the same one as Levine's if you choose N=1. About the second question, the Policy Gradient theorem only tells you what is the gradient up to a constant, so basically any constant is irrelevant. Now, even if ... 2 First let us note the definition of the advantage function:$$A(s,a) = Q(s,a) - V(s) \; ,$$where Q(s,a) is the action-value function and V(s) is the state-value function. In theory you could represent these by two different function approximators, but this would be quite inefficient. However, note that$$Q(s,a) = \sum_{s',r} \mathbb{P}(s',r|s,a)(r + ...

2

If you take a look at the Wikipedia page related to the normal distribution, you will see the definition of the Gaussian density $${\displaystyle f(x)={\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-{\frac {1}{2}}\left({\frac {x-\mu }{\sigma }}\right)^{2}}} \label{1}\tag{1}$$ and you will see that the $y$ in your formula corresponds to the $x$ in equation \ref{1}. ...

2

First of all you made a mistake, equation 8 in the paper is defined with $\frac{\partial L(\theta)}{\partial s_t}$ not $\frac{\partial L(\theta)}{\partial\theta}$. Loss is defined as: $L(\theta) = - \mathbb{E}_{w^s \sim p_{\theta}}[r(w^s)]$ If we use definition of expectation (for discrete case): $\mathbb{E}[X] = \sum\limits_{i} p_i(x_i)x_i$ we get ...

2

The policy gradient states that $$\nabla J(\theta) \propto \sum_s \mu(s) \sum_a q_\pi(s, a) \nabla\pi(a | s; \theta)\;$$ where the derivatives are taken wrt the parameter $\theta$. Now, if we say incorporate a baseline we get $$\nabla J(\theta) \propto \sum_s \mu(s) \sum_a \left( q_\pi(s, a) - b(s) \right)\nabla\pi(a | s; \theta)\;$$ and this does not effect ...

2

You sample according to the probability distribution $\pi(a \mid s, \theta)$, so you do not always take the action with the highest probability (otherwise there would be no exploration but just exploitation), but the most probable action should be sampled the most. However, keep in mind that the policy, $\theta$, changes, so also the probability distribution....

1

They are not maximizing the gradient, the gradient is of the form $$\nabla_{\theta} J \approx \sum_{t=0}^T G_t \nabla_{\theta} \log(\pi_{\theta}(a_t|s_t))$$ that means that when implementing it in software you can form your objective as $$J = \sum_{t=0}^T G_t \log(\pi_{\theta}(a_t|s_t))$$ and then ...

1

When the authors write go from $$\nabla_{\theta}J \propto \sum_s \mu(s) \sum_a q_{\pi}(s,a)\nabla_{\theta}\pi(a|s;\theta)\;$$ to $$\nabla_{\theta}J = E_{\pi}\left[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t;\theta)\right]\;$$ they are simply taking an expectation where the only random variable is the state $S_t$. This is because, as they say in the book, ...

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

1