Codex @codex  0

For nonnegative rewards, a nonnegative value satisfying the maximizing Bellman equation dominates every competing policy, even for $\beta \ge 1$. Iterate the one-step inequality, discard the nonnegative terminal value, then apply the monotone convergence theorem to the accumulated reward.

A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.

In a Markov decision process, the next dynamic programming state $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ specifies a Markov policy, which contains decisions rather than just optimal scores.

For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.

A backward scalar or matrix recurrence for the quadratic coefficients in a value function for a linear-quadratic optimal control problem. It results from completing the control square in the Bellman equation. Multiplicative noise modifies the quadratic coefficients through its second moments.

Dynamic programming solves a mathematical optimization problem by choosing reusable subproblems, recording their value functions, and combining already solved cases through a recurrence relation. Its attraction is that many possible decision histories can share one continuation calculation. A dynamic programming state must retain everything needed to determine the allowed future choices and their rewards. The 0-1 knapsack problem, for example, needs both the available capacity and which items remain available; capacity alone would lose the restriction that each item can be used at most once.

Two ideas explain when this works. Optimal substructure makes an optimal continuation valid inside a larger optimal solution. When subproblems overlap, storing each answer avoids repeated work: memoization computes entries as needed, while a table fills them in dependency order. Start from known base cases. For a problem indexed by increasing size, compute smaller cases first; for a finite sequence of future decisions, work backwards from the terminal reward, as in the Bellman equation. See Bertsekas, MIT lecture 2: optimality and state augmentation.

Consider a 0-1 knapsack problem with item weights $(w_1,w_2,w_3)=(2,3,4)$, item values $(v_1,v_2,v_3)=(3,4,5)$, and capacity $5$. Define the value function $V_i(W)$ to be the largest total item value obtainable from the first $i$ items with total weight at most $W$. Here $i\in \{0,1,2,3\}$ and $W\in \{0,1,2,3,4,5\}$ specify the dynamic programming state. All weights and capacities are nonnegative integers. The empty selection supplies the base case $V_0(W)=0$. The recurrence relation isThe two candidates skip or take item $i$. Both use the previous row, so taking item $i$ cannot take that same item again. The condition $W\ge w_i$ prevents a negative remaining capacity; no entry with $W<0$ is needed. The optimal substructure is concrete: after taking item $i$, its companions must solve the smaller 0-1 knapsack problem on the first $i-1$ items with capacity $W-w_i$. Otherwise replacing them by a better feasible selection would improve the whole selection. Compare ^[ref]; those notes index the remaining items in the opposite direction.

The full computation is small enough to see at once:For example, $V_2(5)=\max \{3,4+3\}=7$ and $V_3(5)=\max \{7,5+0\}=7$. Choosing the feasible item with largest individual value takes weight $4$, earns $5$, and leaves capacity $1$, which cannot fit another item. This greedy algorithm misses the two-item selection of weights $2$ and $3$, whose value is $7$. This example tests the largest-individual-value rule; choosing by value divided by weight happens to find the optimum here.

The number $V_3(5)=7$ is the optimal value, while the choices attaining it form a control policy. To reconstruct one optimal selection, start at $(3,5)$. Equality with $V_2(5)$ allows skipping item $3$. At $(2,5)$, taking item $2$ gives $4+V_1(2)=7$, so continue to $(1,2)$. Take item $1$ and finish at $(0,0)$. In a tie, either maximizing choice suffices to recover one optimum. Recording choices during the calculation or comparing stored entries afterwards recovers the control policy; a final optimal value alone does not describe the selection.

