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


16

Q-learning and A* can both be viewed as search algorithms, but, apart from that, they are not very similar. Q-learning is a reinforcement learning algorithm, i.e. an algorithm that attempts to find a policy or, more precisely, value function (from which the policy can be derived) by taking stochastic moves (or actions) with some policy (which is different ...


12

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


12

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


10

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


9

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


9

Here is a table that attempts to systematically show the differences between tabular Q-learning (TQL), deep Q-learning (DQL), and deep Q-network (DQN). Tabular Q-learning (TQL) Deep Q-learning (DQL) Deep Q-network (DQN) Is it an RL algorithm? Yes Yes No (unless you use DQN to refer to DQL, which is done often!) Does it use neural networks? No. It uses a ...


8

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


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


7

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


7

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


7

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


7

If we write the pseudo-code for the SARSA algorithm we first initialise our hyper-parameters etc. and then initialise $S_t$, which we use to choose $A_t$ from our policy $\pi(a|s)$. Then for each $t$ in the episode we do the following: Take action $A_t$ and observe $R_{t+1}$, $S_{t+1}$ Choose $A_{t+1}$ using $S_{t+1}$ in our policy $Q(S_t, A_t) = Q(S_t, A_t)...


6

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


6

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

1) Is there any way to set the initial Q-values for the actions? You can generally do this, but you cannot specify specific weights for specific actions in specific states. Not through the network weights directly, at least. That would defeat the purpose of using backpropagation to optimize the weights and find the optimal parameters and Q-values. 2) Is ...


5

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


5

This answer will point the reader to potentially useful resources, but I can't ensure that the courses are good (because I have never followed them). Free Reinforcement Learning in the Open AI Gym (a small course that you can find in the YouTube channel suggested in the other answer) by Phil Tabor The free course Advanced Deep Learning & Reinforcement ...


5

If you're interested in the theory behind Double Q-learning (not deep!), the reference paper would be Double Q-learning by Hado van Hasselt (2010). As for Double deep Q-learning (also called DDQN, short for Double Deep Q-networks), the reference paper would be Deep Reinforcement Learning with Double Q-learning by Van Hasselt et al. (2016), as pointed out ...


5

Why is this a convergence criterion? It is because $R$ and $S'$ are stochastic. A large learning rate applied when these values have variance would not converge to mean, but would wander around typically within some value proportional to $\alpha\sigma$ of the true value, where $\sigma$ is the standard deviation of the term $R + \gamma\text{max}_aQ(S',a)$. ...


5

In Q-learning (and in general value based reinforcement learning) we are typically interested in learning a Q-function, $Q(s, a)$. This is defined as $$Q(s, a) = \mathbb{E}_\pi\left[ G_t | S_t = s, A_t = a \right]\;.$$ For tabular Q-learning, where you have a finite state and action space - note that in practice even the spaces being finite might not be ...


5

If your algorithm is executed multiple (or enough) times using an outer loop, it would converge to similar results as Q-learning would with $\gamma = 0$ (as you don't look what is the expected future reward). In this case, the difference is that you would pass as much time to explore each possible couple of (state, action) while Q-learning would pass more ...


5

I'm using OpenAI's cartpole environment. First of all, is this environment not Markov? The OpenAI Gym CartPole environment is Markov. Whether or not you know the transition probabilities does not affect whether the state has the Markov property. All that matters is that knowing the current state is enough to be determine the next state and reward in ...


4

In a two player zero-sum game (if I win, you lose and vice-versa), then you can have a simple and efficient solution learning from self-play. How should an opponent be implemented to get good and fast improvements? You don't need to think in terms of agent vs opponent, instead think in terms of coding both the players' goals into a single Q function. ...


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

Usually when people write about having a high-dimensional state space, they are referring to the state space actually used by the algorithm. Suppose my state is a high dimensional vector of $N$ length where $N$ is a huge number. Let's say I solve this task using $Q$-learning and I fix my state space to $10$ vectors each of $N$ dimensions. $Q$-learning can ...


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

I think this was just a "clever" design choice. You can actually design a neural network (NN), to represent your Q function, which receives as input the state and an action and outputs the corresponding Q value. However, to obtain $\max_aQ(s', a)$ (which is a term of the update rule of the Q-learning algorithm) you would need a "forward pass" of this network ...


4

After some research and reading this post, I see where my problem was: I was introducing a full consecutive batch of experiences, selected randomly, yes, but the experiences in the batch were consecutives. After redoing my experience selection method, my DQN is actually working and has reached about +200 points after 400000 experiences (about 500 episodes; ...


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