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

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


13

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

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


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


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


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

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


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

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


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

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


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


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

Let me first say that deep RL is just the combination of RL with deep learning. So, if you study RL and deep learning, then studying deep RL should be straightforward. For this reason, this answer will point the reader to potentially useful courses on RL (also because there aren't many free courses completely dedicated to deep RL), which have at least one ...


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

Short answer The Q values are updated using a greedy policy because, in the Q-learning algorithm, the $\max$ operator is used to determine the target, which is denoted by $$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$$ Intuitively, the $\max$ operator is used because we assume that the target policy (the policy associated with the ...


5

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


5

For the programming part I suggest this YouTube channel by Phil Tabor (he also has a website: neuralnet.ai. I found his videos really useful while I was attending reinforcement learning classes at the uni. He covers basic algorithms like value iteration and policy iteration and also more advanced like deep q learning, covering all main python libraries (...


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 you can maintain a table lookup that maintains your current estimate ...


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


5

Q-learning is guaranteed to converge (in the tabular case) under some mild conditions, one of which is that in the limit we visit each state-action tuple infinitely many times. If your random random policy (i.e. 100% exploration) is guaranteeing this and the other conditions are met (which they probably are) then Q-learning will converge. The reason that ...


4

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


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

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


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