# Questions tagged [proofs]

For questions that ask about or call for proofs for specific assertions, whether they be proofs of theorems or corollaries, proofs of concept through working implementation, counter proofs, or counter examples.

118 questions
Filter by
Sorted by
Tagged with
14k views

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

The Wikipedia article for the universal approximation theorem cites a version of the universal approximation theorem for Lebesgue-measurable functions from this conference paper. However, the paper ...
• 455
5k views

• 185
13k views

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

How do I show that uniform-cost search is a special case of A*? How do I prove this?
• 323
1k views

• 573
1k views

### Proof of Maximization Bias in Q-learning?

In the textbook "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, the concept of Maximization Bias is introduced in section 6.7, and how Q-learning "over-estimates" action-...
• 147
4k views

### Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}. If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) ...
• 265
392 views

### Why is the stationary distribution independent of the initial state in the proof of the policy gradient theorem?

I was going through the proof of the policy gradient theorem here: https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#svpg In the section "Proof of Policy Gradient ...
• 338
247 views

### How is G(z) related to x in GAN proof?

In the proofs for the original GAN paper, it is written: $$∫_x p_{data}(x) \log D(x)dx+∫_zp(z)\log(1−D(G(z)))dz =∫_xp_{data}(x)\log D(x)+p_G(x) \log(1−D(x))dx$$ I've seen some explanations asserting ...
223 views

### Is there a limit of minimum error for a particular training dataset in artificial Neural Network?

In error-based learning using gradient descent, if I give you a training dataset, then can you find the minimum error after training? And the minimum error should be true for all architectures of a ...
80 views

### When do two identical neural networks have uncorrelated errors?

In Chapter 9, section 9.1.6, Raul Rojas describes how committees of networks can reduce the prediction error by training N identical neural networks and averaging the results. If $f_i$ are the ...
• 217
238 views

### In lemma 1 of the TRPO paper, why isn't the expectation over $s'∼P(s'|s,a)$?

In the Trust Region Policy Optimization paper, in Lemma 1 of Appendix A, I didn't quite understand the transition from (21) from (20). In going from (20) to (21), $A^\pi(s_t, a_t)$ is substituted with ...
• 141
298 views

### What is the proof that the branch and bound algorithm always finds optimal path in a graph?

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others However, I haven't been able to find a ...
• 351
770 views

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

I read in books, blogs, and articles that there are three learning paradigms: supervised, unsupervised, and reinforcement. However, I have never found a proof that this list is exhaustive. Can it be ...
1k views

### Is the summation of consistent heuristic functions also consistent?

Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not? Is there any proof ...
252 views

### Why does (not) the distribution of states depend on the policy parameters that induce it?

I came across the following proof of what's commonly referred to as the log-derivative trick in policy-gradient algorithms, and I have a question - While transitioning from the first line to the ...
• 1,141
444 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 letting the network keep ...
4k views

### If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?
2k 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?
• 309
3k views

### Why does the KL divergence not satisfy the triangle inequality?

The KL divergence is defined as $$D_{KL}=\sum_i p(x_i)log\left(\frac{p(x_i)}{q(x_i)}\right)$$ Why does $D_{KL}$ not satisfy the triangle inequality? Also, can't you make it satisfy the triangle ...
• 777
460 views

### Why is the max a non-expansive operator?

In certain reinforcement learning (RL) proofs, the operators involved are assumed to be non-expansive. For example, on page 6 of the paper Generalized Markov Decision Processes: Dynamic-programming ...
• 40.2k
198 views

### Is there an error in A* optimality proof Russel-Norvig 4th edition?

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. ...
• 81
342 views

### Why adding a baseline doesn't affect the policy gradient?

On the OpenAI's Spinning Up, they justify the fact that adding a baseline $b(s_t)$ in the policy gradient doesn't change its gradient by saying that this is an immediate consequence of the EGLP Lemma ...
370 views

### How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?

In the proof of the policy gradient theorem in the RL book of Sutton and Barto (that I shamelessly paste here): there is the "unrolling" step that is supposed to be immediately clear With ...
• 382
987 views

### How do I find whether this heuristic is or not admissible and consistent?

I was given the following problem to solve. Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge ...
• 31