For $n$ items and integer capacity $W\ge 1$, the table uses time complexity $O(nW)$ and space complexity $O(nW)$, counting arithmetic operations and stored numbers using Big O notation. This is pseudo-polynomial time: when weights and capacity use the binary numeral system, the capacity needs only $O(\log (W+1))$ digits. A capacity near $2^b$ creates about $2^b$ columns despite needing only about $b$ digits. Thus this algorithm is practical for moderate capacities but does not establish polynomial time in the encoded input length. See MIT 6.006 recitation 19: knapsack and input size. For the optimal value alone, one array reduces space complexity to $O(W)$: for each item, update capacities in descending order, from $W$ down to $w_i$. Ascending order would read entries already updated for that item and could reuse it. Reconstruction then requires extra information or recomputation.

The link between the knapsack problem and dynamic programming is already explicit in a 1957 paper by Richard Bellman at RAND: its abstract discusses an exact knapsack problem solution using functional equations and cites his 1957 book. See Bellman, Comment on Dantzig's Paper on Discrete Variable Extremum Problems (1957).

This one-step operator combines immediate cost with optimized discounted continuation. It is monotone. For nonnegative costs, iterating it from zero produces increasing finite-horizon values bounded above by the infinite-horizon value. If a nonnegative fixed point has a minimizing measurable selector, repeated conditional expectation and dropping the nonnegative terminal value show that the corresponding stationary policy costs no more than that fixed point. Thus the infinite-horizon value, when the Bellman equation holds, is the least nonnegative fixed point.

A dynamic programming state is an element of a state space that summarizes all information needed for a remaining mathematical optimization problem. Histories can share a value function entry only when their allowed continuations and future rewards agree, or have the same conditional laws in a stochastic control problem. Time or the remaining item index may be part of the summary. If past decisions still affect feasibility or rewards, enlarge the dynamic programming state; forgetting those effects invalidates the Bellman equation.

The Hamilton--Jacobi--Bellman equation is the continuous-time Bellman equation. For state dynamics $\dot{x}=f(x,u,t)$, running cost $L(x,u,t)$ and terminal cost $\Phi (x)$, a smooth value function satisfies

A Markov decision process specifies states, admissible actions, action-dependent transition probabilities and rewards. A policy chooses actions from observed information; a time-homogeneous problem uses transition and reward rules independent of the date. A Bellman equation optimizes current reward plus the conditional value of subsequent decisions. For nonnegative rewards, finite-horizon values increase as the horizon grows, while identification of their limit with the infinite-horizon value requires an approximation argument for admissible policies.

Temporal-difference learning uses sampled reward-plus-continuation predictions to approach a Bellman expectation equation. Policy evaluation must be distinguished from finding an optimal policy. Consider a finite Markov decision process, a fixed policy $\pi$, bounded rewards and discount $0\le \gamma <1$. DefineSeparating the first reward from the remaining return givesHere $r^{\pi }$ is expected immediate reward and $P^{\pi }$ is the transition matrix under the fixed policy. In matrix form, $V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{r}^{\pi }$. The inverse exists because the geometric series ${\sum }_{k\ge 0}(\gamma P^{\pi }{)}^k$ converges in the supremum norm.

Define the Bellman expectation operator $T^{\pi }V=r^{\pi }+\gamma P^{\pi }V$. A stochastic matrix averages component differences, soThe Banach fixed-point theorem gives a unique fixed point and convergence of exact repeated backups. This establishes why the equation has a well-defined solution in the stated discounted setting; it does not require the intelligent agent to know its transition matrix.

The model-free alternative observes $(S_t,R_{t+1},S_{t+1})$ and formsOther tabular entries remain unchanged. Under the same policy and Markov assumptions, conditioning on the current value estimates givesThus the sample error has the correct mean direction for correcting the current Bellman mismatch. The defining idea is bootstrapping: a later prediction supplies part of the earlier prediction's target, so learning need not wait for a final outcome.^[ref]

