# Tag Info

6

The convergence and optimality proofs of (linear) temporal-difference methods (under batch training, so not online learning) can be found in the paper Learning to predict by the methods of temporal differences (1988) by Richard Sutton, specifically section 4 (p. 23). In this paper, Sutton uses a different notation than the notation used in the famous book ...

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

4

When formulating a problem in deep learning, we need to come up with a loss function, which uses model weights as parameters. Back-propagation starts at an arbitrary point on the error manifold defined by the loss function and with every iteration intends to move closer to a point that minimises error value by updating the weights. Essentially for every ...

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

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

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

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

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

There are different TD algorithms, e.g. Q-learning and SARSA, whose convergence properties have been studied separately (in many cases). In some convergence proofs, e.g. in the paper Convergence of Q-learning: A Simple Proof (by Francisco S. Melo), the required conditions for Q-learning to converge (in probability) are the Robbins-Monro conditions $\sum_{... 3 Why are we allowed to convert the Bellman equations into update rules? There is a simple reason for this: convergence. The same chapter 4 of the same book mentions it. For example, in the case of policy evaluation, the produced sequence of estimates$\{v_k\}$is guaranteed to converge to$v_\pi$as$k$(i.e. the number of iterations) goes to infinity. There ... 3 writing here my suggestion, because i haven't earned the right to comment yet. Your main "problem" could be your loss function. It converges, this is why your loss value is decreasing. So I suggest to let it maybe train longer. Alternatively you could change the loss function to fit your need. For example you could use: loss = tf.reduce_mean(tf.square(... 3 The inputs that you describe seem like they should be sufficient for a DQN-based agent to learn a good strategy for playing Minesweeper, regardless of whether or not the starting layout changes. The inputs contain all information that is necessary. However, the problem certainly becomes much easier (probably too easy) if the initial problem is always the ... 3 Has this been done? Difficult to prove a negative, but I suspect although plenty of research has been done into finding ideal learning rate values (the need for learning rate at all is an annoyance), it has not been done to the level of suggesting a global function worth approximating. The problem is that learning rate tuning, like other hyperparameter ... 2 It looks like you have some common misconceptions about AI and neural networks. First, AI programs generally do not try to imitate the human behaviour of a human brain. Instead, they try to imitate some higher-level behaviour. For example, they might imitate the reasoning process that you go through when you make a plan. In this context, the building-blocks ... 2 Which is more important, doubt or reinforcement? The single-sentence answer to this would be: it depends. The core of this question seems to be very closely related to the well-known trade-off between exploration (similar to how you describe "doubt") and exploitation (similar to how you describe "reinforcement"). It is almost never the case that someone ... 2 There are different actor-critic (AC) algorithms with different convergence guarantees. For example, AC algorithms where the critic is tabular have different convergence guarantees than AC algorithms where the critic is a neural network (function approximation). Most convergence proofs assume that the actor and the critic operate at different time scales, ... 2 See the paper On the Convergence Properties of the Hopfield Model (1990), by Jehoshua Bruck. In the first section of the paper, J. Bruck describes the Hopfield network (popularized by J. J. Hopfield in 1982 in his paper Neural networks and physical systems with emergent collective computational abilities, hence the name of the network), then he describes ... 2 As far as I know, there is no very simple proof of the convergence of temporal-difference algorithms. The proofs of convergence of TD algorithms are often based on stochastic approximation theory (given that e.g. Q-learning can be viewed as a stochastic process) and the work by Robbins and Monro (in fact, the Robbins-Monro conditions are usually assumed in ... 2 It is not so much the problem of using Reinforcement Learning to train the neural networks, it is the assumptions made about the data given to standard Neural Networks. They are not capable of handling strongly correlated data which is one of the motivations for introducing Recurrent Neural Networks, as they can handle this correlated data well. 2 Yes, it is possible to use deep learning architecture with Apache Spark now. Databricks have Spark-deep-learning which is a pipeline based in python and uses tensorflow and keras. https://github.com/databricks/spark-deep-learning You can check this. There is also BigDL by Intel analytics. https://github.com/intel-analytics/BigDL 2 The issue is that in your list comprehension in def V_pi(state) you have return sum(prob * (reward + mdp.discount*V[newState]) for prob, reward, newState in mdp.succProbReward(state)) whereas with the way you have defined the succProbReward output, it should be return sum(prob * (reward + mdp.discount*V[newState]) for newState, prob, reward in ... 2 Here is the commit I fixed few minor errors, but the major one was when I saw what the line histories = [deque(maxlen=self.reward_steps)] * len(self.env.envs) was doing. It was just repeating the same queue. In [2]: histories = [deque(maxlen=5)] * 4 In [3]: histories ... 2 Why do RL implementations converge on one action? If the optimal policy shouldn't always select the same action in the same state, i.e., if the optimal policy isn't deterministic (e.g., in the case of the rock paper scissors, the optimal policy cannot be deterministic because any intelligent player would easily memorize your deterministic policy, so, after ... 2 If anything, you want the learning rate to decrease as the number of iterations increases. When you're looking for a good spot and you're clueless, take large steps. When you've found a pretty good spot, take small steps, so you don't end up far away. In other fields of machine learning, there are studies of how the learning rate should scale. For example, ... 1 It seems like you're suffering from the the dying ReLU problem. ReLU enforces positive values so the weights and biases your network learned are leading to a negative value passed through the ReLU function - meaning you would get 0. There are a few things you can do. I do not know the exact format of your data, but if it is MNIST it is possible you simply ... 1 Yes Q-learning benefits from decaying epsilon in at least two ways: Early exploration. It makes little sense to follow whatever policy is implied by the initialised network closely, and more will be learned about variation in the environment by starting with a random policy. It is fairly common in DQN to initially fill the experience replay table whilst ... 1 The paper Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms by Satinder Singh et al. proves that SARSA(0), in the case of a tabular representation of the value functions, converges to the optimal value function, provided certain assumptions are met Infinite visits to every state-action pair The learning policy becomes greedy ... 1 I have the conditions for convergence in these notes SARSA convergence by Nahum Shimkin. The Robbins-Monro conditions above hold for$α_t$. Every state-action pair is visited infinitely often The policy is greedy with respect to the policy derived from$Q\$ in the limit The controlled Markov chain is communicating: every state can be reached from any other ...

1

The paper Convergence of Q-learning: A Simple Proof (by Francisco S. Melo) shows (theorem 1) that Q-learning, a TD(0) algorithm, converges with probability 1 to the optimal Q-function as long as the Robbins-Monro conditions, for all combinations of states and actions, are satisfied. In other words, the Robbins-Monro conditions are sufficient for Q-learning ...

1

Apparently there is an example of non-convergence for semi-gradient sarsa, according to Rich Sutton (check slide 35). I guess TD(0) is not so different. So, probably your approximator will need to satisfy certain conditions to proof convergence. Maybe this paper will be useful for you. It seems that they show that constraining your network to have relu ...

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