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.

Filter by
Sorted by
Tagged with
29 votes
3 answers
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 ...
Leroy Od's user avatar
  • 455
22 votes
3 answers
5k views

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

The tabular Q-learning algorithm is guaranteed to find the optimal $Q$ function, $Q^*$, provided the following conditions (the Robbins-Monro conditions) regarding the learning rate are satisfied $\...
nbro's user avatar
  • 40.2k
14 votes
1 answer
1k views

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

The No Free Lunch (NFL) theorem states (see the paper Coevolutionary Free Lunches by David H. Wolpert and William G. Macready) any two algorithms are equivalent when their performance is averaged ...
user avatar
13 votes
5 answers
6k views

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

It is often implicitly assumed in computer science that the human mind, or at least some mechanical calculations that humans perform (see the Church-Turing thesis), can be replicated with a Turing ...
yters's user avatar
  • 387
13 votes
1 answer
29k views

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

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
Wizard's user avatar
  • 303
11 votes
2 answers
2k views

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

In section 7.1 (about the n-step bootstrapping) of the book Reinforcement Learning: An Introduction (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-...
123learn's user avatar
  • 111
10 votes
2 answers
4k views

Why are the Bellman operators contractions?

In these slides, it is written \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \tag{9} \label{9} \\ \|T V-T U\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \...
kevin's user avatar
  • 201
9 votes
2 answers
1k views

Why is baseline conditional on state at some timestep unbiased?

In the homework for the Berkeley RL class, problem 1, it asks you to show that the policy gradient is still unbiased if the baseline subtracted is a function of the state at time step $t$. $$ \...
Laura C's user avatar
  • 91
8 votes
2 answers
4k views

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

Although I know how the algorithm of iterative policy evaluation using dynamic programming works, I am having a hard time realizing how it actually converges. It appeals to intuition that, with each ...
SAGALPREET SINGH's user avatar
8 votes
1 answer
925 views

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

It has been proven in the paper "Approximation by Superpositions of a Sigmoidal Function" (by Cybenko, in 1989) that neural networks are universal function approximators. I have a related question. ...
Yan King Yin's user avatar
8 votes
1 answer
333 views

Can deep learning be used to help mathematical research?

I am currently learning about deep learning and artificial intelligence and exploring his possibilities, and, as a mathematician at heart, I am inquisitive about how it can be used to solve problems ...
Antoine Labelle's user avatar
8 votes
0 answers
272 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', ...
sirfroggy's user avatar
7 votes
2 answers
2k views

How is this Pytorch expression equivalent to the KL divergence?

I found the following PyTorch code (from this link) -0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp()) where mu is the mean ...
user8714896's user avatar
7 votes
2 answers
2k views

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

In this video, the lecturer states that $R(s)$, $R(s, a)$ and $R(s, a, s')$ are equivalent representations of the reward function. Intuitively, this is the case, according to the same lecturer, ...
nbro's user avatar
  • 40.2k
7 votes
1 answer
3k views

Why does a negative reward for every step really encourage the agent to reach the goal as quickly as possible?

If we shift the rewards by any constant (which is a type of reward shaping), the optimal state-action value function (and so optimal policy) does not change. The proof of this fact can be found here. ...
nbro's user avatar
  • 40.2k
6 votes
1 answer
1k 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?
fool's user avatar
  • 203
6 votes
2 answers
10k views

Is there a proof to explain why XOR cannot be linearly separable?

Can someone explain to me with a proof or example why you can't linearly separate XOR (and therefore need a neural network, the context I'm looking at it in)? I understand why it's not linearly ...
Slowat_Kela's user avatar
6 votes
1 answer
381 views

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

The following paragraph about $\epsilon$-greedy policies can be found at the end of page 100, under section 5.4, of the book "Reinforcement Learning: An Introduction" by Richard Sutton and ...
Nishanth Rao's user avatar
6 votes
1 answer
1k views

Can two admissable heuristics not dominate each other?

I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am ...
JRowan's user avatar
  • 163
6 votes
1 answer
113 views

Proof that there always exists a dominating policy in an MDP

I think that it is common knowledge that for any infinite horizon discounted MDP $(S, A, P, r, \gamma)$, there always exists a dominating policy $\pi$, i.e. a policy $\pi$ such that for all policies $\...
MMM's user avatar
  • 185