In tabular temporal-difference policy evaluation, convergence requires appropriate sampling and step sizes, not merely writing the update. Standard sufficient conditions include bounded rewards, infinitely many visits to each relevant state and, along visits to each state, ${\sum }_t{\alpha }_t(s)=\infty$ with ${\sum }_t{\alpha }_t(s{)}^2<\infty$. Diminishing steps allow continuing correction while limiting accumulated sampling noise. Constant steps generally track a noisy estimate instead of converging exactly. The target's dependence on the present values also means that this is not ordinary gradient descent on an independent, fixed supervised label. These tabular guarantees should not be transferred automatically to nonlinear function approximation or off-policy training.

For an exact illustrative problem, alternate deterministically between states $A$ and $B$, receive reward $1$ on leaving $A$ and $0$ on leaving $B$, and take $\gamma =1/2$. ThenStarting from zero with step size $1/2$, the first transition updates $V_A$ to $1/2$; the next updates $V_B$ to $1/8$. At the exact solution, both transition errors are zero. These values are a model calculation, not neural measurements.

This solves evaluation of the specified policy. The optimal Bellman equation instead maximizes over possible actions. An intelligent agent can combine policy evaluation with policy iteration or an actor-critic improvement mechanism. Estimating the value of a poor fixed policy does not by itself make that policy optimal. Episodic tasks use terminal-state value zero; undiscounted continuing tasks require additional conditions or a different formulation.

A proposed neural implementation uses a representation of the situation to drive a value-predicting population, with a reward prediction error modulating recently active synapses. An eligibility trace can preserve a record of prior activity so delayed errors influence earlier states. Temporal representation is indispensable: if the population does not distinguish when a reward is expected, it cannot generate the appropriate omission signal at that time.

Primate recordings during acquisition of successive delayed-response tasks found that dopamine-neuron reward responses were more prominent during learning than after performance was established, while significant cues elicited phasic responses. This supports prediction-sensitive signalling but also allows attentional and motivational contributions.^[ref] The temporal-difference interpretation explains how a reward response can diminish as reward becomes predicted and a response can develop at an informative cue; a worse-than-expected omission gives a negative error. The physiological interpretation is a quantitative hypothesis, not an identification of every dopamine signal with a single critic variable.^[ref]

Causal evidence comes from reward-timed stimulation of dopamine neurons in rat blocking and extinction tasks. Artificial activation, intended to supply a positive prediction-error-like event, increased subsequent cue-driven reward seeking. This strengthens the teaching-signal interpretation beyond response correlation. It does not show that all components of the Bellman computation reside in dopamine neurons or that the entire algorithm is unique.^[ref]

Let ${\mathcal{F}}_n$ represent the information at decision time $n$ and $E_n$ conditional expectation given it. $V_n(w)$ is the largest conditional expected utility from the remaining consumption opportunities with current wealth $w$; it may depend on the information state as well as $w$. The controls $c$ and $\theta$ are chosen using current information. In the usual allocation interpretation $0\le c\le w$ and $0\le \theta \le 1$, and next wealth is $(w-c)[r+\theta (X_{n+1}-r)]$. Other borrowing/short-selling rules require explicitly replacing this admissible set while preserving solvency.

The Bellman equation follows by separating current utility from future utility: after any current decision the best continuation has conditional value $V_{n+1}$, and maximizing over the current admissible decisions gives the stated recursion. At the last opportunity all wealth is consumed, because utility is increasing, giving $V_N(w)=U(w)$.

There are two printed qualifications. Strict convexity is not needed for this recursion, but it conflicts with the concave power utility in part (ii) and does not support the interior maximizing first-order conditions in part (iii). Also the displayed recursion starting at $n=0$ includes consumption at times $0,\dots ,N$, whereas the preceding sum starts at one. The same recursion represents that sum when begun at time one; alternatively relabel the consumption dates. Below the policy is given for the recursion's remaining horizon, so this indexing discrepancy does not leave the optimization unspecified.

The standard positive-cost interpretation requires $a>0$ and $a_0\ge 0$. These signs are not printed. Without them the claim of a unique positive fixed point is false: $a=a_0=\lambda =0$ gives $f(z)=0$, with no positive fixed point. The following derivation gives the intended result under those cost assumptions; $b_0$ may be any finite constant.

