8 votes
Accepted

How to show temporal difference methods converge to MLE?

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 ...
nbro's user avatar
  • 40.4k
6 votes

What is convergence in machine learning?

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 ...
ashenoy's user avatar
  • 1,409
6 votes
Accepted

Deep Q-Learning poor convergence on Stochastic Environment

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 ...
Dennis Soemers's user avatar
  • 10.3k
6 votes
Accepted

What are the conditions of convergence of temporal-difference learning?

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 ...
nbro's user avatar
  • 40.4k
6 votes
Accepted

What is curriculum learning in reinforcement learning?

Curriculum learning is a general technique for deep learning, which got recently applied to also deep reinforcement learning. It's about designing tasks to guide the learning process of the network ...
Luca Anzalone's user avatar
5 votes

Why can the Bellman equation be turned into an update rule?

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 ...
nbro's user avatar
  • 40.4k
5 votes
Accepted

How can I ensure convergence of DDQN, if the true Q-values for different actions in the same state are very close?

Let $Q^*(s, a)$ denote the "true" $Q$-value for a state-action pair $(s, a)$, i.e. the values that we're hoping to learn to approximate using a neural network that outputs $Q(s, a)$ values. The ...
Dennis Soemers's user avatar
  • 10.3k
5 votes
Accepted

If deep Q-learning starts to choose only one action, is this a sign that the algorithm diverged?

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 ...
Neil Slater's user avatar
  • 31.8k
5 votes
Accepted

When do SARSA and Q-Learning converge to optimal Q values?

The true answers are 1 and 3. 1 is true 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 ...
David's user avatar
  • 4,790
5 votes
Accepted

If $\alpha$ decreases over time, why is Q-learning guaranteed to converge?

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 ...
Neil Slater's user avatar
  • 31.8k
5 votes
Accepted

Why does Q-learning converge under 100% exploration rate?

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 ...
David's user avatar
  • 4,790
5 votes

What is curriculum learning in reinforcement learning?

Curriculum learning is a training strategy in the context of DRL and other machine learning methods that involves organizing the learning process in a way that gradually increases the complexity of ...
Hans-Peter Schrei's user avatar
4 votes

Is there a rigorous proof for finding Hopfield minima?

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 ...
nbro's user avatar
  • 40.4k
4 votes
Accepted

How fast does Monte Carlo tree search converge?

Yes, Monte Carlo tree search (MCTS) has been proven to converge to optimal solutions, under assumptions of infinite memory and computation time. That is, at least for the case of perfect-information, ...
Dennis Soemers's user avatar
  • 10.3k
4 votes
Accepted

Is there an advantage in decaying $\epsilon$ during Q-Learning?

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 ...
Neil Slater's user avatar
  • 31.8k
4 votes

How to determine if Q-learning has converged in practice?

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 ...
nbro's user avatar
  • 40.4k
4 votes

Learning an identity function with convolutional networks

Learning the identity function is not trivial at all. The main reason is that the identity function is linear, and a neural network try to approximate it in a non linear fashion. Non linear ...
Edoardo Guerriero's user avatar
3 votes

Is there a simple proof of the convergence of TD(0)?

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 (...
nbro's user avatar
  • 40.4k
3 votes

How is the actor-critic algorithm guaranteed to converge?

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 ...
nbro's user avatar
  • 40.4k
3 votes
Accepted

LSTM network doesn't converge, what should be changed?

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 ...
Fabian's user avatar
  • 146
3 votes
Accepted

Is a calculus or ML approach to varying learning rate as a function of loss and epoch been investigated?

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), ...
Neil Slater's user avatar
  • 31.8k
3 votes

What is convergence analysis, and why is it needed in reinforcement learning?

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 ...
harwiltz's user avatar
  • 1,126
3 votes

Does the policy iteration convergence hold for finite-horizon MDP?

In the discussion about Neil Slater's answer (that he, sadly, deleted) it was pointed out that the policy $\pi$ should also depend on the horizon $h$. The decision of action $a$ can be influenced by ...
Kostya's user avatar
  • 2,515
3 votes

Does elitism cause premature convergence in genetic algorithms?

There are many ideas to escape from local optima in GA. One solution is selecting the population for the next iteration based on the probability that is defined based on the individual score. In that ...
OmG's user avatar
  • 1,816
3 votes
Accepted

Why and how can the policy and value iteration methods converge to the OPTIMAL point?

These two algorithms converge to the optimal value function because they are instances of the generalization policy iteration, so they iteratively perform one policy evaluation (PE) step followed by ...
nbro's user avatar
  • 40.4k
3 votes
Accepted

What is the impact of the initialization of weights in the performance of a neural network in machine learning?

Progress about how to best initialize the weights, is what has made neural networks to be popular again. Initially (around the 80s I think), NNs were initialized from Normal distributions like $\...
Luca Anzalone's user avatar
2 votes

What is chaotic behavior and how it is achieved in non-linear regression and artificial networks?

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 ...
John Doucette's user avatar

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