5 votes
1 answer
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?
dua fatima's user avatar
5 votes
2 answers
1k views

Given two optimal policies, is an affine combination of them also optimal?

If there are two different optimal policies $\pi_1, \pi_2$ in a reinforcement learning task, will the linear combination (or affine combination) of the two policies $\alpha \pi_1 + \beta \pi_2, \alpha ...
yang liu's user avatar
5 votes
1 answer
1k views

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)$?

The AIMA book has an exercise about showing that an MDP with rewards of the form $r(s, a, s')$ can be converted to an MDP with rewards $r(s, a)$, and to an MDP with rewards $r(s)$ with equivalent ...
Asher's user avatar
  • 436
5 votes
1 answer
2k views

How does L2 regularization make weights smaller?

I'm learning logistic regression and $L_2$ regularization. The cost function looks like below. $$J(w) = -\displaystyle\sum_{i=1}^{n} (y^{(i)}\log(\phi(z^{(i)})+(1-y^{(i)})\log(1-\phi(z^{(i)})))$$ And ...
Riddle Aaron's user avatar
5 votes
2 answers
162 views

Why is $\sum_{s} \eta(s)$ a constant of proportionality in the proof of the policy gradient theorem?

In Sutton and Barto's book (http://incompleteideas.net/book/bookdraft2017nov5.pdf), a proof of the policy gradient theorem is provided on pg. 269 for an episodic case and a start state policy ...
jwl17's user avatar
  • 59
4 votes
3 answers
1k views

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

The machine learning community often only provides empirical results, but I am also interested in theoretical results and proofs. Specifically, is there a mathematical proof that shows that certain ...
Wizard Programming's user avatar
4 votes
2 answers
9k views

If an heuristic is not admissible, can it be consistent?

I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
Awa's user avatar
  • 41
4 votes
2 answers
257 views

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning? I came across this statement in the section 5.2 of the book "understanding machine learning: from theory to ...
Ben's user avatar
  • 253
4 votes
1 answer
147 views

How to prove the second form of Bellman's equation?

I'd like to prove this "second form" of Bellman's equation: $v(s) = \mathbb{E}[R_{t + 1} + \gamma v(S_{t+1}) \mid S_{t} = s]$ starting from Bellman's equation: $v(s) = \mathbb{E}[G_{t} \mid ...
Daviiid's user avatar
  • 573
4 votes
1 answer
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-...
Nishanth Rao's user avatar
4 votes
1 answer
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) ...
ihavenoidea's user avatar
4 votes
1 answer
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 ...
Luca Thiede's user avatar
4 votes
1 answer
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 ...
NNLearner's user avatar
4 votes
1 answer
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 ...
bipul kalita's user avatar
4 votes
0 answers
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 ...
EmmanuelMess's user avatar
4 votes
1 answer
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 ...
A Das's user avatar
  • 141
4 votes
2 answers
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 ...
Gooby's user avatar
  • 351
3 votes
1 answer
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 ...
Vladislav Gladkikh's user avatar
3 votes
1 answer
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 ...
Mostafa Ghadimi's user avatar
3 votes
2 answers
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 ...
stoic-santiago's user avatar
3 votes
1 answer
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 ...
lolodino77's user avatar
3 votes
2 answers
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?
user avatar
3 votes
1 answer
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?
KaneM's user avatar
  • 309
3 votes
1 answer
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 ...
user8714896's user avatar
3 votes
2 answers
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 ...
nbro's user avatar
  • 40.2k
3 votes
1 answer
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. ...
vdbuss's user avatar
  • 81
3 votes
1 answer
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 ...
Thomas Hustache's user avatar
3 votes
2 answers
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 ...
tmaric's user avatar
  • 382
3 votes
1 answer
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 ...
hpr16's user avatar
  • 31
3 votes
1 answer
198 views

$\gamma^t$ in REINFORCE update (Sutton-Barto RL book Exercise 13.2)

I've struggled with solving exercise 13.2 from Reinforcement Learning: An Introduction Second Edition : Generalize the box on page 199, the policy gradient theorem (13.5), the proof of the policy ...
cfml's user avatar
  • 53