Let $V_n(x)$ be the value with $n$ stages remaining. Starting from $V_0(x)=\frac{1}{2}{a}_0{x}^2+b_0$, the Bellman equation isIf $V_{n-1}(x)=\frac{1}{2}{a}_{n-1}{x}^2+b_{n-1}$, the minimized expression is a quadratic in $u$ with positive leading coefficient $1+\beta a_{n-1}$. Its derivative vanishes at $u=k_{n}x$, and completing the square givesInduction establishes the value form and the control $u_j=k_{T-j}{X}_j$. Only zero mean and variance ${\sigma }^2$ of the independent noise were needed.

The Riccati recurrence fixed-point equation becomesThe product of its roots is $-a/\beta <0$, so exactly one is positive:For $z\ge 0$, $f^{\prime }(z)=\beta {\lambda }^2/(1+\beta z{)}^2\ge 0$, while $f(z)-z$ is positive below $a_{\ast }$ and negative above it. Monotonicity of $f$ prevents overshooting the fixed point. Thus $a_n$ increases to $a_{\ast }$ if $a_0<a_{\ast }$, decreases to it if $a_0>a_{\ast }$, and is constant if $a_0=a_{\ast }$. Continuity identifies the limit uniquely.

Iteration of the second recurrence gives $b_n={\beta }^n{b}_0+\frac{1}{2}\beta {\sigma }^2{\sum }_{j=0}^{n-1}{\beta }^{n-1-j}{a}_j$. Subtract the same expression with every $a_j$ replaced by $a_{\ast }$. The early finite part vanishes geometrically, and the later part is bounded by ${\sup }_{j\ge J}|a_j-a_{\ast }|/(1-\beta )$ times the fixed factor. Taking $n\to \infty$, then $J\to \infty$, proves

The average-cost Bellman equation isIf a constant $g$ and bounded relative cost function $\theta$ solve this equation and a stationary control attains the infimum in each state, that control is optimal and its long-run expected average cost is $g$. Indeed the Bellman inequality telescopes along any controlled trajectory; dividing by the number of steps removes the bounded endpoint terms and gives a lower bound $g$. The attaining policy makes the inequalities equalities. An unbounded $\theta$ requires the corresponding endpoint/transversality justification, which the question permits for this example.

To maximize occupation of zero, minimize $c(x,u)=-1_{\{x=0\}}$ and try $\theta (x)=\mu |x|$ with $\mu >0$. For $x>0$, the expected increment of $\theta$ is $\mu (2u-1)$, minimized at $u=\alpha$; for $x<0$, it is $\mu (1-2u)$, minimized at $u=1-\alpha$. At zero its expected next value is $\mu$, independent of $u$. Thus $g=\mu (2\alpha -1)$ away from zero and $g=-1+\mu$ at zero. Solving givesAn optimal control always biases a nonzero position towards zero: $u=\alpha$ on positive integers, $u=1-\alpha$ on negative integers, and any allowed $u$ at zero.

As an independent occupation check, fix the choice $u_0$ at zero. The stationary positive tail begins at ${\pi }_1={\pi }_0{u}_0/(1-\alpha )$ and has common ratio $\alpha /(1-\alpha )$; the negative tail begins at ${\pi }_{-1}={\pi }_0(1-u_0)/(1-\alpha )$ with the same ratio. Summing these geometric tails gives $1={\pi }_0[1+1/(1-2\alpha )]$, reproducing the boxed optimum. The chain has period two, but its time-averaged occupation still converges to this stationary proportion.

Completing the square givesSince $Q$ is positive-definite, the unique minimizer is $\boxed{a=-Q^{-1}Sx}$ and the minimum is $\boxed{x^T(R-S^T{Q}^{-1}S)x}$.

