Skip to main content
31 votes
Accepted

Where can I find the proof of the universal approximation theorem?

There are multiple papers on the topic because there have been multiple attempts to prove that neural networks are universal (i.e. they can approximate any continuous function) from slightly different ...
nbro's user avatar
  • 40.9k
14 votes

Why doesn't Q-learning converge when using function approximation?

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 $...
John Doucette's user avatar
14 votes
Accepted

What are the implications of the "No Free Lunch" theorem for machine learning?

This is a really common reaction after first encountering the No Free Lunch theorems (NFLs). The one for machine learning is especially unintuitive, because it flies in the face of everything that's ...
John Doucette's user avatar
13 votes
Accepted

Why is A* optimal if the heuristic function is admissible?

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your ...
John Doucette's user avatar
10 votes

How do we prove the n-step return error reduction property?

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}$: \...
Dennis Soemers's user avatar
  • 10.3k
10 votes
Accepted

What is the proof that policy evaluation converges to the optimal solution?

First of all, efficiency and convergence are two different things. There's also the rate of convergence, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. ...
nbro's user avatar
  • 40.9k
9 votes

Why doesn't Q-learning converge when using function approximation?

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

How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?

In general the different reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ are not equivalent mathematically, so you will not find any formal proof. It is possible for the functions to resolve to ...
Neil Slater's user avatar
  • 32.7k
8 votes

Is there a rigorous proof that AGI is possible, at least, in theory?

A strong reason why people think the mind can be implemented on a Turing Machine stems from the Computational Theory of Mind (CTOM), which is the leading theory of mind for now. There are lots of ...
k.c. sayz 'k.c sayz''s user avatar
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.9k
8 votes

How is this Pytorch expression equivalent to the KL divergence?

This is the analytical form of the KL divergence between two multivariate Gaussian densities with diagonal covariance matrices (i.e. we assume independence). More precisely, it's the KL divergence ...
nbro's user avatar
  • 40.9k
7 votes

Is there a mathematical proof that shows that certain parameters work "better" than others for a certain task?

There is stuff like the Universal Approximation Theorem. There are also investigations into the loss surface of neural networks. And classics like this explanation of the vanishing gradient problem....
BlindKungFuMaster's user avatar
7 votes

Why is baseline conditional on state at some timestep unbiased?

Using the law of iterated expectations one has: $\triangledown _\theta \sum_{t=1}^T \mathbb{E}_{(s_t,a_t) \sim p(s_t,a_t)} [b(s_t)] = \nabla_\theta \sum_{t=1}^T \mathbb{E}_{s_t \sim p(s_t)} \left[ \...
Andrei Poehlmann's user avatar
7 votes
Accepted

How do I show that uniform-cost search is a special case of A*?

Yes, UCS is a special case of A*. UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) =...
nbro's user avatar
  • 40.9k
6 votes

Is there a rigorous proof that AGI is possible, at least, in theory?

Consciousness is not well-understood As an AI practitioner and philosopher, I don't think that humans will be able to create a truly conscious silicon-based AGI. Humans are incapable of creating some ...
ProfVersaggi's user avatar
6 votes

Where can I find the proof of the universal approximation theorem?

"Modern" Guarantees for Feed-Forward Neural Networks My answer will complement nbro's above, which gave a very nice overview of universal approximation theorems for different types of ...
ABIM's user avatar
  • 565
6 votes
Accepted

Is this proof of $\epsilon$-greedy policy improvement correct?

The weights do sum to one. Note that in the second line where we have $$\frac{\epsilon}{|\mathcal{A}(s)|} \sum_a q_{\pi}(s,a) + (1-\epsilon)\max_aq_{\pi}(s,a) \; ,$$ the sum is over the whole action ...
David's user avatar
  • 4,920
6 votes

Why are the Bellman operators contractions?

The inequality \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1}, \end{align} where $U$ and $V$ are two value functions, follows from the ...
nbro's user avatar
  • 40.9k
6 votes
Accepted

How is this Pytorch expression equivalent to the KL divergence?

The code is correct. Since OP asked for a proof, one follows. The usage in the code is straightforward if you observe that the authors are using the symbols unconventionally: ...
Sycorax's user avatar
  • 473
6 votes
Accepted

Why policy improvement theorem can't be applied in case of function approximation?

As referenced in Sutton's RL book regarding policy improvement theorem (PIT): The policy improvement theorem applies to the two policies that we considered at the beginning of this section: an ...
cinch's user avatar
  • 2,277
5 votes
Accepted

How is inequality 31 derived from equality 30 in lemma 2 of the "Trust Region Policy Optimization" paper?

We can start with equation (30): $$ \bar{A}(s) = P(a \neq \tilde{a}) \mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)] $$ Taking the absolute value ...
Nishant Desai's user avatar
5 votes

How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?

Let $R(s)$ denote a probability distribution over rewards that our agent may get in some MDP as a reward for entering a state $s$. The easiest case is to demonstrate that we can also choose to write ...
Dennis Soemers's user avatar
  • 10.3k
5 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.9k
5 votes

Is the summation of consistent heuristic functions also consistent?

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1. s --1-- g Assume that $h_0$ and $h_1$ are ...
Nathan S.'s user avatar
  • 371
5 votes
Accepted

Why there are only three machine learning paradigms: supervised, unsupervised, reinforcement?

You can formulate RL and unsupervised learning as "some sort of supervised learning"... in the case of UL you have that the target is an handcrafted task, it being similarity learning, next ...
Alberto's user avatar
  • 2,273
4 votes
Accepted

How can a neural network approximate all functions when the weights are not allowed to grow exponentially?

What is Proven The question references the proof of Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems. The 1989 proof stated that ...
Douglas Daseeco's user avatar
4 votes
Accepted

Can two admissable heuristics not dominate each other?

This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another ...
respectful's user avatar
  • 1,106
4 votes

Are these two forms of the state value function the same?

There are a few different, but equivalent, ways to express the relationships between value functions in the Bellman equations. Some differences are just notation, but in the case of the two equations ...
Neil Slater's user avatar
  • 32.7k
3 votes

Why doesn't Q-learning converge when using function approximation?

There are three problems Limited capacity Neural Network (explained by John) Non-stationary Target Non-stationary distribution Non-stationary Target In tabular Q-learning, when we update a Q-value, ...
Vignesh Sk's user avatar
3 votes

Understanding why the expectation is over the new policy $\pi'$ in the proof of the Policy Improvement Theorem

The expectation is over the policy $\pi'$ because the action at the state $S_t = s$ is taken according to $\pi'$, and, for the proof, the book text (2nd edition, paragraph below Equation 4.8) defines $...
PraveenPalanisamy's user avatar

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