Rule Agent Tuning — アルゴリズム詳細¶

作成日: 2026-07-07

このドキュメントは pca.rule_agents.tuning の Optuna stage がパラメータをどのように最適化するか を数式レベルで説明する。CLI の使い方や設計方針は姉妹ドキュメントを参照:

使い方: rule-agent-tuning-optuna.md
ファイル更新の仕組み: rule-agent-tuning-flow.md
全体設計: rule-agent-tuning.md
採用理由 (ADR): ../decisions/0003-tuning-tpe-vs-grid.md

対応実装:

src/pca/rule_agents/tuning/optuna_stage.py
src/pca/rule_agents/tuning/aggregate.py (目的関数)

1. 最適化ループ全体像¶

flowchart TB
    START([tuning run 開始]):::start
    INIT["Startup phase<br/>初期 N_startup 回<br/>= ランダムサンプル"]:::init
    PROP["TPE が次の overrides を提案"]:::propose
    EVAL["SelfplayEvaluator.evaluate<br/>200 games × 25 opponents"]:::eval
    PRUNE{"MedianPruner<br/>should_prune?"}:::pruner
    OBJ["Aggregator.objective で複合スコア"]:::obj
    UPDATE["Study にスコア記録<br/>TPE 内部モデル更新"]:::update
    DONE{"n_trials 到達?"}:::check
    WRITE["Aggregator.write_reports<br/>history.csv / top_k.yaml / best.yaml"]:::write
    END([終了]):::start

    START --> INIT --> PROP --> EVAL --> PRUNE
    PRUNE -- "prune (弱い)" --> UPDATE
    PRUNE -- "keep (中央値以上)" --> OBJ --> UPDATE
    UPDATE --> DONE
    DONE -- "no" --> PROP
    DONE -- "yes" --> WRITE --> END

    classDef start fill:#e3f2fd,stroke:#1976d2,color:#000
    classDef init fill:#fff9c4,stroke:#f9a825,color:#000
    classDef propose fill:#fff3e0,stroke:#f57c00,color:#000
    classDef eval fill:#f3e5f5,stroke:#7b1fa2,color:#000
    classDef pruner fill:#fce4ec,stroke:#c2185b,color:#000
    classDef obj fill:#e8f5e9,stroke:#388e3c,color:#000
    classDef update fill:#e0f2f1,stroke:#00796b,color:#000
    classDef check fill:#ede7f6,stroke:#5e35b1,color:#000
    classDef write fill:#f1f8e9,stroke:#689f38,color:#000

役割分担:

提案 (Optuna TPESampler): 過去 trial の履歴を見て、次に試すパラメータを選ぶ
評価 (SelfplayEvaluator): 提案されたパラメータで実際に selfplay を回し勝率を得る
選別 (MedianPruner): 中間結果が中央値未満なら残り評価をスキップ
集計 (Aggregator): 複合スコア化 + 全 trial を降順ソート + 上位選定

2. TPE (Tree-structured Parzen Estimator)¶

2.1 直感¶

TPE は「良かった trial のパラメータ分布 と 悪かった trial のパラメータ分布 の比率」を最大化する点を次に試す。

良かった trial が集まっている領域 = 有望
悪かった trial ばかりの領域 = 避ける

この 2 分布の比が大きい点を選ぶことで、有望領域を効率よく絞り込める。

2.2 定式化¶

パラメータを x (多次元)、目的関数値を y とする。

Step 1: 過去 trial を y の値で 2 群に分ける (default: 上位 25% と残り):

good 群: Y_good = { y_i | y_i は top 25% }
bad 群: Y_bad = { y_i | y_i は残り 75% }

Step 2: 各群のパラメータ分布を KDE (Kernel Density Estimation) で推定:

l(x) = P(x | good)   ← 良かった trial のパラメータの密度
g(x) = P(x | bad)    ← 悪かった trial のパラメータの密度

Step 3: 獲得関数 (Expected Improvement) を最大化する x を選ぶ:

x_next = argmax_x  l(x) / g(x)

実装上は Optuna が l/g 比が大きい候補を数十個サンプルし、その中の最良を次 trial に採用する。

2.3 具体例¶

