# 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.

118 questions
Filter by
Sorted by
Tagged with
735 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 ...
14 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
31 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 ...
167 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 ...
114 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
85 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 ...
1 vote
795 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 ...
27 views

### How to prove that, for any graph $G$, the tree width of $G$ is $1$, if and only if $G$ is acyclic?

I am studying about CSPs, tree decomposition of a graph and tree width ($\text{TW}(G)$) of a graph - the smallest tree width of a tree decomposition. I encountered the following problem: Prove that ...
154 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 ...
1 vote
126 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 ...
766 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
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 ...
1 vote
177 views

98 views

358 views

122 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$...
1 vote
44 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, ...
1 vote
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 ...
174 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?
923 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? 