Tag Info

19

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

9

My best guess that it's been done to reduce the computation time, otherwise we would have to find out the q value for each action and then select the best one. It has no real impact on computation time, other than a slight increase (due to extra memory used by two networks). You could cache results of the target network I suppose, but it probably would not ...

8

That's the Expected Value operator. Intuitively, it gives you the value that you would "expect" ("on average") the expression after it (often in square or other brackets) to have. Typically that expression involves some random variables, which means that there may be a wide range of different values the expression may take in any concrete, single event. ...

7

Here's an intuitive description answer: Function approximation can be done with any parameterizable function. Consider the problem of a $Q(s,a)$ space where $s$ is the positive reals, $a$ is $0$ or $1$, and the true Q-function is $Q(s, 0) = s^2$, and $Q(s, 1)= 2s^2$, for all states. If your function approximator is $Q(s, a) = m*s + n*a + b$, there exists no ...

6

Tabular Q-Learning does not explicitly create a model of the transition function. It does not generate any output that you can afterwards use as a function to predict what the next state s' will be given a current state s and an action a (that's what a transition function would allow you to do). So no, Q-learning is still model-free. By the way, model-based ...

6

The motivation for adding the discount factor $\gamma$ is generally, at least initially, based simply in "theoretical convenience". Ideally, we'd like to define the "objective" of an RL agent as maximizing the sum of all the rewards it gathers; its return, defined as: $$\sum_{t = 0}^{\infty} R_t,$$ where $R_t$ denotes the immediate reward at time $t$. As ...

6

Let's start by looking at: $$\max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert.$$ We can rewrite this by plugging in the definition of $G_{t:t+n}$: \begin{aligned} & \max_s \Bigl\lvert \mathbb{E}_{\pi} \left[ G_{t:t+n} \mid S_t = s \right] - v_{\pi}(s) \Bigr\rvert \\ % =& \max_s \Bigl\lvert \mathbb{...

5

Note: you mentioned in the comments that you are reading the old, pre-print version of the paper describing AlphaZero on arXiv. My answer will be for the "official", peer-reviewed, more recent publication in Science (which nbro linked to in his comment). I'm not only focusing on the official version of the paper just because it is official, but also because ...

5

$\mathbb E$ is the symbol for the expectation (or expected value). To fully understand the concept of expected value, you need to understand the concept of random variable. An example should help you understand the idea behind the concept of a random variable. Suppose you toss a coin. The outcome of this (random) experiment can either be heads or tails. ...

4

To model chess as a Markov decision problem (MDP) you can refer to the AlphaZero paper (Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm). The exact details can be found starting from the bottom of page 13. Briefly, an action is described by picking a piece and then picking a move with it. The size of the board is 8 by ...

4

The exploration rate, typically parameterized as epsilon / ε, can be changed on every trial. It depends on the complexity of the model and the goals. The simplest thing to do is keep exploration rate high and fixed. That means the model will continue to explore new options, even at the cost of not "exploiting" the best available option. Another option is ...

4

I'm going to assume here that you're using the standard, basic, simple variant of $Q$-learning that can be described as tabular $Q$-learning, where all of your state-action pairs for which you're learning $Q(s, a)$ values are represented in a tabular fashion. For example, if you have 4 actions, your $Q(s, a)$ values are likely represented by 4 matrices (...

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

Picking actions and making updates should be treated as separate things. For Q-learning you also need to explore by using some exploration strategy (e.g. $\epsilon$-greedy). Steps for Q-learning: 1) initialize state $S$ For every step of the episode: 2) choose action $A$ by some exploratory policy (e.g. $\epsilon$-greedy) from state $S$ 3) take action $A$ ...

4

As far as I'm aware, it is still somewhat of an open problem to get a really clear, formal understanding of exactly why / when we get a lack of convergence -- or, worse, sometimes a danger of divergence. It is typically attributed to the "deadly triad" (see 11.3 of the second edition of Sutton and Barto's book), the combination of: Function approximation, ...

3

