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
4 votes
1 answer
238 views

In lemma 1 of the TRPO paper, why isn't the expectation over $s'∼P(s'|s,a)$?

In the Trust Region Policy Optimization paper, in Lemma 1 of Appendix A, I didn't quite understand the transition from (21) from (20). In going from (20) to (21), $A^\pi(s_t, a_t)$ is substituted with ...
4 votes
2 answers
297 views

What is the proof that the branch and bound algorithm 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 However, I haven't been able to find a ...
0 votes
0 answers
17 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 ...
6 votes
1 answer
113 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 $\...
5 votes
2 answers
162 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 ...
2 votes
1 answer
253 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 ...
1 vote
1 answer
102 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_{\...
3 votes
1 answer
769 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 ...
2 votes
0 answers
218 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
1 answer
198 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 ...
0 votes
0 answers
15 views

Proof of Difference in Return Between Two Policies

I am attempting to understand why Lemma 6.1 holds in this paper on reinforcement learning. I have two questions. First, when defining the value function V(s), why is there a leading (1-γ) term? In the ...
1 vote
1 answer
33 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 ...
7 votes
1 answer
3k 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
1 answer
152 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. ...
1 vote
1 answer
97 views

Is there a mathematical proof that a binary neural network can approximate any function with arbitrary accuracy?

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 ...
3 votes
1 answer
198 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. ...
1 vote
1 answer
897 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 ...
2 votes
1 answer
201 views

How is inequality 31 derived from equality 30 in lemma 2 of the "Trust Region Policy Optimization" paper?

In the Trust Region Policy Optimization paper, in Lemma 2 of Appendix A (p. 11), I didn't quite understand how inequality (31) is derived from equality (30), which is: $$\bar{A}(s) = P(a \neq \tilde{a}...
1 vote
0 answers
26 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 ...
3 votes
2 answers
369 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 ...
2 votes
1 answer
892 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 ...
1 vote
2 answers
153 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 ...
7 votes
2 answers
2k 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 ...
3 votes
1 answer
3k views

Why does the KL divergence not satisfy the triangle inequality?

The KL divergence is defined as $$D_{KL}=\sum_i p(x_i)log\left(\frac{p(x_i)}{q(x_i)}\right)$$ Why does $D_{KL}$ not satisfy the triangle inequality? Also, can't you make it satisfy the triangle ...
4 votes
1 answer
392 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 ...
2 votes
1 answer
126 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$...
6 votes
1 answer
381 views

Is this proof of $\epsilon$-greedy policy improvement correct?

The following paragraph about $\epsilon$-greedy policies can be found at the end of page 100, under section 5.4, of the book "Reinforcement Learning: An Introduction" by Richard Sutton and ...
1 vote
1 answer
192 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\...
2 votes
1 answer
3k 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
1 answer
444 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 letting the network keep ...
0 votes
0 answers
175 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 ...
8 votes
2 answers
4k 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 ...
10 votes
2 answers
4k 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} \...
1 vote
0 answers
223 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 ...
2 votes
0 answers
81 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 ...
2 votes
1 answer
2k views

Why does Q-learning converge to the optimal policy, even if the agent acts sub-optimally?

In Q-learning, during training, it doesn't matter how the agent selects actions. The algorithm always converges to the optimal policy. Why does this happen? What's the intuition?
29 votes
3 answers
14k 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 ...
1 vote
0 answers
169 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 ...
3 votes
1 answer
2k 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
0 answers
254 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 ...
6 votes
2 answers
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 ...
0 votes
1 answer
51 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 ...
2 votes
1 answer
58 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 ...
0 votes
1 answer
106 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_\...
0 votes
0 answers
31 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
104 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),\...
2 votes
0 answers
80 views

How to Prove This Inequality, Related to Generalization Error (Not Using Rademacher Complexity)?

This is an inequality on page 36 of the Foundations of Machine Learning by Mohri, but the author only states it without proof. $$ \mathbb{P}\left[\left|R(h)-\widehat{R}_{S}(h)\right|>\epsilon\right]...
3 votes
1 answer
340 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
147 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 ...
2 votes
2 answers
499 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 ...