P2: Howard policy iteration on opt_savings_2's savings problem
I maintainer di solito rispondono entro 1 giorno
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 4/5
- Tempo stimato
- 3-5 giorni
- Idoneità per principianti
- 25/100
- Tipo di issue
- Funzionalità
- Chiarezza
- Specificata chiaramente
- Stato di attività
- Attiva
- Stack tecnologico
- numpy, python
- Ambito
- data, machine-learning, performance
Direzione di ricerca
Read issue #5's Phase 2 and the opt_savings_2 lecture, then compare the existing P1 implementation and its benchmark checks. Implement P2's Howard policy iteration across the NumPy, Numba and JAX stacks, including the grid and income sweeps, stopping and residual checks, and recorded rounds. Done means the specified value and round comparisons pass for every stack and sweep.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
#5's Phase 2 lists P2, policy iteration: Howard's improvement with a linear solve. This is P2's design, from lecture-jax's opt_savings_2. That lecture solves opt_savings_1's savings problem, which is P1's, by value function iteration, Howard policy iteration (HPI) and optimistic policy iteration, and compares them in JAX. The choices below were agreed with Matt on 2026-11-20, and revised the same day after an independent review of the first version. The review wrote the design in all three stacks, at wealth grids up to 500.
Why
- It's the question
opt_savings_2asks, across stacks. P1 is value function iteration on this model at these sizes. P2'sgridsweep is HPI on the same model at the same sizes, so the two together say, for each stack and size, how long each method takes, compile time included. Each method runs to its own stopping rule, as a user would run it:- P1 stops when the value changes by less than 1e-5, which leaves its value about 8e-6 off in relative terms;
- P2 stops when the policy stops changing, with each value solved to a relative residual of 1e-10, which in the review left its value within about 5e-11 of a direct solve, at 200 wealth points or fewer.
In the review, at 100 to 500 wealth points, the policy greedy against P1's value equalled HPI's at every state.
- It measures an iterative linear solve, in its
incomesweep. Each HPI round finds the current policy's value by solving (I − β P_σ) v = r_σ over every (wealth, income) state. Each application of the operator costs about n·y² for n wealth points and y income states, while each greedy step costs about n²·y. So at P1's larger wealth grids the greedy step dominates. In the review, at 500 points, the solve was about a quarter of NumPy's and serial Numba's time and about half of JAX's on the CPU. Theincomesweep holds wealth at the lecture's 150 points and grows the income states, so the solve grows as y² against the greedy step's y. P1, P3, P4, P5 and P7 have nothing like it.
The problem
| Model | opt_savings_2's, which is opt_savings_1's and P1's: R = 1.01, β = 0.98, CRRA utility with γ = 2, wealth on an evenly spaced grid from 0.01 to 5, and income on a Tauchen chain with ρ = 0.9 and ν = 0.1 |
| The algorithm | From the policy σ = 0: find v_σ, take the greedy policy against it, and stop when the policy stops changing |
| Policy evaluation | BiCGSTAB, as in the lecture, on the operator v ↦ v − β (v Qᵀ)[σ(w, y), y], without building the matrix. The first solve starts from zero, and each later one from the previous policy's value |
| The stopping test | SciPy's, in every stack: the 2-norm of the residual, relative to ‖r_σ‖₂, below 1e-10. It is checked before the first iteration, at the half-step and at the end of each iteration, with r̂ = r₀ |
| Failure | Any of these makes the cell an error: a solve not converged after 1,000 iterations (the review saw at most 37); a relative residual above 1e-9 after any round's solve, recomputed in every stack and recorded as the largest (revised in #77, so that JAX catches a failure in any round, not only the last); or 250 rounds, the lecture's cap |
| The greedy step | The rewards u(R w + y − w′) are computed once, inside the timed solve, and stored, as in P1. The lecture recomputes them each round. Ties go to the first maximum, as argmax does |
| What is timed | The whole solve, from the rewards to the final policy's value |
| Sweeps | grid (named as P1's same axis; wealth in an earlier version of this design): 100, 200, 400, 700, 1,000 and 1,500 wealth points, P1's sizes, with 100 income states. income: 25, 50, 100, 200 and 400 income states, with 150 wealth points |
| Precision | float64 only, as P1 |
| Recorded | The HPI rounds, and the largest relative residual after a round's solve |
Why a tolerance of 1e-10, against the lecture's 1e-5. With warm starts, HPI at 1e-5 stops, but not on the optimal policy. In the review, SciPy stopped after 8 or 9 rounds at 100 to 500 wealth points, 2 to 210 states off the policy found at 1e-10, with its value about 4e-6 off. JAX stopped on a different suboptimal policy: 179 states off at 500, against SciPy's 210. Starting each solve from zero instead, at the lecture's 150 points, the lecture's JAX code stopped after 10 rounds, while SciPy flipped one near-tied state back and forth to the 250-round cap. At 1e-10, SciPy, JAX, serial Numba and parallel Numba took the same rounds (9, 9, 9, 10 and 10 at 100 to 500), chose the same policy at every state, and agreed on the value to within 2e-13. So 1e-10 gives an accurate answer that every stack agrees on.
Why float64 only. float32 can't reach 1e-10. With warm starts, float32 at 1e-5 stopped after 9 rounds with 63 states off the policy, and at 1e-6 it reached the 250-round cap.
Why not a direct solve. With SciPy's sparse direct solve for each policy, HPI took 2.6 s at 150 wealth points and 84 s at 500, against 0.06 s and 0.39 s with BiCGSTAB.
Stacks
| Policy evaluation | The greedy step | |
|---|---|---|
| NumPy | scipy.sparse.linalg.bicgstab on a LinearOperator, with SciPy imported in setup, outside the timed solve |
NumPy's argmax over the stored rewards, as in P1 |
| Numba | A BiCGSTAB written in njit to SciPy's loop, since Numba has no solver of its own. The operator is a matrix product, which calls BLAS, and a gather. The run's env records SciPy's BLAS and its thread settings. (Revised 2026-11-20, in #77, after review: the gather is serial in numba-parallel too, since as a prange loop it started a parallel region two or three times an iteration, which cost more than the gather: 0.108 s against serial's 0.035 s at 50 income states) |
A prange loop over (wealth, income), keeping the first maximum |
| JAX | jax.scipy.sparse.linalg.bicgstab, as in the lecture. It reports no failure, so the final residual check covers it |
jnp.argmax, with the whole solve in lax.while_loop |
Checks
- The value function, at 64 fixed positions, against NumPy's at the same size, within a relative 1e-8, as for P1.
- The rounds, compared with NumPy's.
The review found 1e-8 has at least 100 times margin, and catches a policy reached at the lecture's looser tolerance.
- Lingua principale
- Python
- Stelle
- 0
- Fork
- 1
- Merge medio
- 3h 29m
- PR unite (30g)
- 64
Preparare l'ambiente
Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di QuantEcon/benchmarks
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 35/100
QuantEcon/benchmarks#78 ·
I maintainer di solito rispondono entro 1 giorno
-
P5: Markov chains, starting with the stationary distribution of a savings policy (aiyagari_jax)Aperta
Difficoltà 5/5 Più di una settimana Idoneità per principianti 45/100
QuantEcon/benchmarks#47 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 25/100
QuantEcon/benchmarks#27 · 2 commenti ·
I maintainer di solito rispondono entro 1 giorno
-
Float32 fidelity: which float64 lectures need float64, and can the heaviest step drop to float32?Aperta
Difficoltà 5/5 Più di una settimana Idoneità per principianti 25/100
QuantEcon/benchmarks#11 · 2 commenti ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 32/100
QuantEcon/benchmarks#5 · 2 commenti ·
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di QuantEcon/benchmarks
Issue simili
-
needs-triage
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 88/100
flashinfer-ai/flashinfer#9803 ·
I maintainer di solito rispondono entro 1 giorno
-
bug frontend good first issue help wanted
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
Difficoltà 2/5 1-3 ore Idoneità per principianti 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 89/100
cuadrao-ai/argus#2328 ·
I maintainer di solito rispondono entro 1 giorno
-
bug frontend good first issue help wanted
Difficoltà 2/5 1-3 ore Idoneità per principianti 88/100
nikhilb2/simple_invoicing#907 ·