supporter_tier.critical を [15000, 28000] で最適化中、10 trial 完走時点:

trial	critical	objective
0	18000	0.42
1	25000	0.58 ★top
2	15000	0.31
3	22000	0.51
4	26000	0.55 ★top
5	17000	0.38
6	23000	0.53
7	20000	0.46
8	28000	0.44
9	24000	0.57 ★top

Step 1 (分割):

good (top 25% = 3 trials): {1, 4, 9} の critical = {25000, 26000, 24000}
bad (下位 75% = 7 trials): {6, 3, 7, 0, 8, 5, 2} の critical = {23000, 22000, 20000, 18000, 28000, 17000, 15000}

Step 2 (KDE):

l(x) の密度:

             ▂▅█▅▂
            /     \
15000 ─────/       \────── 28000
       (25000 付近が突出)

g(x) の密度:

     ▂▂▂▃▃▃▃▂▂▂
     ──────────
15000          28000
   (広く分散、特にピークなし)

Step 3 (比率最大化):

x 候補	l(x)	g(x)	l/g
15000	≈0	中	極小
20000	小	中	小
25000	大	中	最大
28000	小	中	小

→ 次 trial は critical ≈ 25000 付近を選ぶ。

2.4 多次元と独立性¶

raging_bolt_space.optuna.yaml は 12 次元。TPE は 各次元独立に KDE を推定する:

supporter_tier.critical:      l/g argmax → 25000
supporter_tier.lethal:        l/g argmax → 55000
attach_energy.main_match:     l/g argmax → 6000
items.hyper_ball_empty_bench: l/g argmax → 22000
...

制約: パラメータ間の相互作用は捕捉できない。「A を上げる and B を上げる」が同時に効くケースを見逃す可能性 (詳細は 6.1)。

2.5 Startup phase¶

TPE は分布推定のためある程度のサンプル数が必要。default:

n_startup_trials = 10

最初の 10 trial は 一様ランダムサンプル。11 trial 目から KDE ベースの提案に切り替わる。startup を大きくすると初期の探索は広くなるが有望領域への収束が遅れる。少ないと KDE が不安定になり誤った領域に集中しがち。

2.6 実装コード¶

# src/pca/rule_agents/tuning/optuna_stage.py

study = optuna.create_study(
    direction="maximize",
    sampler=optuna.samplers.TPESampler(seed=seed),   # ← TPE
    pruner=optuna.pruners.MedianPruner(
        n_startup_trials=pruner_n_startup,
        n_warmup_steps=pruner_n_warmup,
    ),
)
study.optimize(objective, n_trials=n_trials, n_jobs=parallel)

TPESampler のデフォルト:

n_startup_trials = 10
gamma = 0.25 (top 25% を good に)
n_ei_candidates = 24 (l/g 最大化のため 24 個候補をサンプルして最良選択)

これらは Optuna の default をそのまま採用しており、必要に応じて TPESampler(gamma=..., n_ei_candidates=...) で調整可能 (現状は未 CLI 化)。

3. MedianPruner¶

TPE と並行して走る 早期打ち切り機構。中間評価が過去 trial の中央値未満なら残りの評価をスキップする。

3.1 動作¶

各 trial 内で SelfplayEvaluator が opponent ごとの win_rate を返すと objective() は step ごとに trial.report(...) を呼ぶ:

# src/pca/rule_agents/tuning/optuna_stage.py

if result.per_opponent:
    for step, (_, rate) in enumerate(result.per_opponent.items()):
        trial.report(rate, step)                # ← 各 opponent が 1 step
        if trial.should_prune():
            pruned = True
            break

MedianPruner の判定:

should_prune() が True になる条件:

    trial.report(v, step=s)  を呼んだ直後、

    v < median({ v_i | 過去に完走した trial の同 step=s の値 })

かつ

    trial.number >= n_startup_trials     (startup 完了後のみ)
    s        >= n_warmup_steps            (warmup を過ぎたステップ)

3.2 具体例¶

--opponents opp1,opp2,opp3 で 25 trial まで進んだ時点で trial 26 が発生:

