Questions tagged [convergence]

For questions related to the convergence of AI algorithms.

Filter by
Sorted by
Tagged with
7
votes
2answers
7k views

What is convergence in machine learning?

I came across this answer on Quora, but it was pretty sparse. I'm looking for specific meanings in the context of machine learning, but also mathematical and economic notions of the term in general.
7
votes
1answer
179 views

Why does reinforcement learning using a non-linear function approximator diverge when using strongly correlated data as input?

While reading the DQN paper, I found that randomly selecting and learning samples reduced divergence in RL using a non-linear function approximator (e.g a neural network). So, why does Reinforcement ...
6
votes
1answer
637 views

How to show temporal difference methods converge to MLE?

In chapter 6 of Sutton and Barto (p. 128), they claim temporal difference converges to the maximum likelihood estimate (MLE). How can this be shown formally?
6
votes
0answers
175 views

Is the Bellman equation that uses sampling weighted by the Q values (instead of max) a contraction?

It is proved that the Bellman update is a contraction (1). Here is the Bellman update that is used for Q-Learning: $$Q_{t+1}(s, a) = Q_{t}(s, a) + \alpha*(r(s, a, s') + \gamma \max_{a^*} (Q_{t}(s', ...
5
votes
1answer
221 views

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

I am working on this assignment where I made the agent learn state-action values (Q-values) with Q-learning and 100% exploration rate. The environment is the classic gridworld as shown in the ...
5
votes
1answer
569 views

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

In reinforcement learning, temporal difference seem to update the value function in each new iteration of experience absorbed from the environment. What would be the conditions for temporal-...
5
votes
1answer
362 views

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

Most RL books (Sutton & Barto, Bertsekas, etc.) talk about policy iteration for infinite-horizon MDPs. Does the policy iteration convergence hold for finite-horizon MDP? If yes, how can we derive ...
5
votes
1answer
242 views

How to create and train (with mutation and selection) a neural network to predict the next state of a board?

I'm aiming to create a neural network that can learn to predict the next state of a board using the rules of Conway's Game of Life. Technically, I have three questions, but I felt that they needed to ...
5
votes
1answer
51 views

How can we conclude that an optimization algorithm is better than another one

When we test a new optimization algorithm, what the process that we need to do?For example, do we need to run the algorithm several times, and pick a best performance,i.e., in terms of accuracy, f1 ...
4
votes
1answer
388 views

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

Here's another interesting multiple-choice question that puzzles me a bit. In tabular MDPs, if using a decision policy that visits all states an infinite number of times, and in each state, randomly ...
4
votes
2answers
109 views

How does $\alpha$ affect the convergence of the TD algorithm?

In Temporal-Difference Learning, we update our value function by $V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$ If we ...
4
votes
1answer
45 views

Does elitism cause premature convergence in genetic algorithms?

I have a genetic algorithm which is working fairly well. It's got all the standard operators, including initial random population, crossover ratio, mutation rate, degree of mutation, etc. This works ...
4
votes
1answer
222 views

Convergence of semi-gradient TD(0) with non-linear function approximation

I am looking for a result that shows the convergence of semi-gradient TD(0) algorithm with non-linear function approximation for on-policy prediction. Specifically, the update equation is given by (...
4
votes
1answer
311 views

When exactly is a model considered over-parameterized?

When exactly is a model considered over-parameterized? There are some recent researches in Deep Learning about the role of over-parameterization toward generalization, so it would be nice if I can ...
4
votes
1answer
106 views

REINFORCE algorithm for portfolio optimization - problem while training

I'm trying to implement the Reinforce algorithm (Monte Carlo policy gradient) in order to optimize a portfolio of 94 stocks on a daily basis (I have suitable historical data to achieve this). The idea ...
3
votes
1answer
409 views

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

I am using Q-learning and SARSA to solve a problem. The agent learns to go from the start to the goal without falling in the holes. At each state, I can choose the action corresponding to the maximum ...
3
votes
3answers
315 views

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

In chapter 4.1 of Sutton's book, the Bellman equation is turned into an update rule by simply changing the indices of it. How is it mathematically justified? I didn't quite get the initiation of why ...
3
votes
1answer
898 views

Deep Q-Learning poor convergence on Stochastic Environment

I'm trying to implement a Deep Q-network in Keras/TF that learns to play Minesweeper (our stochastic environment). I have noticed that the agent learns to play the game pretty well with both small and ...
3
votes
1answer
34 views

How much can an inclusion of the number of iterations have on the training of an MLP?

My doubt is like this : Suppose we have an MLP. In an MLP, as per the backprop algorithm (back-propagation algorithm), the correction applied to each weight is : $$ w_{ij} := -\eta\frac{\partial E}{\...
3
votes
1answer
339 views

Why do RL implementations converge on one action?

I have seen this happening in implementations of state-of-the-art RL algorithms where the model converges to a single action over time after multiple training iterations. Are there some general ...
3
votes
1answer
246 views

Neural network doesn't seem to converge with ReLU but it does with Sigmoid?

I'm not really sure if this is the sort of question to ask on here, since it is less of a general question about AI and more about the coding of it, however I thought it wouldn't fit on stack overflow....
3
votes
0answers
67 views

Convergence of a delayed policy update Q-learning

I thought about an algorithm that twists the standard Q-learning slightly, but I am not sure whether convergence to the optimal Q-value could be guaranteed. The algorithm starts with an initial ...
3
votes
1answer
342 views

Why does the error of my LSTM not decrease after 10 epochs?

Despite the problem being very simple, I was wondering why an LSTM network was not able to converge to a decent solution. ...
3
votes
0answers
30 views

How do we give a kick start to the Facenet network?

I read the Facenet paper and one thing I am not sure about (it might be trivial and I missed it) is how do we give the kick start to the network. The embeddings in the beginning are random, so ...
3
votes
0answers
37 views

How to know when a Environment will yield a deterministic model

Given enough experiment data on time taken for objects to fall to earth from different heights, one can create various models that will accurately predict the time it will take for an object falling ...
2
votes
1answer
50 views

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

While reading a paper about Q-learning in network energy consumption, I came across the section on convergence analysis. Does anyone know what convergence analysis is, and why is convergence analysis ...
2
votes
1answer
895 views

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

Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?
2
votes
1answer
104 views

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

Many have examined the idea of modifying learning rate at discrete times during the training of an artificial network using conventional back propagation. The goals of such work have been a balance ...
2
votes
2answers
76 views

How to check whether my loss function is convex or not?

Loss functions are useful in calculating loss and then we can update the weights of a neural network. The loss function is thus useful in training neural networks. Consider the following excerpt from ...
2
votes
1answer
692 views

Why isn't my implementation of A2C for the the atari pong game converging?

I have two different implementations with PyTorch of the Atari Pong game using A2C algorithm. Both implementations are similar, but some portion are different. https://colab.research.google.com/drive/...
2
votes
1answer
216 views

Is there a rigorous proof for finding Hopfield minima?

I am looking for a rigorous mathematical proof for finding the several local minima of the Hopfield networks. I am searching for something rigorous, a demonstration, not just let the network keep ...
2
votes
2answers
217 views

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

I'm finding it hard to understand the relationship between chaotic behavior, the human brain, and artificial networks. There are a number of explanations on the web, but it would be very helpful if I ...
2
votes
1answer
70 views

Why do I get the best policy before Q values converge using DQN?

I have implemented DQN algorithm and wonder why during testing, the best performance is achieved by a policy from about 300 episode, when mean Q values converge at about 800 episode? Mean Q-values ...
2
votes
1answer
594 views

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

If the agent is following an $\epsilon$-greedy policy derived from Q, is there any advantage to decaying $\epsilon$ even though $\epsilon$ decay is not required for convergence ?
2
votes
0answers
24 views

How to fix high variance of the returns on a 2d env?

I'm trying to train an agent on a self-written 2d env, and it just doesn't converge to the solution. It is basically a 2d game where you have to move a small circle around the screen and try to avoid ...
2
votes
0answers
76 views

Why does the number of input tokens to an LSTM have an impact on the convergence of Integrated Gradients?

Background I am computing the attribution scores for a simple LSTM model using Integrated Gradients. This method defines the contribution of a feature to a model prediction by integrating over the ...
2
votes
0answers
38 views

Hand Landmark Detector Not Converging

I'm currently trying to train a custom model with TensorFlow to detect 17 landmarks/keypoints on each of 2 hands shown in an image (fingertips, first knuckles, bottom knuckles, wrist, and palm), for ...
2
votes
0answers
39 views

Why does TD (0) converge to the MLE solution of the Markov model?

Why does TD (0) converge to the MLE solution of the Markov model? Let's take the Example 6.4 in Sutton and Barto's book as an example. Example 6.4: You are the Predictor Place yourself now in the ...
2
votes
0answers
9 views

References for the convergence of gradient-based algorithms for training neural networks

I'm looking for some good references that give convergence results of training neural networks. I'm decently familiar with works that analyze the convergence of SGD, and, in particular, I really like ...
2
votes
0answers
19 views

React on train-validation curve after trening

I have a regression task that I tray to solve with AI. I have around 6M rows with about 30 columns. (originally there was 100, but I reduce it with drop feature importance) I understand basic ...
2
votes
0answers
59 views

If the performance of an RL agent in a partially observable environment is "good", is this likely only accidental?

In my research, I remember to have read that, in case of an environment which can be modeled by partially observable MDP, there are no convergence guarantees (unfortunately, I do not find the paper ...
2
votes
0answers
447 views

Why is DDPG not learning and it does not converge?

I have used a different setting, but DDPG is not learning and it does not converge. I have used these codes 1,2, and 3 and I used different optimizers, activation functions, and learning rate but ...
2
votes
0answers
120 views

If the minimum Q value is decreasing and the maximum Q value increasing, is this a sign that dueling double DQN is diverging?

I'm training a dueling double DQN agent with prioritized replay buffer and notice that the min Q values are decreasing, while the max Q values are increasing. Is this a sign that it is diverging? ...
2
votes
0answers
430 views

Why is it hard to prove the convergence of the deep Q-learning algorithm?

Why is it hard to prove the convergence of the DQN algorithm? We know that the tabular Q-learning algorithm converges to the optimal Q-values, and with a linear approximator convergence is proved. ...
2
votes
0answers
43 views

How to show Monte Carlo methods converge to an estimate which minimizes mean squared error?

In chapter six of Sutton and Barto (p.128), they claim Monte Carlo methods converge to an estimate minimizing the mean squared error. How can this be shown formally? Bump
2
votes
0answers
73 views

Are there reinforcement learning algorithms that ensure convergence for continuous state space problems?

The Q-learning does not guarantee convergence for continuous state space problems (Why doesn't Q-learning converge when using function approximation?). In that case, is there an algorithm which ...
2
votes
1answer
465 views

Why does Q-learning converge to the optimal policy, even if the agent acts sub-optimally?

In Q-learning, during training, it doesn't matter how the agent selects actions. The algorithm always converges to the optimal policy. Why does this happen? What's the intuition?
1
vote
1answer
69 views

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

Q-Learning is guaranteed to converge if $\alpha$ decreases over time. On page 161 of the RL book by Sutton and Barto, 2nd edition, section 8.1, they write that Dyna-Q is guaranteed to converge if each ...
1
vote
1answer
133 views

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

I'm working on a deep q-learning model in an infinite horizon problem, with a continous state space and 3 possible actions. I'm using a neural network to approximate the action-value function. ...
1
vote
1answer
89 views

Is there a tutorial for understanding the proof of convergence for TD learning?

I'm reading the article An Analysis of Temporal-Difference Learning with Function Approximation (1997), but the mathematics inside seems overly complicated for me. Answers to some similar questions ...