28

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


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


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

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

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


6

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

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

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


5

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


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


4

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


4

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


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

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

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


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

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

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

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


3

Usually it is assumed that there is no correlation between different actions, so the covariance matrix will be zero everywhere except on the main diagonal. Diagonal will represent variances of actions. Diagonal covariance matrix will be positive semidefinite if all values on diagonal are $\geq$ 0 so you need to insure that output of final layer is $\geq$ 0, ...


3

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


3

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


3

Softmax policy $\pi_\theta(s,a)$ is defined as $\frac{\exp{(\phi(s,a)^T \theta})}{\Sigma \exp{(\phi(s,a) ^T \theta) }}$, where the summation is over the action space. Taking log, this becomes $$ \log \pi_\theta(s,a) = log(e^{\phi(s,a) ^T \theta}) - log({\Sigma e^{\phi(s,a) ^T \theta }}) \\ = \phi(s,a) ^T \theta - log({\Sigma e^{\phi(s,a)^T \theta }}) $$ ...


3

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


3

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


3

The reason you are confused is because this is not the full derivation of the Policy Gradient Theorem. You are correct in thinking that $\mu(s)$ depends on the policy $\pi$ which in turn depends on the policy parameters $\theta$, and so there should be a derivative of $\mu$ wrt $\theta$, however the Policy Gradient Theorem doesn't require you to take this ...


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.


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