1): The intuition is based on the concept of value iteration, which the authors mention but don't explain on page 504. The basic idea is this: imagine you knew the value of starting in state x and executing an optimal policy for n timesteps, for every state x. If you wanted to know the optimal policy (and it's value) for running for n+1 timesteps in each ...

3

Does it have to do with the reward function? This seems likely to me. You have chosen a reward that is unusual in that it cross-links episodes. It is not really a reinforcement problem to optimise behaviour with respect to results of previous episode behaviour in this way. This might be an option for an evolutionary fitness context, if you have competing ...

3

Would it be helpful to use a LSTM and reduce the input state? I'd bet, no. LSTM is more complicated and harder to learn, while the input is 4 * 9 * 36 bits is still rather limited. However, you may want to aggregate the information somehow, e.g., add additional bits informing about what cards were already played (no matter when). This information is ...

3

Your main problem is that you need to separate out what is driving the behaviour policy from the Q-table. Q Learning is an off-policy algorithm. The Q-table that it eventually learns is for an optimal policy (also called the target policy). In order to be able to learn that policy, the agent needs to explore. The usual way to do this is to make the agent ...

3

This is the problem that reinforcement learning (RL) is trying to solve: What is the best way to behave when we don’t know what the right action is and only have a scalar (the reward (r) is a scalar) reward of how well we have done? RL approaches this problem by utilizing temporal difference learning and makes predictions based on the previous experience. ...

3

For normal value iteration, you need to have the model, i.e. the transition probability, denoted by $P(s' \mid s,a)$. With Q-learning, you use the current reward and the already stored Q value: The relation between the value function $V(s)$ and the Q function $Q(s, a)$ is that the $V(s)$ function is simply the value of the action $a$, such that $Q(s, a)$ is ...

3

I think your net should have the various actions as outputs, but I am not an expert in Deep Nets. I just think that that light form of multi-task learning might be better. The idea of multi-task learning is that a predictor predicting multiple variables (in this case the various Q(s,a1), Q(s,a2), ...) using mostly the same structure (varying only the output ...

3

The inputs that you describe seem like they should be sufficient for a DQN-based agent to learn a good strategy for playing Minesweeper, regardless of whether or not the starting layout changes. The inputs contain all information that is necessary. However, the problem certainly becomes much easier (probably too easy) if the initial problem is always the ...

3

For tabular Q-learning, the q-values for state s and action a are updated according to $$Q(s, a) \gets Q(s, a) + \alpha [(r + max_{a'} Q(s', a')) - Q(s,a)]$$ where $\alpha$ is the learning rate and $(r + max_{a'} Q(s', a')) - Q(s,a)$ is the difference between the current estimate of the q-value, $Q(s,a)$, and the target, $r + max_{a'} Q(s', a')$. The ...

3

No, it will not converge in the general case (maybe it might in extremely convenient special cases, not sure, didn't think hard enough about that...). Practically everything in Reinforcement Learning theory (including convergence proofs) relies on the Markov property; the assumption that the current state $s_t$ includes all relevant information, that the ...

3

No, your second statement does not correctly implement the Q-learning update rule, which the first statement correctly implements.

3

It depends on the implementation of the software package that you are using. If you call a function that returns the maximum value and all values are the same then it might return the value at first index or some other one. The point is it doesn't matter which action is chosen since all of them are the best at the same time. So it's basically random but you ...

3

Q-learning for continuous state spaces Yes, this is possible, provided you use some mechanism of approximation. One approach is to discretise the state space, and that doesn't have to reduce the space to a small number of states. Provided you can sample and update enough times, then a few million states is not a major problem. However, with large state ...

3

Including exogenous variables in your state representation certainly can be useful, as long as you expect them to be relevant information for determining the action to pick. So, state features are not only useful if you expect your agent (through application of actions) to have (partial) influence on those state variables; you just want the state variables ...

3

I was able to solve the problem with the help of comment from @NeilSlater. The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of $-0.00005$ on the learning rate lr and subsequently Q-Learning also converged to the same value as value iteration.

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