ADR 0003: Rule Agent Tuning のアルゴリズムに TPE を採用する¶

状態: 採用
Date: 2026-07-07
Deciders: ryo (本人), Claude Code

背景¶

src/pca/rule_agents/tuning/ は rule-based agent の params.yaml を自動最適化するモジュール。当初 Grid stage のみ実装 (Stub evaluator でパイプライン検証) だったが、以下の課題があった:

Grid のサンプル効率: 4 dim × 5 値 = 108 config × 200 games × 3 opponent pool = 21,600 games / 探索。高次元 (12 dim) にすると 5^12 = 244 万 config で現実不可
1 評価が高コスト: 200 games × 数秒 = 15〜30 分 / config。Grid で数千 config は数百日
勝率ノイズ ±0.03: 200 games でのノイズが順位を頻繁に入れ替える。少サンプル手法は不安定

以下のアルゴリズムを候補として検討した (詳細比較は下記):

Grid Search
Coordinate Descent
CMA-ES (Evolution Strategy)
Genetic Algorithm (NSGA-II)
Hyperband / BOHB
Population Based Training (PBT)
TPE (Tree-structured Parzen Estimator) via Optuna
Bayesian Optimization (GP surrogate)

決定¶

Optuna の TPE + MedianPruner を主力の tuning アルゴリズムとして採用する。

具体的な構成:

Sampler: optuna.samplers.TPESampler (default 設定、gamma=0.25, n_ei_candidates=24)
Pruner: optuna.pruners.MedianPruner (n_startup=10, n_warmup=1)
Study 永続化: in-memory (SQLite なし)。trial 履歴は trials.jsonl に逐次追記
並列: default n_jobs=1 (subprocess 並列と衝突するため推奨は 1)
オプション依存: pyproject.toml の [dependency-groups] tuning グループに optuna>=4.0 を追加

Grid stage は smoke test / 少次元での全探索用途に残す (削除しない)。

採用理由¶

我々の問題の特徴¶

評価コスト: 1 config = 数十分 / 数百 games
ノイズ: 勝率 ±0.03、複合スコア ±0.02〜0.05
次元数: 4〜20 (typical 10〜15)
並列性: config 間は独立、subprocess で 8 並列可能
予算制約: 1 セッション 24 時間、実用的な trial 数 50〜200

TPE の適合性¶

少 sample で収束: 50〜100 trial で有望領域に絞り込める (Grid の数千 config 相当のカバレッジ)
離散連続混在対応: Choice (categorical) と Continuous の両方を suggest_categorical / suggest_int / suggest_float でハンドリング
中央値打ち切り: MedianPruner で弱い trial を早期終了、実効的な予算を有望候補に集中
実装コスト: Optuna 導入 (依存 1 個) + 空間変換 (200 行) + テスト = 半日で稼働
Optuna エコシステム: 後で Hyperband / CMA-ES に差し替え可能 (sampler / pruner を交換するだけ)

想定サンプル効率¶

50 trial (= 250,000 games) × TPE で baseline 0.42 → 0.60 前後の best が期待できる。同じ予算で Grid だと 0.55 前後 (差 +0.05)。詳細は rule-agent-tuning-algorithm.md § 5。

検討した代替案¶

1. Grid Search (残置決定)¶

利点:

実装が最も単純
大域最適が格子点上に載っていれば確実にヒット
少次元 (≤4) では現実的

欠点:

次元の呪い: k dim × N 値 = N^k で爆発
全格子点を均等に評価するため、無駄領域にも予算を使う

判定: 完全に削除せず「smoke / 少次元用」に残す。default stage は Optuna に変更 (--stage grid は explicit 指定時のみ)。

2. Coordinate Descent¶

利点:

Grid best から始めて 1 パラメータずつ動かすだけ、実装容易
局所改善に強い

欠点:

パラメータ間相互作用を捕捉できない
Grid ベースの前段が必要 (2 段階構成)

判定: TPE でカバー可能なため実装せず。将来 CMA-ES 追加時に併せて検討。

3. CMA-ES (Evolution Strategy)¶

利点:

共分散を学習する → パラメータ間相互作用を捕捉
連続空間で高次元に強い

欠点:

500 sample 以上が理想的で我々の予算 (50〜200 trial) に対して重い
離散パラメータ (Choice) を素直に扱えない
ノイズに敏感

判定: 将来 CPU 予算増加時に optuna.samplers.CmaEsSampler に差し替え可能。Optuna 経由で追加コスト最小。

4. Genetic Algorithm (NSGA-II)¶

利点:

離散連続混在に強い (yaml の Choice/Continuous と親和)
Pareto front (multi-objective) が自然に扱える
局所最適に落ちにくい (multi-modal 対応)

欠点:

population × generation = 1000+ sample が必要
ノイズ耐性が弱い (個体スコアがノイズで揺れると選抜が誤る)
実装コストが TPE より大 (crossover / mutation の設計)

判定: サンプル効率で TPE に劣る。Multi-objective が本当に必要になった時点で optuna.samplers.NSGAIISampler で導入検討。

5. Hyperband / BOHB¶

利点:

予算に対する感度が高い: 各 rung で games を段階的に増やす。無駄予算最小
論理的にサンプル効率が最も良い (successive halving)

欠点:

min/max budget の設計が必要 (25 games でも真勝率推定は粗い ±0.10)
実装が MedianPruner より重い

判定: MedianPruner で "十分" と判断し MVP に採用。将来 optuna.pruners.HyperbandPruner に差し替え可能。

6. Population Based Training (PBT)¶

利点:

学習中に params を変更できる: rule agent の場合、trial 途中で params を書き換える意味は薄い
Self-play で opponent も同じ population から選べば co-evolution 実現

欠点:

実装コスト大
我々の問題は「学習中の params 変更」を要求しない (rule agent は一発評価)

判定: rule agent tuning の性質 (evaluate は 1 shot) に対して overkill。将来 Neural agent 側の tuning に検討。

7. Bayesian Optimization (GP surrogate)¶

利点:

理論的にはサンプル効率が最高クラス
不確実性 (信頼区間) を明示的に扱える

欠点:

勝率ノイズ ±0.03 で GP surrogate が信用できない: 1000 games/config以上必要
大次元 (10+) で計算コスト爆発 (O(N^3))
離散パラメータの扱いが不自然

判定: TPE (KDE ベースの近似 Bayesian) の方が我々の問題に適合。純粋な BO は不採用。

各アルゴリズムのスコアリング¶

我々の問題設定 (評価高コスト + ノイズ大 + 中次元) での適性:

手法	サンプル効率	ノイズ耐性	実装コスト	総合
Grid	★	★★★	★★★★★	少次元専用
Coord Descent	★★	★★	★★★★	併用向き
TPE ★採用	★★★★	★★★★	★★★★	本命
CMA-ES	★★★★★	★★	★★	予算増加時
GA	★★	★★	★★	不適
Hyperband	★★★★★	★★★	★★	将来検討
PBT	★★★★	★★★	★	用途不一致
BO (GP)	★★★★★	★	★★★	ノイズで不安定

影響¶

利点¶

サンプル効率: Grid の 2〜3 倍の効率、50〜100 trial で有望領域収束
将来拡張性: Optuna 経由なので Hyperband / CMA-ES / NSGA-II への差し替えが API 変更なしで可能
保守性: MedianPruner の中央値ロジックは単純明快、デバッグ容易
doc 化: TPE の l/g 比 → KDE の理論が確立しており、 algorithm doc に体系的に記述できた

欠点¶

依存増加: optuna>=4.0 が optional dependency として追加。 uv sync --group tuning を明示的に実行する必要
並列制約: Optuna n_jobs>1 は subprocess 並列と衝突するため n_jobs=1 推奨。並列性能は subprocess 側 (--workers) で稼ぐ設計
パラメータ独立仮定: TPE は次元間相互作用を捕捉できない (7 章の制約参照)
CMA-ES/BOHB の実装先送り: 「必要になったら差し替え」方針で今回はスコープ外

その他の影響¶

Grid stage を smoke / 少次元用途に残す。default は Optuna
Selfplay evaluator と Optuna stage は独立に開発 (Evaluator Protocol 抽象化により evaluator と stage が組み合わせ可能)

参考資料¶

rule-agent-tuning-algorithm.md — アルゴリズム詳細
rule-agent-tuning-flow.md — 更新の仕組み
rule-agent-tuning-optuna.md — Optuna stage 実装
rule-agent-tuning.md — Tuning 全体設計
2026-07-05-rule-agents-redesign.md — Rule Agent 再設計方針
Bergstra, Bardenet, Bengio, Kégl (2011). "Algorithms for Hyper-Parameter Optimization." NeurIPS.
Akiba, Sano, Yanase, Ohta, Koyama (2019). "Optuna: A Next-generation Hyperparameter Optimization Framework." KDD.
Farina (2025). "Reevaluating Policy Gradient Methods for Imperfect- Information Games." — 参考: 我々のプロジェクト全体での探索手法選択の文脈 (Neural 側の話だが、ノイズ環境での探索手法の議論として有用)