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.
73
questions
4
votes
2answers
275 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 ...
2
votes
2answers
212 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?
4
votes
1answer
101 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.
...
0
votes
1answer
87 views
What is the optimal value function of the shifted version of the reward function?
Similarly to this question that I asked some time ago, what is the optimal value function of the shifted (by some constant $c$) version of some reward function? More precisely, let's assume that $r(s, ...
3
votes
2answers
69 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 ...
2
votes
0answers
24 views
Do we assume the policy to be deterministic when proving the optimality?
In reinforcement learning, when we talk about the principle of optimality, do we assume the policy to be deterministic?
1
vote
0answers
27 views
How can I derive n-step off-policy temporal difference formula?
I was reading the book "Reinforcement Learning: An Introduction" by Sutton and Barto. In section 7.3, they write the formula for n-step off-policy TD as
$$V(S_t) = V(S_{t-1}) + \alpha \rho_{...
0
votes
0answers
52 views
Can a computer make a proof by induction?
Can a computer solve the following problem, i.e. make a proof by induction? And why?
Prove by induction that $$\sum_{k=1}^nk^3=\left(\frac{n(n+1)}{2}\right)^2, \, \, \, \forall n\in\mathbb N .$$
I'm ...
4
votes
2answers
109 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} \...
5
votes
0answers
143 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',
...
1
vote
0answers
27 views
What is the proof that the variance of the gradient estimate in Actor-Critic is smaller than in REINFORCE?
The intuition provided when introducing actor-critic algorithms is that the variance of its gradient estimates is smaller than in REINFORCE as, e.g., discussed here. This intuition makes sense for the ...
1
vote
1answer
44 views
When to use AND and when to use Implies in first-order logic?
I am trying to learn the theory behind first-order logic (FOL) and do some practice runs of converting statements into the form of FOL.
One issue I keep running into is hesitating on whether to use an ...
2
votes
0answers
79 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-...
2
votes
0answers
90 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 ...
1
vote
0answers
39 views
How do you prove that minimax algorithm outputs a subgame-perfect Nash equilibrium?
At every node, MAX would always move to maximise the minimum payoff while MIN choose to minimise the maximum payoff, hence there is nash equilibrium.
By using backwards induction, at every node, MAX ...
5
votes
1answer
144 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 ...
1
vote
0answers
37 views
Why is it hard to prove the convergence of the deep Q-learning algorithm?
Why is it hard to prove the convergence of the DQN algorithm? We know that the tabular Q-learning algorithm converges to the optimal Q-values, and with a linear approximator convergence is proved.
...
1
vote
1answer
50 views
Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?
My question is actually related to the addition of probabilities. I am reading on computational learning theory from Tom Mitchell's machine learning book.
In chapter 7, when proving the upper bound ...
1
vote
1answer
77 views
Monte Carlo epsilon-greedy Policy Iteration: monotonic improvement for all cases or for the expected value?
I was going through university slides and this particular slide is trying to prove that in a Monte Carlo Policy Iteration algorithm using an epsilon-greedy policy, the state Values (V-Values) are ...
4
votes
2answers
251 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 ...
2
votes
1answer
27 views
Equivalence between expected parameter increments in “Off-Policy Temporal-Difference Learning with Function Approximation”
I am having a hard time understanding the proof of theorem 1 presented in the "Off-Policy Temporal-Difference Learning with Function Approximation" paper.
Let $\Delta \theta$ and $\Delta \...
2
votes
1answer
46 views
Is the derivative of the loss wrt a single scalar parameter proportional to the loss?
I am wondering about the correlation between the loss and the derivative of the loss wrt a single scalar parameter, with the same sample. That means: considering a machine learning model with ...
2
votes
0answers
76 views
Does Rice's theorem prove safe AI is undecidable?
According to Wikipedia
In computability theory, Rice's theorem states that all non-trivial,
semantic properties of programs are undecidable. A semantic property
is one about the program's ...
2
votes
1answer
139 views
How to prove $\mathcal H$ with VC dimension $d$ shatter all subsets with size less than $d-1$?
I was wondering that if a certain hypothesis class $H$ has a VC dimension $d$ over domain $X$ how to prove that $H$ will shatter all subsets of $X$ with size less than $d$ i.e $H$ will shatter $A \...
1
vote
3answers
109 views
How to prove that gradient descent doesn't necessarily find the global optimum?
How can I prove that gradient descent doesn't necessarily find the global optimum?
For example, consider the following function
$$f(x_1, x_2, x_3, x_4) = (x_1 + 10x_2)^2 + 5x_2^3 + (x_2 + 2x_3)^4 + ...
2
votes
0answers
74 views
Is an oracle that answers only with a “yes” or “no” dangerous?
I was thinking about the risks of Oracle AI and it doesn't seem as safe to me as Bostrom et al. suggest. From my point of view, even an AGI that only answers questions could have a catastrophic impact....
3
votes
1answer
166 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 ...
1
vote
0answers
40 views
Does SARSA(0) converge to the optimal policy in expectation if the Robbins-Monro conditions are removed?
The conditions of convergence of SARSA(0) to the optimal policy are :
The Robbins-Monro conditions above hold for $Ī±_t$.
Every state-action pair is visited infinitely often
The policy is greedy with ...
1
vote
2answers
58 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}...
1
vote
1answer
90 views
Does TD(0) prediction require Robbins-Monro conditions to converge to the value function?
Does the learning rate parameter $\alpha$ require the Robbins-Monro conditions below for the TD(0) algorithm to converge to the true value function of a policy?
$$\sum \alpha_t =\infty \quad \text{...
1
vote
1answer
330 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?
2
votes
1answer
95 views
Is there a mathematical theory behind why MLP can classify handwritten digits?
I'm trying to really understand how multi-layer perceptrons work. I want to prove mathematically that MLP's can classify handwritten digits. The only thing I really have is that each perceptron can ...
2
votes
1answer
85 views
Why does KL divergence not satisfy the triangle inequality?
$D_{KL}=\sum_i p(x_i)log(p(x_i)/q(x_i)$
Also can't you make it satisfy the triangle inequality by taking the absolute value of the information at every point?
2
votes
0answers
43 views
How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?
How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?
For this problem, I only try the case $n=2$ for 1. When $n=2$, consider 4 points $A,B,C,D$ and ...
2
votes
0answers
191 views
A problem about the relation between 1-oracle and 2-oracle PAC model
This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $\mathcal{D}_{+}$ and $\mathcal{D}_{-} .$ For an ...
2
votes
0answers
40 views
How can we prove this inequality, related to the generalization error, without using the Rademacher complexity?
This is an inequality on page 36 of the book Foundations of Machine Learning, but the author only states it without proof.
$$
\mathbb{P}\left[\left|R(h)-\widehat{R}_{S}(h)\right|>\epsilon\right] \...
2
votes
0answers
36 views
Convert a PAC-learning algorithm into another one which requires no knowledge of the parameter
This is part of the exercise 2.13 in the book Foundations of Machine Learning (page 28). You can refer to chapter 2 for the notations.
Consider a family of concept classes $\left\{\mathcal{C}_{s}\...
3
votes
1answer
60 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 ...
3
votes
1answer
92 views
Understanding proof of lemma 1 (policy improvement bound) of the “Trust Region Policy Optimization” paper
In the Trust Region Policy Optimization paper, in Lemma 1 of Appendix A, I did not quite understand the transition from (21) from (20). In going from (20) to (21), $A^\pi(s_t, a_t)$ is substituted ...
4
votes
2answers
1k 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 ...
6
votes
1answer
103 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 ...
10
votes
1answer
661 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 ...
4
votes
2answers
95 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 ...
2
votes
1answer
235 views
What is the optimal value function of the scaled version of the reward function?
Consider the reward function $r(s, a)$ with optimal state-action value function $q_*(s, a)$. What would be the optimal state-action value function of $c r(s, a)$, for $c \in \mathbb{R}$? Would it be $...
2
votes
0answers
43 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
4
votes
1answer
324 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?
3
votes
1answer
76 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
98 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 ...
11
votes
2answers
3k 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
167 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 $...