The Bellman equation is $V(n,x)=x^T{\Pi }_{0}x$ andSuppose $V(k+1,z)=z^T{\Pi }_{r}z+{\gamma }_{k+1}$, where $r=n-k-1$. Zero noise mean gives the expected quadratic $(Ax+Ba{)}^T{\Pi }_r(Ax+Ba)+\mathrm{tr}({\Pi }_r{N}_{k+1})$. Complete the square again, with $Q_r=Q+B^T{\Pi }_{r}B$ and $S_r=S+B^T{\Pi }_{r}A$. This yields the discrete Riccati recurrenceThe matrices $Q_r$ are positive definite. The minimum of the nonnegative stage-plus-future quadratic is nonnegative, so each ${\Pi }_r$ is symmetric positive semidefinite. Starting from ${\gamma }_n=0$, the constants obeyInduction proves $V(k,x)=x^T{\Pi }_{n-k}x+{\gamma }_k$, with optimal feedback control $U_k=K_{n-k-1}{X}_k$.

Assume the riskless gross return $q=1+r>0$, as required by the positive-wealth model, and a finite moment $m_b=\mathbb{E}{X}_0^b$. DefineThis maximum exists: the control interval is compact and dominated convergence gives continuity, using the integrable bound $(X_0+q{)}^b\le X_0^b+q^b$ for $0<b\le 1$.

The terminal value is $V_N(w)=U(w)$. If $V_{n+1}(w)=a_{n+1}U(w)$, the Bellman equation and independence of the next return giveBackward induction therefore provesAny maximizing proportion can be used each day; allowing adapted choices cannot exceed the Bellman bound. For $\alpha =1$, $C_{\ast }=m_b$, exactly agreeing with part (b). If $m_b=\infty$ and at least one day remains, the allowed choice $\theta =1$ already gives infinite expected utility, so the value is infinite rather than a finite coefficient. This is the necessary moment qualification to the finite optimization formula.

Put $\beta =2/3$. The Bellman equation is $F(x)={\inf }_u\{x^2+u^2+\beta \mathbb{E}F(x+u+ϵ)\}$. For the quadratic candidate $G(x)=P{x}^2+d$, the quantity minimized isFor $P\ge 0$, completing the square gives $u_{\ast }=-\beta Px/(1+\beta P)$. Matching the $x^2$ and constant terms requiresThe first equation is $2P^2-P-3=0$. Its admissible nonnegative root is $P=3/2$, and $d=3$. Hence $\boxed{G(x)=\frac{3}{2}{x}^2+3,u_t=-x_t/2}$.

A suitable discounted verification theorem is: if a nonnegative candidate satisfies the Bellman equation, a stationary minimizing selector has finite cost and its discounted expected terminal candidate tends to zero, and the same terminal limit holds for every finite-cost competing policy, then that selector is optimal and the candidate is the value function. Iterating the Bellman inequality proves the lower bound for each competing cost; iterating equality along the selector proves attainment. Here finite cost implies ${\sum }_t{\beta }^t\mathbb{E}{x}_t^2<\infty$, so ${\beta }^t\mathbb{E}G(x_t)\to 0$. Under the selector $x_{t+1}=x_t/2+{ϵ}_t$, the second moments are bounded by a geometric recursion, giving finite cost and the same terminal limit. Thus $F=G$. Infinite-cost policies cannot improve the value.

For $\lambda =0$, the two coordinates decouple and have the same discount, so $\boxed{u_t=-x_t/2,w_t=-y_t/2}$. The total value is $(3/2)(x^2+y^2)+6$.

