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.

122 questions
Filter by
Sorted by
Tagged with
52 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. ...
• 113
1 vote
21 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
357 views

• 185
208 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
184 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
231 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 ...
• 329
1 vote
174 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,369
292 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
57 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
265 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
134 views

• 31
1 vote
293 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 (...
• 297
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 ...
• 297
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 ...