論文紹介 "budget constrained bidding by model free reinforcement learning in display advertising"
?Download as PPTX, PDF?
1 like?281 views
社内勉强会での発表资料です。
論文紹介 "budget constrained bidding by model free reinforcement learning in display advertising"
- 1. 論文紹介 “Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising” 2019/02/08 サイバーエージェント アドテク本部 AI Lab 宮西 一徳
- 2. 論文概要 “Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising” 予算内で広告入札の最適なポリシーを探す ?モデルフリーな強化学習 ?効率的な報酬関数の設計 ?DQN拡張の実装 27th ACM International Conference on Information and Knowledge Management (CIKM 2018) にて発表された論文 （Alibaba Groupの人たちの論文） このカンファレンスのテーマは "From Big Data and Big Information to Big Knowledge"
- 3. もくじ ● 問題設定 ● 提案手法 ● 実験 ● まとめ
- 4. もくじ ● 問題設定 ● 提案手法 ● 実験 ● まとめ
- 6. 予算制約付き入札 定式化すると 一定期間にN回のimpがやってくるとして、 i番目のimpで入札に勝つか どうかのindicator i番目のimpの価値 i番目のimpで勝ったときのコスト 予算
- 7. 予算制約付き入札 i番目のimpの入札額 入札額について i番目のimpの価値 scaling factor “Optimal Real-Time Bidding Frameworks Discussion” (Zhang et al.)にて ラグランジュの未定乗数法で、予算制約付き入札問題を解いている。 （λはラグランジュ乗数） 上の式で最適な入札額が求められる と示されている。 この論文では、入札額を生成するのではなくて、 λを適切な値に調節する方法を考える。
- 8. 割引累積コスト 割引累積報酬 強化学習（制約付き） たいてい状態空間?行動空間?状態遷移からなるマルコフ決定過程(MDP)でモデル化される。 ここではコストに対する制約を設けることでMDPを拡張した Constrained Markov Decision Process(CMDP) を使う。 ポリシー を最大化する が制約を満たす 上限コスト 右肩kはコストのタイプ → K種類のコスト全てに ついて制約を満たすこと が条件 割引率(0<γ<=1) 各時点での報酬
- 9. もくじ ● 問題設定 ● 提案手法 ● 実験 ● まとめ
- 11. 提案手法 モデルフリーな強化学習 Deep Q-network(DQN)を採用 → Q-learningでの行動価値関数Q(s, a)をDNNで表現したもの ?報酬関数の改良 ?ε-greedyベースのポリシーの改良 主な提案内容 このあとの提案手法についての説明 ?強化学習の流れ ?報酬関数 ?ε-greedy ?アルゴリズム
- 12. 提案手法 強化学習の流れについて
- 13. 強化学習の流れ 学習の流れ Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 14. 提案手法のモデル 予算Bと初期値λ_0で1エピソード開始 （割引率γ=1） 例、1エピソード=1日 学習の流れ エピソード エピソードに対して予算制約あり 強化学習によってλを調整していく Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 15. 提案手法のモデル 予算Bと初期値λ_0で1エピソード開始 （割引率γ=1） 例、1エピソード=1日 学習の流れ ステップごとにλを調整する 1エピソード=Tステップ （例、1ステップ=15分） エピソード ステップ ステップ内ではλは一定 ステップの最後に報酬を獲 得し、 λを調整して次のステップ へ Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 16. 提案手法 報酬関数の改良について
- 17. 提案手法（報酬関数設計の罠） i番目のimpの入札額 i番目のimpの価値 scaling factor λを小さくする→入札額が大きくなる→即時報酬は増える が 局所解に陥る ?予算制約の無視 = 速攻で予算を使い果たしてしまう ?探索効果の欠如 = 即時報酬に目がくらんで、学習初期に貪欲な行動をとるようになってしまい、 後半は探索しなくなる これを解消するようなシンプルな報酬関数を設計したい
- 19. 提案手法 ポリシーの改良について
- 20. 提案手法（ポリシーの改良） DQNはデフォルトε-greedy = 確率1-εでQを最大化する行動をとり、εでランダム → だいたいεは大きい値で始めて、だんだん小さくしていくもの ?速すぎると、探索が不十分で局所解に陥るかも ?遅すぎると、収束が遅れて局所解にも辿り着かないかも εの更新方法をλとQの値を使って決める
- 21. 提案手法（ポリシー改良） λを少し増減してみて、Qの値がどんな感じになるかで判断する εの更新方法 正常なので εは小さくしていく 異常=行動空間の探索が足りていない → εを大きくして探索する 適応的ε-greedyポリシー 最適入札理論によると 各ステップ内での最適 なλは1つに決まる “Optimal Real-Time Bidding Frameworks Discussion” (Zhang et al.) より Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 22. 提案手法 アルゴリズム全体ついて
- 23. で入札額を決める 提案手法（フレームワークとして） Deep Reinforcement Learning to Bid(DRLB) 適応的ε-greedyに従って 行動を選択 =λを調整する ステップtの結果 報酬と状態が得られる ① ② ③ 報酬を推定する 別のDNN Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 24. で入札額を決める 提案手法（フレームワークとして） Deep Reinforcement Learning to Bid(DRLB) 適応的ε-greedyに従って 行動を選択 =λを調整する ステップtの結果 報酬と状態が得られる ① ② ③ 報酬を推定する 別のDNN 状態 1 現在時刻 2 残予算 3 λの残り調整回数 4 予算消化率 5 t-1からtの間の勝ったimpでのCPM 6 勝率 7 t-1時点での勝ったimpのトータル 価値（総クリック数とかCV数とか） Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 25. 提案手法（アルゴリズム） RewardNetを更新 適応的ε-greedyで行動選択 λを調整して、入札額を決定 RewardNetで報酬推定 これまでの ［状態?行動?報酬］ のミニバッチを抽出して、 それぞれ、それ以降に期待される最大報酬を計算 現在のQ関数の値（DQNの出力）との誤差から DQNの重みパラメータθを更新 各ステップ の処理 Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 26. 提案手法（RewardNet） 過去の状態?行動のペアごとに その状態?行動を含むエピソード 全体の即時報酬の和の最大を 保存する→ M(s, a) エピソードの最後に… 各ステップで ［状態?行動?M］のミニバッチを抽出 各状態?行動ペアに対するRewardNetの 出力値とMの値の誤差を最小化するよう にRewardNetを学習する ある状態である行動をとったときに、 最大どれくらいの報酬が得られそうか を推測するネットワーク Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 27. もくじ ● 問題設定 ● 提案手法 ● 実験 ● まとめ
- 29. ベースライン ■ FLB: 固定線形入札 固定値λ0を使って入札する ■ BSLB: 予算平滑化線形入札 予算の消化情報Δ（エピソードの残り時間を残予算の割合で割ったもの）を組み合わせる ■ RLB: 強化学習による入札 オークション処理をMDPとして定式化する
- 30. 提案手法の実装 ?隠れ層3つで各層が100ユニットの全結合NN ?RewardNetも同じ構造 ?行動の候補としては、λの調整レートを7パターン(-8%?+8%) ?εは最初0.9で最終的には0.05になるように。 各ステップでmax(0.95-r_ε*t, 0.05)で設定 ※ r_εはannealing rateでパラメータ（εを小さくしていくスピードを調整する） ?探索が不十分なときは、ε=max(ε, 0.5)でランダムに選択する
- 32. 頑健性の比較 提案手法がだいたい良い 比較手法は、ズレが大きいところで特に悪化している 提案手法は大きく悪化していない Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 33. 頑健性の比較 固定したλを使っているので、環境の変化に対応できていない Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 34. 頑健性の比較 BSLBは予算の消化情報を取り込んでいるので、環境の変化を捉えられているが 初期の残予算が多い段階での変化には鈍感なため、 λの初期値のズレが大きい場合に悪化している。 Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 35. 報酬関数の評価 RewardNetと即時報酬を使う場合でのエージェントの振る舞いの違いを見る 訓練中の10エピソードごとにダンプしたモデルをテストデータに当てた場合の評価 RewardNetが少ないステップ数で R/R*が0.893まで達している。 即時報酬では0.418どまり。 → RewardNetで最適なポリシーが得られ ている。 Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 36. 報酬関数の評価 各ステップでの報酬の割合を比較してみる 即時報酬の場合、前半で予算を使い果たしてる RewardNetは、理論最適λ*と似た分布 → エピソード全体での報酬に対して予算を活用 できている。 （1エピソード=96ステップ） Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 37. 適応的ε-greedyのannealing rateについて 適応的ε-greedyのεは各ステップでmax(0.95-r_ε*t, 0.05)とする r_εはannealing rateで、εを小さくしていくスピードを調整するパラメータ r_ε=2e-5 r_ε=1e-5 どちらのケースも提案する適応的ε-greedyの方が効率的に探索できていることがわかる 特にannealing rateが大きい場合に早く収束している→ 短時間でいい結果を出せる Di Wu, et al. "Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising" (CIKM '18)
- 38. もくじ ● 問題設定 ● 提案手法 ● 実験 ● まとめ
- 39. まとめ ■ 広告のRTBでの予算制約付き入札問題に対して、 モデルフリーな深層強化学習の手法を提案した ■ λの制御問題として定式化 ■ 即時報酬に代わるRewardNetを提案 ■ ε-greedyを改良して、効率的な探索を可能にした ■ 実データでの実験で、高い性能を示した