20
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 ...
- 33.8k
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 ...
- 8,877
13
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 $...
- 8,877
12
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 ...
- 8,877
9
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}$:
\...
- 9,379
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 ...
- 33.8k
7
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 ...
- 9,379
7
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 ...
- 23.8k
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[ \...
- 171
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....
- 4,007
7
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. ...
- 33.8k
6
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 ...
- 1,951
6
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) =...
- 33.8k
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 ...
- 4,055
6
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 ...
- 33.8k
5
votes
Accepted
Understanding 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 ...
- 101
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 ...
- 361
5
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: ...
- 236
4
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 ...
- 149
4
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 ...
- 9,379
4
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 ...
- 495
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 ...
- 1,016
4
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 ...
- 33.8k
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, ...
- 131
3
votes
Is there a rigorous proof that AGI is possible, at least, in theory?
I'm going to go out on a limb and suggest that this is a matter of evolution, that humans are in no way exceptional in the grand scheme, and that AGI will manifest so long as technology advances, ...
- 6,067
3
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 ...
- 33.8k
3
votes
Accepted
Why does the KL divergence not satisfy the triangle inequality?
To prove that the KL divergence does not satisfy the triangle inequality, you just need a counterexample.
Definitions
KL divergence
Let's first recapitulate the definition of KL divergence for ...
- 33.8k
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 (...
- 33.8k
3
votes
Accepted
How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$?
I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with $r(s,a,s')$ rewards would look like this:
$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,...
- 436
Only top scored, non community-wiki answers of a minimum length are eligible