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
0 votes
0 answers
4 views

If two functions are close apart can I proof the difference of their empirical loss is also small?

I am trying to understand the proof of Theorem 3 in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke. Basically there exist atleast one $w_{L,e}$ in $\mathcal{...
user avatar
0 votes
0 answers
14 views

Derivation in paper Deep Neural Networks as Gaussian processes in ICLR 2018

I am trying to understand the derivation of the main equation in the seminal paper titled Deep Neural Networks as Gaussian processes (in ICLR 2018). I have asked this question in https://math....
user avatar
1 vote
1 answer
73 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\...
user avatar
  • 175
2 votes
1 answer
91 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. ...
user avatar
  • 71
0 votes
0 answers
53 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 ...
user avatar
1 vote
0 answers
144 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 ...
user avatar
1 vote
0 answers
97 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 ...
user avatar
  • 2,229
2 votes
0 answers
72 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 ...
user avatar
  • 43
0 votes
0 answers
23 views

proof of convergence for the random forest algorithm

I am looking for the proof of convergence of the random forest algorithm. A cursory google search shows many, but I do not understand which version (original?) of the algorithm this is. Can you kindly ...
user avatar
  • 175
0 votes
1 answer
35 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 ...
user avatar
2 votes
1 answer
94 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 ...
user avatar
  • 121
0 votes
1 answer
39 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_\...
user avatar
2 votes
1 answer
37 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 ...
user avatar
0 votes
0 answers
30 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 ...
user avatar
0 votes
0 answers
44 views

Why is the proof of convergence in the GAN paper not applicable practically?

This question is about generative adversarial networks and restricted to the research paper titled Generative Adversarial Nets. If I select a particular architecture of MLP as a generator and trained ...
user avatar
  • 2,977
3 votes
0 answers
48 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),\...
user avatar
5 votes
0 answers
67 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 $\...
user avatar
  • 175
2 votes
1 answer
89 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 ...
user avatar
0 votes
0 answers
20 views

How should we interpret "common coarsening" in this proof of the uniqueness of coarsest bisimulation?

On page 4 of this pdf in a theoretical RL course, we have a proof of the uniquness of the coarsest bisimulation. A bisimulation $\phi$ is a mapping from states $s \in\mathcal{S}$ to abstract states $\...
user avatar
  • 203
0 votes
0 answers
22 views

MDP - policy iteration convergence proof

I'm currently taking an Intro to AI course, and we've learned about MDP's and specifically about policy iteration. When we talked about the convergence of the policy iteration, it was mentioned that ...
user avatar
  • 1
3 votes
1 answer
101 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 ...
user avatar
  • 489
2 votes
2 answers
180 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{...
user avatar
  • 33k
1 vote
1 answer
54 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} ...
user avatar
  • 203
2 votes
1 answer
68 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$...
user avatar
  • 2,977
1 vote
0 answers
36 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, ...
user avatar
1 vote
0 answers
36 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 ...
user avatar
  • 216
2 votes
1 answer
66 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?
user avatar
  • 21
0 votes
1 answer
286 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?
user avatar
0 votes
0 answers
31 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 ...
user avatar
1 vote
1 answer
77 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_{\...
user avatar
2 votes
1 answer
122 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 ...
user avatar
6 votes
2 answers
538 views

Why is "-0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp())" in Pytorch equivalent to the KL?

I found this code for the loss function of a VAE: -0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp()) From this link: https://debuggercafe.com/getting-started-...
user avatar
3 votes
1 answer
296 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 ...
user avatar
4 votes
0 answers
73 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 ...
user avatar
2 votes
1 answer
110 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
user avatar
  • 23
2 votes
0 answers
33 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 \...
user avatar
  • 31
1 vote
1 answer
39 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 (...
user avatar
4 votes
2 answers
2k 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 ...
user avatar
5 votes
2 answers
396 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 ...
user avatar
3 votes
2 answers
1k 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?
user avatar
6 votes
1 answer
500 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. ...
user avatar
  • 33k
3 votes
2 answers
95 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 ...
user avatar
2 votes
0 answers
26 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?
user avatar
1 vote
0 answers
42 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_{...
user avatar
2 votes
2 answers
155 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 ...
user avatar
8 votes
2 answers
657 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} \...
user avatar
  • 179
7 votes
0 answers
200 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', ...
user avatar
2 votes
0 answers
54 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 ...
user avatar
  • 121
2 votes
2 answers
148 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 ...
user avatar
  • 352
1 vote
1 answer
90 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 ...
user avatar
  • 25