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
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
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
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
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
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
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
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
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
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
1 vote
2 answers
2k views

What are the conditions for the convergence of SARSA to the optimal value function?

Is it correct that for SARSA to converge to the optimal value function (and policy) The learning rate parameter $\alpha$ must satisfy the conditions: $$\sum \alpha_{n^k(s,a)} =\infty \quad \text{and}...
KaneM's user avatar
  • 309
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
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
334 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
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
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
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
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
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
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
2 votes
1 answer
610 views

How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?

If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ ...
user avatar
2 votes
0 answers
450 views

What is the proof that "reward-to-go" reduces variance of policy gradient?

I am following the OpenAI's spinning up tutorial Part 3: Intro to Policy Optimization. It is mentioned there that the reward-to-go reduces the variance of the policy gradient. While I understand the ...
sirKris van Dela's user avatar
1 vote
1 answer
2k views

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

In reinforcement learning, policy improvement is a part of an algorithm called policy iteration, which attempts to find approximate solutions to the Bellman optimality equations. Pages 84 and 85 in ...
Karthik Thiagarajan's user avatar