Hot answers tagged

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 ...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
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}$: \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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[ \...
user avatar
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....
user avatar
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. ...
user avatar
  • 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 ...
user avatar
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) =...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar
  • 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,...
user avatar
  • 436

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