Trial 26:
    step 0 (vs opp1): win_rate = 0.35
        report(0.35, step=0)
        過去 25 trial の step=0 中央値: 0.48
        0.35 < 0.48 → prune 発火
        ↓
    should_prune() → True
    raise optuna.TrialPruned()
    ↓
    残りの opp2, opp3 は評価しない
    trials.jsonl に state="PRUNED" として記録

効果: 弱い trial に 200 games × 3 opponents 全部使う代わりに opp1 分だけで終わらせる → 予算節約。

3.3 startup と warmup¶

フラグ	default	意味
`--pruner-n-startup`	10	最初 N trial は必ず完走 (中央値を作る母集団)
`--pruner-n-warmup`	1	各 trial の最初 K step は判定対象外 (1 opponent だけで判定は不安定)

startup を大きくすると pruner が働き始めるのが遅れるが判定精度は上がる。warmup を大きくすると各 trial で最初の K opponents は必ず評価される。

3.4 制約: `per_opponent` が空だと働かない¶

MedianPruner は trial.report(...) が呼ばれて初めて有効。SelfplayEvaluator が opponent 別 win_rate を返せない場合 (matchup CSV が空、あるいは 1 opponent しか指定していない) intermediate reporting が起きず MedianPruner は事実上無効化される。

4. 目的関数の設計¶

TPE が最大化する objective(result) は 単純 win_rate ではなく複合スコア:

# src/pca/rule_agents/tuning/aggregate.py

def objective(self, result: EvaluationResult) -> float:
    return (
        self.win_weight * result.win_rate                    # +1.00 * win_rate
        - self.unfinished_penalty * result.unfinished_rate   # -0.50 * unfinished
        + self.prize_diff_weight * (result.mean_prize_diff / 6.0)  # +0.10 * (prize_diff / 6)
        - self.deck_out_penalty * result.deck_out_loss_rate  # -0.20 * deck_out
    )

4.1 なぜ複合スコアか¶

win_rate だけを最大化する落とし穴:

症状	例
unfinished 多発	攻撃可能ターンでも "様子見" を選ぶ agent が生まれ、時間切れで unfinished 頻発
deck_out で勝つ	序盤に無理サーチしまくって山を圧迫、相手より先に山が切れないだけの受動的勝利
極端な spread 局所最適	ランダムに強い/弱い 2 型に分裂した agent が生まれる

これらは runtime 運用で困る挙動なので、目的関数側で減点する。

4.2 各項の解釈と重み¶

項	係数	意味
`+1.0 · win_rate`	主目標	勝つことが最重要
`-0.5 · unfinished_rate`	大ペナルティ	unfinished 20% は勝率換算で 10 pt 減。「攻撃可能なら攻撃する」を強制
`+0.1 · (mean_prize_diff / 6)`	小報酬	「勝敗が付かなかった時でもサイド差で優位」を評価
`-0.2 · deck_out_loss_rate`	中ペナルティ	山切れ負けは実質的な敗北なので、単に "勝てなかった" 以上に減点

4.3 重み調整方針¶

CLI で override 可能 (default は上記):

--win-weight 1.0
--unfinished-penalty 0.5
--prize-diff-weight 0.1
--deck-out-penalty 0.2

方針:

unfinished_penalty は高めに固定: 破綻挙動を排除する目的なので、この項は 0.5 未満にしない
prize_diff_weight は微小に留める: サイド差を過度に重視すると引き分け狙いの agent が生まれる
deck_out_penalty は環境依存: 山切れが多い meta (ドローソースが少ない環境) では 0.3 まで上げる余地あり

4.4 なぜ Pareto front ではないか¶

複数目標 (win_rate 高いかつ unfinished 低い) を Pareto front として保持する選択肢もあるが以下の理由で単一目的関数化を選択:

best 1 個を選びたい: params.yaml は 1 セットしか使わないため、Pareto 全体を残しても最終的に「どれを apply するか」の判断コストが発生
重み再ランキングが可能: history.csv に全メトリクスを保存しているので、後から別の重みで再ソートできる
TPE の獲得関数がスカラー前提: Optuna の multi-objective モードは NSGA-II ベースで TPE より収束が遅い

4.5 目的関数のカスタマイズ手順¶

