# Tag Info

25

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

15

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

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

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

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

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

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

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

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 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 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 ... 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. 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 How does Q learning handle this? Is the Q function only used during the training process, where the future states are known? And is the Q function still used afterwards, if that is the case? The learned$Q$-function is not only used during training, but also after training (in what we may call "deployment", when we expect a trained agent to behave according ... 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 ...

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