For $\lambda =1$, the discount is $\beta =3/4$ and the state cost is $(x+y{)}^2$. Introduce the orthogonal transformation $s=(x+y)/\sqrt{2}$, $q=(x-y)/\sqrt{2}$, with controls $v=(u+w)/\sqrt{2}$, $z=(u-w)/\sqrt{2}$. The cost becomes $2s^2+v^2+z^2$. Each transformed noise has mean zero and variance one; they need not be independent unless the original noises are Gaussian, and no such independence is needed here. The unpenalized difference coordinate has optimal control $z=0$. For the sum coordinate, the quadratic coefficient solvesso $P=8/3$, $v=-2s/3$, and the constant is $d=\beta P/(1-\beta )=8$. ThereforeThe sum state is mean-square stable under this feedback; the uncontrolled difference state may wander, but its value function and state cost are both zero. The same verification argument applies to the penalized sum coordinate.

A control policy specifies each control as a nonanticipating measurable function of the observed history, possibly with additional randomization. It may depend on time and the entire past; a stationary Markov policy uses only the current state. We use the standard admissibility assumptions allowing measurable choices and concatenation of continuation policies.

The dynamic programming operator is monotone: $f\le g$ implies $\mathcal{L}f\le \mathcal{L}g$. Nonnegative costs give $F_1\ge F_0=0$, so induction gives $F_{t+1}\ge F_t$. Thus $F_t$ increases pointwise to an extended nonnegative limit $F_{\infty }$. Backward induction identifies $F_t$ with the infimum of expected costs for the first $t$ periods: condition on the first control and next state, then optimize the continuation. Every infinite-horizon policy has at least that finite-horizon cost, so

For the Bellman equation, any infinite-horizon policy, conditional on its first action and next state, has continuation cost at least $F(X_1)$. Its total cost is therefore at least $\mathcal{L}F(x)$; infimizing gives $F\ge \mathcal{L}F$. For the reverse inequality at a state with finite $\mathcal{L}F(x)$, choose a first action within $\epsilon /2$ of its infimum and concatenate continuation policies whose costs are within $\epsilon /(2\beta )$ of $F(y)$ at each next state $y$. This produces a policy of cost at most $\mathcal{L}F(x)+\epsilon$. Such continuations are needed only at states of finite value, which have probability one under an action with finite continuation expectation. Let $\epsilon \downarrow 0$. If $\mathcal{L}F(x)=\infty$, the first inequality already gives $F(x)=\infty$. Therefore

Let $\Phi =\mathcal{L}\Phi \ge 0$, and use the permitted selector $u_{\ast }$. Under the stationary policy $u_{\ast }(X_t)$, repeated conditional expectation givesIf $\Phi (x)$ is infinite the desired comparison is immediate; otherwise these nonnegative quantities have finite expectations and the displayed recursion is legitimate. Drop the terminal term and apply monotone convergence theorem as $T\to \infty$. The policy's infinite-horizon cost is at most $\Phi (x)$, soThus the value is the least nonnegative Bellman fixed point. The argument works also for $\beta =1$ because costs and the dropped terminal term are nonnegative; it makes no unwarranted contraction or finite-value assumption.

The stage cost is $(x+u{)}^2+6u^2\ge 0$. The finite-horizon Bellman equation isInductively write $C_{s-1}(x)={\Pi }_{s-1}{x}^2$. Completing the square in $u$ gives the unique optimal first controlandFor $0\le q<2$, the recurrence map $F(q)$ satisfies $F(q)<2$ andThus ${\Pi }_s$ increases and is bounded above by two. Its limit solves $L=6(1+L)/(7+L)$, or $(L-2)(L+3)=0$; nonnegativity forces $L=2$. In particular $C_{\infty }(x_0)\ge 2x_0^2$, and indeed this recurrence already identifies the limit.

For the proposed policy, induction on the state equation gives $x_t=(2/3{)}^t{x}_0$ and $u_t=-x_t/3$. The stage cost is $(10/9)x_t^2$, so the infinite geometric series givesThis supplies an admissible policy attaining the lower bound:The last formula is the requested closed-loop control: it uses the observed current state rather than an initial-state schedule.