目的関数の重みを変えて run (baseline との重み差だけ変更)
history.csv を pandas でロード、別の重みで再ランキング
選ばれた best が変わるかを確認 → 変わるならその重みは有効な調整軸

5. サンプル効率と Grid との比較¶

5.1 Grid の限界¶

3 パラメータ × 各 5 値 = 125 config。各 200 games × 25 opponents = 625,000 games。CPU 1 コアで 1 game 30 秒とすると 5,200 時間 = 217 日 (現実的でない)。

5.2 TPE の期待効率¶

同じ 12 パラメータで 50 trial = 250,000 games = 87 日 (1 コア)。並列 8 コアなら 11 日。

Grid と同じ 5,200 時間予算があれば TPE で ~1,000 trial 走らせられるが、経験的には 50〜100 trial で TPE は収束する。理由:

TPE の獲得関数が 無駄領域を刈り込む: bad が集まる領域には行かない
MedianPruner が 弱い trial を早期打ち切り: 実効的な games/trial が減る

5.3 想定されるサンプル効率¶

50 trial × 200 games × 25 opponents の TPE を回した時の想定挙動:

フェーズ	trial 番号	win_rate 分布
Startup (ランダム)	0-9	0.30〜0.55, 平均 0.43
学習開始 (TPE 有効)	10-25	0.40〜0.60, 平均 0.50
有望領域絞り込み	26-40	0.48〜0.62, 平均 0.55
局所探索	41-50	0.55〜0.65, 平均 0.60

最終 best: 0.60〜0.65 前後 (baseline 0.42 と比較して +0.18〜0.23)。

同じ 50 config を Grid でやると (格子点をランダム順に評価):

フェーズ	trial 番号	win_rate 分布
全 trial	0-49	0.30〜0.60, 平均 0.45

Grid の best: 0.55 前後 (格子点の中に偶然 0.60+ が含まれるかは運任せ)。

経験的に TPE は Grid の 2〜3 倍のサンプル効率。

5.4 グラフ的な理解¶

Grid (格子点を均等に評価):
    x1 x2 x3 x4 x5
    ●  ●  ●  ●  ●
    ●  ●  ●  ●  ●     ← 全格子点をランダム順に消化
    ●  ●  ●  ●  ●     ← 有望領域も無駄領域も等しく評価
    ●  ●  ●  ●  ●

TPE (有望領域を優先):
     x1  x2  x3  x4  x5
     ○  ○  ●  ●  ●      ← 初期 startup で分散サンプル
     ○  ○  ●●● ●  ○     ← 25000 付近が良かった → 集中
     ○  ○  ●●●● ○ ○    ← さらに絞り込み
     ○  ○ ●●●●● ○ ○     ← 局所探索

6. 既知の制約¶

6.1 パラメータ独立仮定¶

TPE は各次元の l(x)/g(x) を独立に評価する。「A と B を同時に上げると良い」という相互作用は検出できない。

症状:

個別に A を上げても悪化、B を上げても悪化、しかし A+B を同時に上げると改善する組み合わせが最適解の場合、TPE は A も B も上げない方向に収束
具体例: attach_energy.main_match_bonus と setup.active_priority.main_attacker は相関があるが、TPE は独立と仮定

回避策:

CMA-ES sampler に切り替え (optuna.samplers.CmaEsSampler): 共分散を学習
パラメータをまとめる: 相関の強い 2 パラメータを 1 つの "profile" として yaml で表現

6.2 勝率ノイズへの過剰適合¶

200 games での勝率標準偏差は約 ±0.03。TPE は 0.55 の trial と 0.53 の trial を区別しようとして、実質ノイズを追いかける。

症状:

Trial 20 で best 0.62 だったが、apply して runtime で 500 games 回すと 0.58 になる (真の値は 0.60 前後で ±0.02 のノイズ)

回避策:

games/config を 500 まで増やす (ノイズ半減)
目的関数を複合化 (ノイズの分散を別の情報源で補正)
best.yaml を apply する前に 500 games × 5 対戦相手 の検証ラン (regression test) を挟む

6.3 startup phase の運任せ¶

n_startup_trials=10 のランダムサンプルが偶然 supporter_tier.critical=18000 付近ばかりだと、TPE は 18000 付近を有望と誤認する。

