GPT 6 Astra Ultra attempt on Econ-19

Proof: For $\delta<1$ write every transition row as $P_{sa}=\delta\nu+(1-\delta)Q_{sa}$, with $Q_{sa}$ stochastic. Both a maximum and a minimum of finitely many affine functions change by a quantity between the smallest and largest changes of those functions. Consequently every coordinate of $Tx-Ty$ is between $\delta\nu(x-y)+(1-\delta)\min(x-y)$ and $\delta\nu(x-y)+(1-\delta)\max(x-y)$. This proves the inequality; when $\delta=1$, all rows equal $\nu$ and the same conclusion is immediate. On the space $H=\{x:x_1=0\}$, span is a norm. The map $F(x)=Tx-(Tx)_1\mathbf1$ maps $H$ into itself and is a contraction of factor $1-\delta$. Iterating it gives a Cauchy sequence: successive differences have summable geometric norm bounds. Completeness of finite-dimensional $H$ and continuity give a unique fixed point $h$, with $Th-h$ constant. Finally $\operatorname{sp}(h)\leq\operatorname{sp}(Th-T0)+\operatorname{sp}(T0) \leq(1-\delta)\operatorname{sp}(h)+2R$. ∎

Proof: Let $\mathcal F_t$ contain the history through the realized current action $a_t$, just before the next-state transition; then $r_t=r(s_t,a_t)$ is $\mathcal F_t$-measurable. When Max uses an attaining action, and Min uses any action or mixture, $r_t+\mathbb E[h(s_{t+1})\mid\mathcal F_t]-h(s_t)\geq\rho$. Put $D_{t+1}=h(s_{t+1})-\mathbb E[h(s_{t+1})\mid\mathcal F_t]$. Summing and rearranging yields \[ \sum_{t<T}r_t\geq T\rho+h(s_0)-h(s_T)+\sum_{t<T}D_{t+1}. \] The bounded martingale differences have average tending to zero almost surely. Here is an elementary justification. If $|D_t|\leq C$, orthogonality of martingale differences gives $\mathbb E[(\sum_{t<T}D_{t+1})^2]\leq TC^2$. At square times $T=j^2$, Chebyshev's inequality bounds the probability that the absolute average exceeds $\epsilon$ by $C^2/(j^2\epsilon^2)$. The series is summable, so Borel--Cantelli gives convergence at square times, simultaneously for rational positive $\epsilon$. Between $j^2$ and $(j+1)^2$ there are at most $2j+1$ increments, each bounded by $C$; divided by $j^2$ the additional magnitude tends to zero. This proves convergence at all times. Divide by $T$ and take the lower limit. Interchanging the roles gives the upper guarantee for Min. Bounded rewards allow taking expectations of these almost-sure bounds without exchanging expectation and a limit. For a general $x$, set $a=\min(Tx-x)$ and $b=\max(Tx-x)$; the same argument using greedy actions gives Max's lower guarantee $a$ and Min's upper guarantee $b$. Apply these to the common value already established. ∎

Proof: Apply span contraction $k$ times to $T0$ and $0$: $\operatorname{sp}(x_{k+1}-x_k)\leq(1-\delta)^k\operatorname{sp}(T0) \leq2R(1-\delta)^k$. To turn this into exact decision, an explicit separation bound is needed. Choose both greedy policies at the eigenvector $h$. Their stochastic matrix $P$ retains the minorization. The equations \[ \rho+h_s-\sum_tP_{st}h_t=r_s\quad(s\in[n]),\qquad h_1=0 \] form a square system in $\rho,h_2,\ldots,h_n$. It is nonsingular: a homogeneous solution $(\eta,z)$ has $z+\eta\mathbf1=Pz$; span contraction forces $z$ constant, and then $z_1=0$ and $\eta=0$. Let $D$ be the product of all input denominators. After multiplication by $D$ the system has integer coefficients bounded in absolute value by $D$. The determinant is a nonzero integer of absolute value at most $B=n!D^n$. Hence the reduced denominator of $\rho$ is at most $B$. If the input threshold has reduced positive denominator $b$, then $\rho\ne q$ implies $|\rho-q|\geq1/(Bb)$.

Iterate until interval width is strictly below $1/(Bb)$. If it lies strictly below $q$, answer no; if its lower endpoint is at least $q$, answer yes. If it contains $q$, every point of it is less than $1/(Bb)$ from $q$; therefore $\rho=q$ and the answer is yes. All endpoint conventions are covered by these cases. Since $\log B$ is polynomial in input length, $O(\delta^{-1}[\log(1+R)+\log B+\log b+1])$ iterations suffice (with one iteration handling $\delta=1$). Each iteration uses exact rational sums and maxima/minima. Common denominators can be taken as successive powers of $D$, so after $k$ iterations encoding length is $O(k\log D+\log(1+R)+k\log n)$, polynomial in the asserted parameters. ∎

Proof: Let $\epsilon=2^{-B}$, $B\geq2$, transition matrix $P=\left(\begin{smallmatrix}1-\epsilon&\epsilon\\ \epsilon&1-\epsilon\end{smallmatrix}\right)$ and reward vector $(0,1)$. The vector $h=(0,1/(2\epsilon))$ satisfies $r+Ph=h+(1/2)\mathbf1$. The pathwise certificate lemma therefore establishes average reward $1/2$ from both states. The minorization holds with $\delta=2\epsilon$ and uniform $\nu$. Here $x_{k+1}-x_k=P^kr$ and its span is $(1-2\epsilon)^k$. Bernoulli's inequality gives $(1-2\epsilon)^k\geq1-2k\epsilon>1/2$ for $k<2^{B-2}$. Thus the iteration count is exponential in this encoding. This is a lower bound for this iteration, not for all possible algorithms. ∎