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


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


11

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


10

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


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


7

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


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


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


6

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


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

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


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

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


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


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


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

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

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

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


4

TL;DR: It is Q learning. However Q learning is basically sample-based value iteration, so not surprising you see a similarity. Q learning* and value iteration are very strongly related. When considering action values, both approaches use the same Bellman equation for optimal policy, $q^*(s,a) = \sum_{r,s'}p(r,s'|s,a)(r+\gamma \text{max}_{a'} q^*(s', a'))$ ...


4

The way you have described tends to be the common approach. There are of course other ways that you could do this e.g. using an exponential decay, or to only decay after a 'successful' episode, albeit in the latter case I imagine you would want to start with a smaller $\epsilon$ value and then decay by a larger amount.


4

Q-learning is said to be "model-free". Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken? No. That's not why Q-learning is model-free. Q-learning assumes that the underlying environment (FrozenLake or MountainCar, for example) can be modelled as a Markov decision ...


4

A typical and practical way to measure the convergence to some solution (so not necessarily the optimal one!) of any numerical iterative algorithm (such as RL algorithms) is to check if the current solution has not changed (much) with respect to the previous one. In your case, the solutions are value functions, so you could check if your algorithm has ...


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


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