回避策:

seed を変えて 2〜3 回 tuning を回し best.yaml を比較
Optuna の optuna.samplers.QMCSampler を startup 用に使う (未実装)

6.4 局所最適への閉じ込め¶

l/g 最大化は greedy なので、複数のピークを持つ目的関数だと片方の峰に閉じ込められる。

症状:

パラメータ空間の一部にランダムに強い / 弱い 2 モードがあり、startup で片方に偏るとその周辺しか探索されない

回避策:

constant_liar 機能 (未実装)
ランダム restart (seed 変更した並行 study)

7. 将来の拡張¶

7.1 CMA-ES sampler¶

sampler = optuna.samplers.CmaEsSampler(seed=seed)

相互作用を捕捉できるが、より多くの trial (500+) が必要。CPU 予算が増えたら移行候補。

7.2 Hyperband pruner¶

MedianPruner を Hyperband に置き換え:

pruner = optuna.pruners.HyperbandPruner(
    min_resource=25,    # 最小 games/config
    max_resource=200,   # 最大 games/config
)

trial 予算を "budget" 単位で管理し、有望な trial に予算を集中する。予算に対する感度が高い時に有効。

7.3 Multi-objective (NSGA-II)¶

複数目的関数を Pareto front で保持:

study = optuna.create_study(
    directions=["maximize", "minimize"],   # win_rate 最大, unfinished 最小
    sampler=optuna.samplers.NSGAIISampler(),
)

trade-off を明示的に扱えるが、最終的に 1 セット選ぶ判断コスト が発生。

7.4 warm-start¶

過去の tuning 結果 (history.csv) を次回 tuning の初期サンプルとして注入:

study.add_trial(
    optuna.trial.create_trial(
        params=past_params,
        value=past_objective,
    )
)

新しい agent を作った時、類似 agent (同じ archetype layer) の tuning 結果を初期値として使う。Ogerpon 系デッキ間の transfer に有効。

参考文献¶

TPE 原論文: Bergstra, Bardenet, Bengio, Kégl (2011). "Algorithms for Hyper-Parameter Optimization." NeurIPS.
Optuna 論文: Akiba, Sano, Yanase, Ohta, Koyama (2019). "Optuna: A Next-generation Hyperparameter Optimization Framework." KDD.
MedianPruner の由来: Google Vizier に類似の "Median stopping rule" (Golovin et al. 2017)
Hyperband 原論文: Li, Jamieson, DeSalvo, Rostamizadeh, Talwalkar (2017). "Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization." JMLR.

変更履歴¶

2026-07-07: 初版。TPE / MedianPruner / 目的関数 / サンプル効率 / 制約を体系化。

Rule Agent Tuning — アルゴリズム詳細¶

1. 最適化ループ全体像¶

2. TPE (Tree-structured Parzen Estimator)¶

2.1 直感¶

2.2 定式化¶

2.3 具体例¶

2.4 多次元と独立性¶

2.5 Startup phase¶

2.6 実装コード¶

3. MedianPruner¶

3.1 動作¶

3.2 具体例¶

3.3 startup と warmup¶

3.4 制約: per_opponent が空だと働かない¶

4. 目的関数の設計¶

4.1 なぜ複合スコアか¶

4.2 各項の解釈と重み¶

4.3 重み調整方針¶

4.4 なぜ Pareto front ではないか¶

4.5 目的関数のカスタマイズ手順¶

5. サンプル効率と Grid との比較¶

5.1 Grid の限界¶

5.2 TPE の期待効率¶

5.3 想定されるサンプル効率¶

5.4 グラフ的な理解¶

6. 既知の制約¶

6.1 パラメータ独立仮定¶

6.2 勝率ノイズへの過剰適合¶

6.3 startup phase の運任せ¶

6.4 局所最適への閉じ込め¶

7. 将来の拡張¶

7.1 CMA-ES sampler¶

7.2 Hyperband pruner¶

7.3 Multi-objective (NSGA-II)¶

7.4 warm-start¶

参考文献¶

変更履歴¶

3.4 制約: `per_opponent` が空だと働かない¶