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.
26
questions
1
vote
1answer
26 views
What happens to the optimal value function if the reward is multiplied by a constant?
What happens to the optimal action-value function, $q_*$ if the reward is multiplied by a constant $c$? Is the optimal action-value function also multiplied by such a constant?
2
votes
0answers
41 views
How to show Monte Carlo methods converge to an estimate which minimizes mean squared error?
In chapter six of Sutton and Barto (p.128), they claim Monte Carlo methods converge to an estimate minimizing the mean squared error. How can this be shown formally?
Bump
3
votes
1answer
89 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?
2
votes
1answer
40 views
Is unsupervised disentanglement really impossible?
In Locatello et al's Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations he claims to prove unsupervised disentanglement is impossible.
His entire claim is ...
1
vote
1answer
43 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 let the network keep ...
4
votes
1answer
107 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 ...
2
votes
1answer
59 views
Understanding the proof that A* search is optimal
I don't understand the proof that $A^*$ is optimal.
The proof is by contradiction:
Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
3
votes
1answer
71 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 ...
0
votes
0answers
33 views
Proof of Correctness of Monte Carlo Tree Search
I'm trying to make the proof of correctness of Monte Carlo Tree Search. Any help would be really appreciated.
3
votes
1answer
25 views
Proof Branch and Bound 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, but I haven't been able to find a proof on ...
1
vote
0answers
38 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 $S$ = {$h_1, h_2, ..., h_n$}.
If all heuristics in $S$ are admissible, does that mean that a heuristic that takes the $MIN(S)$ (or $MAX$ for that matter) is ...
9
votes
2answers
210 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 regarding the learning rate are satisfied
$\sum_{t} \alpha_t(s, a) = \infty$
$...
3
votes
2answers
54 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 ...
3
votes
2answers
62 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, ...
6
votes
1answer
302 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-...
1
vote
1answer
77 views
Understanding lemma 2 of the “Trust Region Policy Optimization” paper
In the Trust Region Policy Optimization paper, in Lemma 2 of Appendix A, I did not quite understand deriving inequality (31) from (30), which is:
$$\bar{A}(s) = P(a \neq \tilde{a} | s) \mathbb{E}_{(a,...
2
votes
1answer
1k 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?
1
vote
0answers
68 views
Why does Q-learning converges to optimal policy even if I am acting suboptimally?
In Q-learning, during training, it doesn’t matter how I select actions. The algorithm always converges to optimal optimal policy. Why does this happen?
2
votes
0answers
39 views
Understanding the proof of theorem 2.1 from the paper “Efficient reductions for imitation learning”
I am trying to understand the proof of theorem 2.1 from this paper:
Ross, Stéphane, and Drew Bagnell. "Efficient reductions for imitation learning." Proceedings of the thirteenth international ...
5
votes
1answer
56 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 ...
6
votes
2answers
303 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.
...
7
votes
1answer
4k 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 ...
-1
votes
2answers
88 views
When is a measurable function a Bayesian decision function?
When is a measurable function a Bayesian decision function? How do I prove this?
Can you give an example with standard or weighted binary classification?
10
votes
9answers
2k views
Proof that Artificial General Intelligence is possible
It is assumed in computer science that the human mind can be replicated with a Turing machine, therefore Artificial General Intelligence (AGI) is possible. To assume otherwise is to believe in ...
2
votes
1answer
658 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 ...
-2
votes
3answers
195 views
Is there a proof that states that an AI can become smarter than its creator?
Is there a proof that states the possibility or impossibility of an AI system to acquire more sophisticated capabilities (in terms of generic cleverness) than its own creator?
