13

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


11

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


9

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


7

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


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


7

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


7

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


5

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


4

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


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

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


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

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


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


1

this is maybe not a paper but this article is dope. I got 2 link in below to help you understand about policy gradient algorithms especially Reinforce Learning. Both article have a good explanation about that algorithms and not only an explanation, also contain a good example about that. They really put their effort into it so i'm sure if you've read it ...


1

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


1

The advantage is basically a function of the actual return received and a baseline. The function of the baseline is to make sure that only the actions that are better than average receive a positive nudge. One way to estimate the baseline is to have a value function approximator. At every step, you train a NN, using the trajectories collected via the ...


1

In deep reinforcement learning for portfolio optimization, many researchers (Xiong at al. for example) use historical market data for model training. The resulting MDP dynamics is of course completely deterministic (if historical prices are used as states) and there's no real sequentiality involved. Whilst I cannot comment on the specific financial model, I ...


1

REINFORCE is called a gradient estimator because it doesn't work on the true gradient, that comes from a loss function and the whole data, but makes up a heuristic loss, so that the gradient it ends up with isn't the true one. Let's see that with the REINFORCE equation: $$ {\huge \Delta \mathbf{\theta}_t = \alpha \nabla_{\mathbf{\theta}} \log \pi_{\mathbf{\...


1

Reinforcement Learning experiments are empirical and you want to be able to reproduce your experiments. Random numbers are generated off a seed; with the seed function you are fixing the seed so the RNG function produces the same sequence of random numbers.


Only top voted, non community-wiki answers of a minimum length are eligible