P2: Howard policy iteration on opt_savings_2's savings problem

Đang mở
#72 1 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
numpy, python

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

#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_2 asks, across stacks. P1 is value function iteration on this model at these sizes. P2's grid sweep 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 income sweep. 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. The income sweep 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.

Ngôn ngữ chính
Python
Star
0
Fork
1
Merge trung bình
3 giờ 29 phút
Pull request đã merge (30 ngày)
64

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của QuantEcon/benchmarks

Tất cả issue của QuantEcon/benchmarks

Issue tương tự

Thêm issue về Python

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.