Markov Decision Processes

Motivation

An American option may be exercised at any moment up to maturity, so pricing one is not an integration problem but a stopping problem: the holder must decide, at each date and in each state of the market, whether the payoff available now beats the option value of waiting. A perpetual American put pushes this to its limit — there is no maturity at all, so the horizon is unbounded and the problem has no terminal condition to induct backwards from. What replaces the terminal condition is a fixed point characterization, and the classical answer, going back to McKean (1965) and Merton (1973) in continuous time and to Cox, Ross and Rubinstein (1979) in the binomial model, is that the price is the smallest superharmonic majorant of the payoff.

Bäuerle and Rieder's Chapter 11 (Markov Decision Processes with Applications to Finance, Springer, 2011) derives this from their own general unbounded-horizon stopping theory rather than from stochastic analysis, and in the same chapter applies the bounded-horizon version to a problem from banking rather than trading: when should a bank cancel a credit line? The two halves share one mathematical shape — a stopping problem whose optimal policy turns out to be of threshold type — and this mission formalizes both, with the perpetual put as the goal.

Setting

The binomial model (§11.1). A stock moves from price $x$ to $xu$ with risk-neutral probability $q$ and to $xd$ with $1-q$, where $0 < d < u$, and the discount factor is $\beta \in (0,1]$. The defining relation of the risk-neutral measure,

$$\beta q u + \beta(1-q)d = 1,$$

is carried as a hypothesis of the model: it is what makes the discounted stock price a martingale, and the proofs use it directly.

The American put with strike $K$ pays $(K-x)^+$ when exercised. With $n$ periods to maturity its price satisfies the recursion $J_0(x) = (K-x)^+$ and

$$J_n(x) = \max\Big\{(K-x)^+,\ \beta\big(q J_{n-1}(xu) + (1-q)J_{n-1}(xd)\big)\Big\} =: \mathcal{T}J_{n-1}(x),$$

the maximum being "exercise now" against "hold". Proposition 11.1.2 describes the price $\pi_n(x) := J_{N-n}(x)$ at time $n$ of an option maturing at $N$: it is continuous in $x$, decreasing in $n$, and — the part that carries the argument — $x \mapsto \pi_n(x) + x$ is increasing, even though $\pi_n$ itself decreases in $x$. That single reformulation, obtained by adding $x$ to both sides of the recursion and using the risk-neutral relation, is what yields the threshold structure: there are exercise boundaries $K =: x_N^* \ge x_{N-1}^* \ge \dots \ge x_0^* \ge 0$ with $\tau^* = \inf\{n \le N \mid X_n \le x_n^*\}$ optimal. Exercise when the stock falls far enough, and the boundary rises as maturity approaches.

The perpetual put (Theorem 11.1.3, the goal). With no expiration date the price at time zero is a supremum over all stopping times, $\tau \le \infty$ included:

$$P(x) := \sup_{\tau \le \infty} \mathbb{E}^{\mathbb{Q}}_x\big[\beta^\tau (K - S_\tau)\big],$$

with the stopping reward set to zero on $\{\tau = \infty\}$. The theorem says four things: $P$ is the limit of the finite-maturity prices $J_n$; $P$ solves $\mathcal{T}P = P$ and satisfies $0 \le P \le K$; $P$ is the smallest superharmonic function majorizing $(K-x)^+$; and, if the value $J_{f^*}$ of the exercise-region policy dominates $\mathcal{T}J_{f^*}$, then $P$ equals that value and $\tau^* = \inf\{n \mid X_n \in E^*\}$, the hitting time of $E^* = \{x \mid P(x) = (K-x)^+\}$, is optimal.

The conditional in part d) is the book's own and is not decoration: without it the exercise region need not deliver an optimal stopping time, and the unconditional version is a different, false statement. The boundedness $0 \le P \le K$ in b) is likewise a genuine claim rather than a side remark — the fixed point equation alone admits other solutions, and it is boundedness together with minimality that pins $P$ down among them.

Credit granting (§11.2). A bank holds a credit contract of maximal duration $N$. Each period it observes a rating class $x_n$ evolving as a Markov process $Q^X$, and chooses to extend — earning $c(x)$ — or to cancel, ending the contract. The value iteration is $J_n(x) = \max\{0,\ c(x) + \beta\int J_{n-1}\,dQ^X(\cdot|x)\}$. Under two structural assumptions — $c$ increasing, and $Q^X$ stochastically monotone, so that a better-rated borrower stays better-rated — Theorem 11.2.1 gives the same shape of answer as the option: cancel exactly when the rating falls below a threshold $x_n^*$, and those thresholds rise as the remaining duration shortens, since a marginal borrower is no longer worth keeping when there is little time left to recover.

Theorem 11.2.2 repeats this when the borrower is not rated at all. The bank has only a prior $\mu_0$ on the repayment probability and one signal per period; the state $(s,n)$ records $s$ positive signals out of $n$, and the expected repayment probability is the posterior mean $q(s,n)$. Monotonicity here is for the order of p. 342 — more positive signals and fewer negative ones — and not the coordinatewise order, under which the claim would be false: an extra signal that is negative makes the state worse.

What is being asked

Formalize Theorem 11.1.3 in full, all four parts: the limit identification, the fixed point equation with its bounds, the minimality among superharmonic majorants, and the conditional optimality of the exercise-region stopping time. The three milestones are Proposition 11.1.2, the finite-horizon put whose threshold structure the perpetual case specializes, and the two credit granting theorems, which run the same bounded-horizon argument on a different model.

The stopping-time apparatus is built rather than assumed: the stock path, the law $\mathbb{Q}$ pinned by its finite-dimensional distributions, stopping times valued in $\mathbb{N}\cup\{\infty\}$, and the reward vanishing at $\infty$. Part a) of the goal is the identification of the supremum with $\lim_n J_n$, so carrying $P$ as an abstract function would make the theorem vacuous.