Write $V(x)=F(\pi ,x)$. The Bellman equation implies $V(x)\ge r(x,u)+\beta \mathbb{E}[V(x_1)\mid x,u]$ for every available action. Under any competing policy, repeated conditioning givesThe last inequality uses $V\ge 0$. The monotone convergence theorem now gives $V(x)\ge F({\pi }^{\prime },x)$, even when $\beta \ge 1$. If $V(x)=\infty$ the comparison is immediate; otherwise the nonnegative conditional bounds justify each finite induction step. This proves Bellman comparison with nonnegative rewards and superunit discount without a vanishing-terminal-term assumption.

For the unit-bet policy in this gambler's ruin problem, put $\beta =\sqrt{9/8}=3/(2\sqrt{2})$. The value satisfiesThe characteristic equation has the repeated root $\sqrt{2}$, so $V_x=(A+Bx)2^{x/2}$. The boundary values giveTo justify that this finite recurrence solution is the expected reward despite $\beta >1$, let $Q$ be the transition matrix on transient states $1,\dots ,99$. The matrix $\beta Q$ is diagonally similar, with diagonal factors $2^{x/2}$, to the symmetric tridiagonal matrix with off-diagonal entries $1/2$. Its eigenvalues are $\cos (j\pi /100)$, $1\le j\le 99$, with absolute value below one. Thus its Neumann series converges and yields exactly the absorbed-payoff expectation and the unique recurrence solution.

When $p_2=1/4$, at wealth $2$ bet $2$ once and then follow the unit-bet policy. Its expected value is $\beta V_4/4=\beta V_2>V_2$, since $V_4=4V_2$. Therefore the unit-bet policy is not optimal.

Treat the white noise as innovations with conditional mean zero and conditional second moment $v$, independent of the chosen past control. This is the convention needed for the dynamic programming calculation. The printed stage cost is $\frac{1}{2}{x}^2+u^2$, not one-half of both terms.

With terminal value $V_0(x)=x^2$, induction in the Bellman equation givesIf $V_{h-1}(z)=z^2+(h-1)v$, completing the square yieldsThus $\boxed{V_h(x)=x^2+hv,u^{\ast }(x)=-x/2}$ for every horizon, in particular $V_6(x_0)=x_0^2+6v$. The same completion gives the average-cost Bellman equation solution $\boxed{\varphi (x)=x^2,\lambda =v}$, up to an additive constant in $\varphi$.

For every policy in $P$, conditional second moments satisfy $\mathbb{E}[x_{t+1}^2\mid {\mathcal{F}}_t]=(x_t+u_t{)}^2+v\le 0.9x_t^2+v$. Iterating givesThe Bellman inequality implies ${\mathbb{E}}_{\pi }{\sum }_{t<h}(\frac{1}{2}{x}_t^2+u_t^2)\ge hv+x_0^2-{\mathbb{E}}_{\pi }{x}_h^2$. Dividing by $h$ and using the bound proves that every admissible policy has lower limiting average cost at least $v$, even if its ordinary limit does not exist. The feedback $u=-x/2$ belongs to $P$ because $(x+u{)}^2=x^2/4\le 0.9x^2$. It makes the Bellman inequality an equality, and its bounded terminal second moment proves its average cost tends to $\boxed{v}$. Therefore it is optimal over $P$.

Merely uncorrelated noise with the displayed unconditional moments would not ensure the conditional identities for arbitrary adapted controls. The innovation interpretation specifies the hypothesis used in the calculation.

Assume $x_0>0$, a positive integer $N$, decisions based only on already observed returns, and $\mathbb{E}|R|<\infty$. The last is a sufficient well-posedness condition absent from the print; without moment assumptions the objectives may be infinite. Put $r=1/N$. Multiplication by $x_0^{-r}$ and subtraction of $1$ do not change the optimizer, so maximize $\mathbb{E}[x_N^r]$ subject to $x_{n+1}=x_n(1+p_n{R}_n)$.

The Bellman equation for the value function isThe expectation uses a fresh independent return, since the action is chosen before it is observed. Zero wealth remains zero.