Numerical Derivatives and Optimization in Nested Fixed-Point Models

Why Numerical Accuracy Matters in Nested Fixed-Point Estimation

In nested fixed-point estimation, each proposed parameter vector requires solving a dynamic programming problem before the likelihood can be evaluated. Optimization then compares likelihoods at nearby parameter values. If the inner value-function calculation is inaccurate, those comparisons can be noisy: an optimizer may mistake numerical error for a meaningful improvement or a gradient direction. This tutorial develops two ways to calculate likelihood gradients and shows how to tell whether the inner solution is accurate enough to support them.

Consider a finite-state choice model with states \(s\), actions \(a\), discount factor \(\beta\), and parameter vector \(\theta\). Let \(u_a(s;\theta)\) be the deterministic current payoff and \(P_a(s,s')\) the probability of moving to state \(s'\) after choosing \(a\) in state \(s\). Assume \(0\leq\beta<1\), known transitions that do not depend on \(\theta\), and independent Type I extreme-value choice shocks with the location normalized so that their integrated value is the log-sum-exp. The observed states and choices are treated as given when forming the conditional choice likelihood.

The value function is “nested” inside the likelihood: evaluating \(\ell(\theta)\) requires first solving its fixed-point equation. The definitions above assume the transition probabilities are fixed with respect to \(\theta\). If a particular model estimates transition parameters, derivatives of \(P_a\) and any transition likelihood contributions must also be included; they are not part of the formulas developed here.

Finite-Difference Gradients

The direct numerical approach evaluates the solved likelihood at small perturbations of each parameter. For parameter \(\theta_j\), a central finite difference is

where \(e_j\) is a vector with a one in coordinate \(j\) and zeros elsewhere, and \(h>0\) is the step size. Each likelihood in the numerator must be computed using a value function solved at that perturbed parameter vector. Reusing the unperturbed value function without updating it generally does not calculate the derivative of the nested likelihood.

With an exact, sufficiently smooth likelihood, central differences have truncation error of order \(h^2\). But each likelihood evaluation is computed numerically. If its absolute error is at most \(\eta\), the resulting error in the difference quotient can be as large as \(\eta/h\): the two likelihood errors are subtracted and divided by \(2h\). Thus a very small step reduces truncation error but magnifies inner-solver error and floating-point error. A large step suppresses that noise but can make the finite difference a poor approximation to a local derivative.

Implicit Differentiation of the Fixed Point

Rather than perturbing and resolving the model for every parameter, one can differentiate the Bellman fixed-point equation. This gives a derivative that accounts directly for how a parameter changes both current payoffs and future values. Write \(V_\theta\) for the vector of derivatives of \(V\) with respect to one scalar parameter \(\theta_j\), and write \(u_{a,\theta}\) for the corresponding derivative of \(u_a\), holding \(V\) fixed.

To justify the result, differentiate \(V(s)=\log\sum_a\exp(Q_a(s))\). The derivative of log-sum-exp is a probability-weighted average, so

The first term is \(g(s)\), and the transition-weighted term is \(\beta\bar P V_\theta\), which gives the stated linear system. Since each row of \(\bar P\) sums to one, its maximum absolute row sum is one. Thus the maximum absolute row sum of \(\beta\bar P\) is \(\beta<1\); the inverse exists and is given by the convergent series \(I+\beta\bar P+(\beta\bar P)^2+\cdots\). This also shows why a parameter's effect on current payoffs propagates through future values.

Finally, differentiating the log choice probability gives the score contribution for observing action \(y\) in state \(s\):

Summing this expression over observations gives the likelihood gradient. For a vector of parameters, solve the corresponding system for each parameter coordinate, or solve for several right-hand sides together.

Diagnosing the Inner Solver

A stopping rule based only on the change between successive value iterates can be misleading. A more interpretable diagnostic is the Bellman residual. For an approximate value vector \(\widetilde V\), define \(r=\|T_\theta(\widetilde V)-\widetilde V\|_\infty\), where \(T_\theta\) is the Bellman operator and \(\|\cdot\|_\infty\) is the largest absolute state-specific error.

Indeed, using \(V=T_\theta(V)\) and the contraction property,

Rearranging gives the bound. When \(\beta\) is near one, even a small residual can permit a noticeably larger value error. That error can affect the likelihood and, more sharply, a finite-difference gradient that divides the difference of two likelihoods by a small \(h\).

Optimization Checks and Common Pitfalls

A numerical optimizer sees only the objective values and gradients it is given. It cannot distinguish a genuine likelihood improvement from a change caused by an inner solver stopping inconsistently. In practice, solve the Bellman equation to a controlled residual at every trial parameter vector, and make that tolerance sufficiently stringent near the optimizer's solution. If parameters have very different scales, rescale them so that a common numerical step does not represent a negligible perturbation in one coordinate and an enormous perturbation in another.

Common mistake: “The optimizer stopped, so the estimated parameters maximize the likelihood.” This reasoning treats the optimizer's stopping rule as proof that its inputs were accurate. In a nested model, small parameter steps or a small reported gradient can instead reflect noisy likelihood evaluations, inaccurate finite differences, or a poorly scaled parameterization. The correction is to verify the inner residual, tighten it and rerun, check gradient stability over sensible step sizes, and confirm that the likelihood and parameter estimates are stable. These checks support a numerical convergence claim; they do not by themselves establish identification or model validity.