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.

36 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
272 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', ...
sirfroggy's user avatar
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 $\...
MMM's user avatar
  • 185
4 votes
0 answers
80 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 ...
EmmanuelMess's user avatar
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 ...
A Das's user avatar
  • 141
4 votes
2 answers
298 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 ...
Gooby's user avatar
  • 351
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),\...
joesph chan's user avatar
3 votes
1 answer
416 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 ...
Jesus is Lord's user avatar
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 ...
XXX's user avatar
  • 143
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 ...
MoneyBall's user avatar
  • 121
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 \...
Phil's user avatar
  • 31
2 votes
0 answers
31 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?
hakiki_makato's user avatar
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 ...
Igor's user avatar
  • 121
2 votes
0 answers
450 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 ...
sirKris van Dela's user avatar
2 votes
0 answers
200 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....
Yamar69's user avatar
  • 131
2 votes
0 answers
203 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 ...
j200932's user avatar
  • 181
2 votes
0 answers
942 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 ...
j200932's user avatar
  • 181
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]...
j200932's user avatar
  • 181
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}\...
j200932's user avatar
  • 181
2 votes
0 answers
63 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
fool's user avatar
  • 203
2 votes
1 answer
147 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 ...
user8714896's user avatar
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 ...
SHASHANK RANJAN's user avatar
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 ...
stats_noob's user avatar
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 ...
mshlis's user avatar
  • 2,359
1 vote
0 answers
45 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, ...
E. Ginzburg's user avatar
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 ...
Marcus's user avatar
  • 226
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_{\...
quest ions's user avatar
1 vote
0 answers
100 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_{...
Swakshar Deb's user avatar
1 vote
0 answers
275 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 ...
goldilocks's user avatar
1 vote
0 answers
123 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 ...
KaneM's user avatar
  • 309
1 vote
0 answers
69 views

Proof of Correctness of Monte Carlo Tree Search

I'm trying to write the proof of correctness of Monte Carlo Tree Search. Any help would be really appreciated.
ATidedHumour's user avatar
1 vote
0 answers
92 views

Understanding the proof of theorem 2.1 from the paper "Efficient reductions for imitation learning"

I am trying to understand the proof of theorem 2.1 from this paper: Ross, Stéphane, and Drew Bagnell. "Efficient reductions for imitation learning." Proceedings of the thirteenth international ...
MrYouMath's user avatar
  • 255
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 ...
Thomas Nguyen's user avatar
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 ...
Nikhil Sridhar's user avatar
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 ...
陳文澤's user avatar
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 ...
Anony Mous's user avatar
0 votes
0 answers
49 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 ...
quest ions's user avatar