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


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


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

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

The update form $\theta^{\prime} \leftarrow \tau \theta+(1-\tau) \theta^{\prime}$ (where $\theta'$ and $\theta$ represent the weights of the target network and the current network, respectively) does exist and is correct. It is called soft update and it has been used in the Deep Deterministic Policy Gradient (DDPG) paper, which uses the concept of a target ...


4

The true answers are 1 and 3. 1 because the required conditions for tabular Q-learning to converge is that each state action pair will be visited infinitely often, and Q-learning learns directly about the greedy policy, $\pi(a|s) := \arg \max_a Q_\pi(s,a)$, and because Q-learning converges to the optimal Q-value function we know that the policy will be ...


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


4

This post contains many answers that describe the difference between on-policy vs. off-policy. Your book may be referring to how the current (DQN-based) state-of-the-art (SOTA) algorithms, such as Ape-X, R2D2, Agent57 are technically "off-policy", since they use a (very large!) replay buffer, often filled in a distributed manner. This has a number ...


4

I know this might be specific to different problems but does anyone know if there is any rule of thumb or references on what constitutes a large state space? Not really, it is all relative. There are two main ways in which the scale of a value table might be too much: Memory required to represent the table. This is relatively simple to calculate for any ...


4

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


3

Is this a sign that the algorithm diverged? It is a common sign of a problem with learning process. That includes divergence due to poor hyper-parameters, even just bad luck. But it can also point to a design/architecture problem. Other common causes of algorithm failing with a fixed action choice include: Neural network inputs not scaled before use. ...


3

In Tabular Q-learning the update is as follows $$Q(s,a) = Q(s,a) + \alpha \left[R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a) \right]\;.$$ Now, as we are interested in learning about the optimal policy, this would correspond to the $\max_aQ(s',a)$ term in the TD target because that is how the optimal policy chooses its actions - i.e. $\pi_*(a|s) = \arg\max_aQ_*(...


3

You should first read the introductory paper of Double DQN. https://arxiv.org/abs/1509.06461 Then, depending on what you would like to do, search for other relevant papers that use this method.


3

Removing the learning rate will likely yield poor convergence to the optimal policy and optimal Q-values. Note that the current policy is completely dependent on the Q-values, as we take the action with highest Q-value in a given state (with a few other considerations such as exploration, etc.). If we were to remove the learning rate, then we are making a ...


3

The primary issue I see is that in the loop through time steps t in every training episode, you select actions for both players (who should have opposing goals to each other), but update a single q_table (which can only ever be correct for the "perspective" of one of your two players) on both of those actions, and updating both of them using a ...


3

Convergence analysis is about proving that your policy and/or value function converge to some desired value, which is usually the fixed-point of an operator or an extremum. So it essentially proves that theoretically the algorithm achieves the desired function. Without convergence, we have no guarantees that the value function will be accurate or the policy ...


3

I don't think people generally do use neural nets for grid world. As long as the state and action spaces are small enough, you should be able to store Q values in a table like you suggested. Neural nets come in handy when the state space is very large (or even continuous), so you can't afford to store a table of Q values. Also, neural nets have the ability ...


3

You would still be picking a single action. Your action space is now $\mathcal{A} = \mathcal{O} \times \mathcal{I}$ where I've chosen $\mathcal{O}$ to be the set of possible orders from your problem and $\mathcal{I}$ to be the set of possible items. Provided both of these sets are finite, then you should still be able to approach this problem with DQN. ...


3

You are referring to catastrophic forgetting which could be an issue in any neural net. More specifically for DQN refer to this article.


3

I am using the convention of uppercase $X$ for random variable and lowercase $x$ for an individual observation. It is possible your source material did not do this, which might be causing your confusion. However, it is the convention used in Sutton & Barto's Reinforcement Learning: An Introduction. What I didn't understand what is 𝑋 here. i.e., what is ...


3

The overestimation comes from the random initialisation of your Q-value estimates. Obviously these will not be perfect (if they were then we wouldn't need to learn the true Q-values!). In many value based reinforcement learning methods such as SARSA or Q-learning the algorithms involve a $\max$ operator in the construction of the target policy. The most ...


3

I will first explain briefly to you the difference between supervised learning and reinforcement learning to make sure that you don't have any misunderstandings. In supervised learning you are provided with some data $\{(\textbf{x}_i, y_i)\}_{i=1}^n$ where $\textbf{x}_i$ are the features for data point $i$ and $y_i$ is its true label. Now, the aim of ...


3

A Q table allows you to look up any state/action pair in it and find the associated action value. It is not itself a policy. However, in order to calculate the action values, you will have assumed something about the policy. The most common policy scenarios with Q learning are that it will converge on (learn) the values associated with a given target policy, ...


3

As you say, the output of a $Q$ network is typically a value for all actions of the given state. Let us call this output $\mathbf{x} \in \mathbb{R}^{|\mathcal{A}|}$. To train your network using the squared bellman error you need first calculate the scalar target $y = r(s, a) + \max_a Q(s', a)$. Then, to train the network we take a vector $\mathbf{x'} = \...


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