# Tag Info

36

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

14

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

12

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 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 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 ... 8 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 In order for the algorithm to have stable behavior, the replay buffer should be large enough to contain a wide range of experiences, but it may not always be good to keep everything. The larger the experience replay, the less likely you will sample correlated elements, hence the more stable the training of the NN will be. However, a large experience replay ... 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 ... 7 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 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 ... 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 ... 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 ... 5 You need to read this 2020 paper by Deepmind: "Revisiting Fundamentals of Experience Replay" Also, to add to the answer by @nbro Assume you implement experience replay as a buffer where the newest memory is stored instead of the oldest. Then, if your buffer contains 100k entries, any memory will remain there for exactly 100k iterations. Such a ... 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 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 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 \begin{equation} h(s, a, \theta) = \theta^T \phi(s,a) \end{equation} and softmax policy \... 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 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 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 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

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

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

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

4

I don't think that (at least from a practical standpoint), there is much difference between continuous action space and discrete action space with >2k discrete actions. Quoting the "Continuous control with Deep RL" paper - which I'd recommend as a starting point for your investigation: An obvious approach to adapting deep reinforcement learning ...

3

A stateless RL problem can be reduced to a Multiarmed Bandit (MAB) problem. In such a scenario, taking an action will not change the state of the agent. So, this is the setting of a conventional MAB problem: at each time step, the agent selects an action to either perform an exploration or exploitation move. It then records the reward of the taken action ...

3

As far as I understood, most RL applications have much more states than there are actions to choose from. Yes, this is quite common, but in no way required by the underlying theory of Markov Decision Processes (MDPs). The most extreme version of the opposite thing - with one state (or effectively no state, as state is not relevant) - are k-armed bandit ...

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