# Tag Info

39

However, both approaches appear identical to me i.e. predicting the maximum reward for an action (Q-learning) is equivalent to predicting the probability of taking the action directly (PG). Both methods are theoretically driven by the Markov Decision Process construct, and as a result use similar notation and concepts. In addition, in simple solvable ...

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 \... 12 Here is the gradient that they are discussing in the video:$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \left( \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (\mathbf{a}_{i, t} \vert \mathbf{s}_{i, t}) \right) \left( \sum_{t = 1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i, t}) \right)$$In this equation, \pi_{\theta} (\mathbf{a}_{i, t} \vert \... 11 This Tutorial by OpenAI offers a great comparison of different RL methods. I'll try to summarize the differences between Q-Learning and Policy Gradient methods: Objective Function In Q-Learning we learn a Q-function that satisfies the Bellman (Optimality) Equation. This is most often achieved by minimizing the Mean Squared Bellman Error (MSBE) as the loss ... 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 An important thing we're going to need is what is called the "Expected Grad-Log-Prob Lemma here" (proof included on that page), which says that (for any t):$$\mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta}(a_t \mid s_t) \right] = 0.Taking the analytical expression of the gradient (from, for example, slide 9) ... 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 ... 8 As you has said, actions chosen by Actor-Critic typically come from a normal distribution and it is the agent's job to find the appropriate mean and standard deviation based on the the current state. In many cases this one distribution is enough because only 1 continuous action is required. However, as domains such as robotics become more integrated with AI, ... 7 Using the law of iterated expectations one has: \triangledown _\theta \sum_{t=1}^T \mathbb{E}_{(s_t,a_t) \sim p(s_t,a_t)} [b(s_t)] = \nabla_\theta \sum_{t=1}^T \mathbb{E}_{s_t \sim p(s_t)} \left[ \mathbb{E}_{a_t \sim \pi_\theta(a_t | s_t)} \left[ b(s_t) \right]\right] = written with integrals and moving the gradient inside (linearity) you get = \sum_{... 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 The "trick" of subtracting a (state-dependent) baseline from the Q(s, a) term in policy gradients to reduce variants (which is what is described in your "baseline reduction" link) is a different trick from the modifications to the rewards that you are asking about. The baseline subtraction trick for variance reduction does not appear to be present in the ... 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 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 It depends on your loss function, but you probably need to tweak it. If you are using an update rule like loss = -log(probabilities) * reward, then your loss is high when you unexpectedly got a large reward—the policy will update to make that action more likely to realize that gain. Conversely, if you get a negative reward with high probability, this will ... 5 Absolutely, it’s a really interesting problem. Here is a paper detailing off policy actor critic. This is important because this method can also support continuous actions. The general idea of off-policy algorithms is to compare the actions performed by a behaviour policy (which is actually acting in the world) with the actions the target policy (the ... 5 This question is discussed in detail, in the following NeurIPS 2016 paper by David Silver: Learning values across many orders of magnitude. They also give experimental results over the Atari domain. 5 Calculation of gradient \begin{align} \nabla_{\theta} \log(\pi_{\theta}(a|s)) &= \phi(s,a) - \mathbb E[\phi (s, \cdot)]\\ &= \phi(s,a) - \sum_{a'} \pi(a'|s) \phi(s,a') \end{align} is only valid for linear function approximation with action preferences of form $$h(s, a, \theta) = \theta^T \phi(s,a)$$ and softmax policy \... 5 The difference between Vanilla Policy Gradient (VPG) with a baseline as value function and Advantage Actor-Critic (A2C) is very similar to the difference between Monte Carlo Control and SARSA: The value estimates used in updates for VPG are based on full sampled returns, calculated at the end of episodes. The value estimates used in updates for A2C are ... 5 This question is really getting at the meaning of the discount factor in Markov decision processes. There are actually two, equivalent ways of interpreting the discount factor. The first is probably what you're familiar with: the i^{th} step receives a reward of \gamma^{i}r_i instead of just r_i. The second, equivalent interpretation, is that at every ... 4 When using the loss function for the critic described in your question, the Actor-Critic is an on-policy approach (as are most Actor-Critic methods). Your intuition as to what it is learning seems to be quite close, but the notation/terminology is not quite on point. First it's important to realize that the Q(s, a) critic is an estimator, we're training ... 4 The loss function is estimated in every batch training cycle. Gradients of the loss are computed and propagation back to the network happens in every cycle. This means that you use a small batch (e.g. 100 instances) from the replay memory, and by having the states you can input them to the respective network and have the Q(s) for every state in your batch. ... 4 We subtract mean from values and divide it with standard deviation to get data with mean of zero and variance of one. The range of values per episode does not matter, it will always make it to have zero mean and variance of one in all cases. If the range is bigger ([100, 200]) then deviation will be bigger as well than for smaller range ([0, 1]) so we will ... 4 Both implementations may be closer than you think. In short: PPO has both parts: there is noisiness in draws during training (with learned standard deviation), helping to explore new promising actions/policies. And there is a term added to the loss function aiming to prevent a collapse of the noisiness, to help ensure exploration continues and we don't get ... 4 I think what you mean to ask is how can differentiation occur when there's no obvious neural network function to differentiate? Don't worry - lots of people get confused about this, because it seems like an obvious hole in the puzzle. As mentioned by @AtillaOzgur, neural networks use partial differentiation through backpropagation. First, take the output ... 4 First, the derivative is usually taken with respect to a variable (input) of the function. Hence the notation \frac{df}{dx} for some function f(x). If you look at your equation more carefully\nabla log P(\tau^{i};\theta) = \Sigma_{t=0}\nabla_{\theta}log\pi(a_{t}|s_t, \theta). You will see that the gradient is taken with respect to $\theta$, which ...

4

Let's say your old policy is $\pi_b$ and your current one is $\pi_a$. If you collected trajectory by using policy $\pi_b$ you would get return $G$ whose expected value is \begin{align} E_{\pi_b}[G_t|S_t = s] &= E_{\pi_b}[R_{t+1} + G_{t+1}]\\ &= \sum_a \pi_b(a|s) \sum_{s', r} p(s', r|s, a) [r + E_{\pi_b}[G_{t+1}|S_{t+1} = s']]\\ \end{align} You can ...

4

DQN on the other hand, explores using epsilon greedy exploration. Either selecting the best action or a random action. This is a very common choice, because it is simple to implement and quite robust. However, it is not a requirement of DQN. You can use other action choice mechanisms, provided all choices are covered with a non-zero probability of being ...

4

In the policy gradient theorem, we don't need to write $r$ as a function of $a$ because the only time we explicitly 'see' $r$ is when we are taking the expectation with respect to the policy. For the first couple lines of the PG theorem we have \begin{align} \nabla v_\pi(s) &= \nabla \left[ \sum_a \pi(a|s) q_\pi (s,a) \right] \;, \\ &= \sum_a \left[ \...

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

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