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.
124 questions
1
vote
1
answer
47
views
mathematics on monotonic e-greedy policy improvement
The picture is the shortcut from the Stanford CS234 RL course note. I have a question about the proof on the monotonic property of $\epsilon$-greedy policies. In the red underlined expression, if some ...
- 13
0
votes
1
answer
40
views
Proof of representation as a trajectory is the same as a representation in terms of state-action pairs
I would like to prove the following equation, which pops up everywhery in RL and I would like to have a clean proof of it. It kind of gives a representation as a trajectory vs. a representaiton in ...
- 139
0
votes
0
answers
28
views
How to combine language models and theorem provers?
Suppose that a mathematician wants to find a proof of a conjecture or understand details of some proof. Can one combine language models like ChatGpt or Copilot and theorem proving software like Coq to ...
- 101
1
vote
1
answer
85
views
Proof of gradient of $v_{\pi}(s)$ via Kronecker Product
Hi I am reading Mathematical Foundation of Reinforcement Learning by Shiyu Zhao and I try to understand a proof regarding policy gradients. The part is on page 209/210 in Policy Gradient Methods. ...
- 139
1
vote
1
answer
71
views
Understanding the policy improvement theorem for Monte Carlo Control without Exploring Starts
I am currently studying the equations 5.2 in Reinforcement Learning An Introduction By Sutton and Barto on page 101.
I want to comprehent the proof by a simple example:
Having only one State with two ...
- 13
3
votes
2
answers
379
views
Is the Bellman backup unbiased?
This is comes from cs285 2023Fall hw3.
In my opinion, if $\hat{Q}$ is unbiased estimate of $Q$, then
$$
\begin{align}
\mathbb{E}_{D \sim P}[B_{D}\hat{Q} - B_{D}Q]
&= \mathbb{E}_{D \sim P}[r(s,a) +...
- 77
4
votes
1
answer
285
views
Why policy improvement theorem can't be applied in case of function approximation?
Policy improvement theorem is proven as follows:
$$v_\pi(s) = \sum_{a \in A} \pi(a|s)q_\pi(a,s) \leq \max_{a \in A} q_\pi(a,s) = q_\pi(\pi'(s), s)$$
What step of the proof does not hold for function ...
- 143
0
votes
0
answers
46
views
Separation property of general uninform graph search from Artificial Intelligence: A Modern Approach Textbook by Peter Norvig and Stuart J. Russell
Before I start, I'm deeply sorry if my grammar is incorrect or hard to understand, since I haven't trained my English for a long time. Thanks you for spending time and effort to read and answer my ...
3
votes
1
answer
813
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 ...
1
vote
1
answer
38
views
Applicability of Holland's Schema Theorem to Genetic Algorithms with Non-Binary Individual Representations
I'm currently working on a problem formulation that requires non-binary individual representations in a genetic algorithm (GA). I've been exploring Holland's Schema Theorem as a theoretical basis for ...
- 11
3
votes
3
answers
388
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 ...
- 53
0
votes
1
answer
256
views
How to prove that $V^\star$ is optimal if and only if it satisfies the Bellman equation?
The Question
I'd like to prove that a function $V$ (like in reinforcement learning) is optimal iff it satisfies the bellman equation. A lot of places online reference this fact, but none prove it. ...
- 89
1
vote
1
answer
178
views
Is there a mathematical proof of the universal approximation theorem for neural networks with binary weights?
Since the Universal approximation theorem shows that standard multilayer feedforward networks with as few as a single hidden layer, sufficient hidden units, and arbitrary bounded and nonconstant ...
- 33
4
votes
1
answer
1k
views
Would it be possible to involve a proof assistant in the process of training a LLM?
LLMs like GPT-3 have been shown capable of outputting highly complex code. Sadly, actually using them to replace a programmer's job has two major caveats:
LLMs are notoriously bad at producing ...
- 405
5
votes
2
answers
202
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 ...
- 59
1
vote
2
answers
284
views
Why $V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s,a),\forall s \in S$ in reinforcement learning?
In some RL notes, I encountered the following equation, which I am trying to prove:
$$
V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s, a),\forall s \in S
$$
Here is my attemption:
Firstly, I only need to ...
- 11
2
votes
1
answer
1k
views
Are my proofs that the Bellman operators are contractions correct?
Introduction
I'm studying Reinforcement Learning, and in order to increase my understanding I've been challenging myself by trying to write proofs that show that the right hand side of the Bellman ...
- 53
1
vote
0
answers
34
views
Proof that the Policy Iteration Converges?
Let $\mathcal{X}=:\{x_1, x_2, x_3,...,x_n\}$ be the state space. Let $\mathcal{U}:=\{u_1, u_2, u_3,...,u_m\}$ be the set of actions. Let $A^{u_1}, A^{u_2}, A^{u_3},...,A^{u_m}$ be the state transition ...
2
votes
1
answer
221
views
Are these two forms of the state value function the same?
Why are there different forms of the value function in reinforcement learning?
Sutton & Barto (2nd edition, equation 3.14) define the state value function as follows
$$v_{\pi}(s) = \displaystyle\...
- 185
3
votes
1
answer
224
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
0
votes
0
answers
199
views
How to prove that "w will converge to TD fixed point once A is positive definite"
In Reinforcement Learning: An Introduction 2nd edition section 9.4 (p. 206), it says that when we use TD(0) as target and use semi-gradient method to update :
In general, $w_t$ will be reduced ...
- 1
1
vote
0
answers
242
views
Why does the schema theorem of genetic algorithms hold?
I have been reading about the Schema Theorem - one of the first theorems from the field of evolutionary computing and genetic algorithms, largely responsible for justifying the use of genetic ...
- 339
1
vote
0
answers
179
views
Where do the characteristics of self-attention come into play in Linformer's proof that self-attention is low rank?
In Linformer's proof that self-attention is low rank in their paper, I don't see how it doesn't generalize to every matrix. They don't utilize any specifics of self-attention (the entire proof feels ...
- 2,387
2
votes
0
answers
330
views
Why does TD (0) converge to the MLE solution of the Markov model?
Why does TD (0) converge to the MLE solution of the Markov model?
Let's take the Example 6.4 in Sutton and Barto's book as an example.
Example 6.4: You are the Predictor Place yourself now in the ...
- 143
0
votes
1
answer
65
views
How to show $\rho > 0$ when $\rho$ be minimum attainable from $y_n(W^{*T}X_n)$, where $W^*$ the vector that separates the data?
In the book Learning from Data written (by Abu Mostafa), we have the following exercise:
Let $\rho$ be minimum attainable from $y_n(W^{*T}X_n)$ where $W^*$ is the vector that separates the data. Show ...
- 101
2
votes
1
answer
282
views
What is the derivative of equation 1 in the paper "Conservative Q-Learning for Offline Reinforcement Learning"?
I am looking at the paper Conservative Q-Learning for Offline Reinforcement Learning, but I'm not sure how they proved theorem 3.1.
Here is a screenshot of theorem 3.1.
In the proof of theorem 3.1
...
- 121
0
votes
1
answer
164
views
Policies for which the policy improvement theorem holds
According to Reinforcement Learning (2nd Edition) by Sutton and Barto, the policy improvement theorem states that for any pair of deterministic policies $\pi'$ and $\pi$, if $q_\pi(s,\pi'(s)) \geq v_\...
2
votes
1
answer
65
views
How to prove importance sampling ratio is uncorrelated with action-value (or state-value) estimate?
In Sutton & Barto (2nd edition), the following is mentioned on page 150 (p. 172 of the pdf), section 7.4:
the importance sampling ratio has expected value one (Section 5.9) and is uncorrelated ...
- 379
0
votes
0
answers
32
views
Non-locally Electrically Programmable Logic Gates - Technological Advances Progress
Preface: I’d like to clarify that I understand what a relay is and that a PLC uses a fairly conventional microprocessor that only digitally establishes logical logic gate configuration as a digitally ...
3
votes
0
answers
118
views
How to prove Lemma 1.6 in the book "Reinforcement Learning: Theory and Algorithms"
I am trying to prove the following lemma from Reinforcement Learning: Theory and Algorithms on page 8.
Lemma 1.6. We have that:
$$
\left[(1-\gamma)\left(I-\gamma P^{\pi}\right)^{-1}\right]_{(s, a),\...
- 31
6
votes
1
answer
128
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 $\...
- 185
3
votes
1
answer
450
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
...
4
votes
1
answer
156
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 ...
- 575
2
votes
2
answers
514
views
Why is the equation $\mathbb{E} \left[ (Y - \hat{Y})^2 \right] = \left(f(X) - \hat{f}(X) \right)^2 + \operatorname{Var} (\epsilon)$ true?
In the book An Introduction to Statistical Learning, the authors claim (equation 2.3, p. 19, chapter 2)
$$\mathbb{E} \left[ (Y - \hat{Y})^2 \right] = \left(f(X) - \hat{f}(X) \right)^2 + \operatorname{...
- 41.4k
1
vote
1
answer
95
views
When showing that the policy improvement theorem applies to MC control, why is $q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \geq v_{\pi_{k}}(s)$ true?
When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on page 98 of Sutton and Barto's book (2nd edition) that:
$$
\begin{aligned}
...
- 225
2
votes
1
answer
127
views
Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?
Consider the following statement from 4.1 Policy Evaluation of the first edition of Sutton and Barto's book.
The existence and uniqueness of $V^{\pi}$ are guaranteed as long as
either $\gamma < 1$...
- 3,990
1
vote
0
answers
50
views
Why is the number of examined nodes $ O(b^{3d/4})$ in $\alpha$-$\beta$ pruning?
I'm taking a course 'Introduction to AI' and, in one of the tutorials, it was written that when pruning the game tree using $\alpha$-$\beta$ boundaries, the number of nodes that will be developed, ...
- 131
1
vote
0
answers
42
views
How to prove that a regularisation method simplified a neural network?
There are a few ways to regularise a neural network, for example dropout or the L1. Now, both these methods, and possibly most other regularisation methods, tend to remove from, or simplify the neural ...
- 236
2
votes
1
answer
251
views
Is $\min(h_1(s),\ h_2(s))$ consistent?
If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?
- 21
0
votes
1
answer
1k
views
Are hill climbing variations always optimal and complete?
Are hill climbing variations (like steepest ascent hill climbing, stochastic hill climbing, random restart hill climbing, local beam search) always optimal and complete?
user45792
0
votes
0
answers
56
views
How is the discounted maximum entropy objective obtained for soft-q-learning and SAC
In the soft q-learning paper, they provide an expression for the maximum entropy objective that takes discounting into account.
My main question is: can someone explain how they incorporated ...
- 394
1
vote
1
answer
111
views
Can the law of iterated expectation be used on the inner expectation of the DQN cost function described in the DQN paper
Is the expression for the DQN cost function, Equation (2) of the DQN paper
$$\begin{align}L_1 &= E_{\mu,\pi}\left[\left(y_i - q(s,a;\theta)\right)^2\right]\\
&=E_{\mu,\pi}\left[\left(E_{\...
- 394
2
votes
1
answer
401
views
If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?
Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible.
Why are the following statements true?
$A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
- 21
7
votes
2
answers
3k
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 ...
- 805
3
votes
1
answer
455
views
Is my proof of equation 0.6 in the book "Reinforcement Learning: Theory and Algorithms" correct?
In Sham Kakade's Reinforcement Learning: Theory and Algorithms, this equation (page 17) is used preceding the proof of performance difference lemma.
I am attempting to prove equation 0.6. Here is my ...
- 33
4
votes
0
answers
83
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 ...
- 227
2
votes
1
answer
157
views
How to prove the formula of eligibility traces operator in reinforcement learning?
I don't understand how the formula in the red circle is derived. The screenshot is taken from this paper
- 23
2
votes
0
answers
55
views
Does there necessarily exist "dominated actions" in a MDP?
In a Markov Decision Process, is it possible that there exists no "dominated action"?
I define a dominated action the following way:
we say that $(s,a)$ is a dominated action, if $\forall \...
- 31
1
vote
1
answer
308
views
How do I prove that the MSE is zero when all predictions are equal to the corresponding labels?
In the back-propogation algorithm, the error term is:
$$
E=\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2,
$$
where $\hat{y}_k$ is a vector of outputs from the network, $y_k$ is the vector of correct labels (...
- 305
7
votes
2
answers
12k
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 ...
- 305