P2: Howard policy iteration on opt_savings_2's savings problem
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 4/5
- 見積もり時間
- 3〜5日
- 初心者へのやさしさ
- 25/100
- issue の種類
- 機能追加
- 明瞭さ
- 明確に書かれている
- 活発さ
- 活発
- 技術スタック
- numpy, python
調査の方向性
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.
索引モデルが issue の本文から書いたものです。
説明
#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.
- 主要言語
- Python
- スター
- 0
- フォーク
- 1
- 平均マージ
- 3時間 29分
- マージ済み PR(30日)
- 64
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
QuantEcon/benchmarks のほかの issue
-
難易度 5/5 1週間以上 初心者へのやさしさ 35/100
QuantEcon/benchmarks#78 ·
メンテナーはふだん 1 日以内に返信
-
P5: Markov chains, starting with the stationary distribution of a savings policy (aiyagari_jax)オープン
難易度 5/5 1週間以上 初心者へのやさしさ 45/100
QuantEcon/benchmarks#47 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
QuantEcon/benchmarks#27 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
Float32 fidelity: which float64 lectures need float64, and can the heaviest step drop to float32?オープン
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
QuantEcon/benchmarks#11 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 32/100
QuantEcon/benchmarks#5 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
QuantEcon/benchmarks の issue をすべて見る
似ている issue
-
needs-triage
難易度 1/5 1時間未満 初心者へのやさしさ 88/100
flashinfer-ai/flashinfer#9803 ·
メンテナーはふだん 1 日以内に返信
-
bug frontend good first issue help wanted
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
難易度 2/5 1〜3時間 初心者へのやさしさ 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
難易度 1/5 1時間未満 初心者へのやさしさ 89/100
cuadrao-ai/argus#2328 ·
メンテナーはふだん 1 日以内に返信
-
bug frontend good first issue help wanted
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
nikhilb2/simple_invoicing#907 ·