この記事について
以下の論文の翻訳です。
Wang et al. Learning Adaptive Display Exposure for Real-Time Advertising
https://arxiv.org/abs/1809.03149
数式のLaTeX化は諦めました。
----------------------------------------以下翻訳----------------------------------------
リアルタイム広告のための適応的表示の学習
要旨
商品の推薦と広告が同時にユーザーに表示される電子商取引広告において、伝統的な配置は広告を固定された位置に表示することである。しかしそのような配置では広告システムは広告の数と位置を制御する柔軟性を得られず、プラットフォームの収益とユーザー体験は最適とならない。その結果、主要な電子商取引プラットフォーム(例: Taobao.com)は広告を表示するより柔軟な手法を検討し始めている。本稿は「適応的表示による広告」を調査した: 一定のビジネス上の制約下で、それぞれのユーザー訪問に対して広告の数と位置を動的に決定することは可能か、その結果としてプラットフォームの収益は増大し得るだろうか？より具体的には、2種類の制約を検討する: それぞれのユーザー訪問に対してユーザー体験を保証するリクエストレベルの制約と、プラットフォーム全体の収益化率を制御するプラットフォームレベルの制約である。私たちはこの問題を状態ごとの制約を伴う制約付マルコフ決定過程(psCMDP)としてモデル化し、制約付2段階強化学習手法を提案することで、元の問題を2つの比較的独立した部分問題に分解する。また、方策の学習を促進するため制約付hindsight experience replay機構を考案する。産業規模の実世界データセットにおける実験評価は、制約下でより高い収益を得ることと、制約付hindsight experience replay機構の効果双方についてこの手法の利点を証明する。
キーワード
広告のための学習、適応的広告表示、リアルタイム広告、深層強化学習、制約付2段階強化学習
1 導入
深層ニューラルネットワークの進歩に伴い、深層強化学習の手法はアタリのゲーム、ロボットの移動と操作を含む多くの応用分野で重要な進歩を遂げてきた。近年、オンライン推薦、インプレッションの割り当て、広告入札戦略、商品ランキングを含む異なる側面から、電子商取引での意思決定過程を最適化する深層強化学習技術適用の成功が見られる。
伝統的なオンライン広告では広告の位置は固定され、それぞれのユーザーリクエストに対して、これらの位置にどの広告が表示されるかのみを決定する必要がある。これは広告位置入札問題としてモデル化することができ、深層強化学習は入札戦略の学習に効果的であることが広告主に示されてきた。しかし、固定された広告位置は広告システムの柔軟性を制限する。直感的に、ユーザーが高い収益化価値を持つ(例: 広告クリックを好む)場合、広告プラットフォームにとってこのユーザーが訪問した時により多くの広告を表示することは合理的である。一方で、2つの理由で、過剰に多くの広告を表示することを懸念する。第1に、そのような表示は質の低いユーザー体験につながり、ユーザー維持に悪影響を与える可能性がある。第2に、収益化率は企業にとって加減するべき重要なビジネス指標である。したがって本稿では2段階の制約を検討する: (1)リクエストレベル: それぞれのリクエスト(すなわちユーザー訪問)における広告の最大数は閾値を超えてはならない; (2)プラットフォームレベル: すべてのリクエスト(時間枠内)における広告の平均数は閾値を超えてはならない。以上の制約下で適応的表示を伴う広告の問題を調査した: それぞれのユーザー訪問に対して広告の集合と位置を動的に決定し、その結果プラットフォームの収益は最大化し得るか？以上の問題を「適応的表示を伴う広告の問題」と呼ぶ。
図1は中国の電子商取引企業Taobaoによって適用されている柔軟な適応的表示機構を示す。それぞれのユーザー訪問に対して、このプラットフォームは商品推薦と商品広告の動的な混合を表示する。広告位置は事前に固定されたものではなく、ユーザーのプロファイルと行動によって動的に決定される。適応的表示問題は連続決定問題として定式化できる。それぞれの段階で、推薦・広告システムはまずスコアリングシステムに基づいて個々に商品を選択する。そしてこれらの商品はスコアにより全体的に並べ替えられ、上位の数商品がリクエスト(ユーザー)に対して表示される。
上述の問題を制約付マルコフ決定過程(CMDP)としてモデル化する。小さいサイズのCMDPに対する最適な方策は線形計画法で導けるが、大規模で複雑な現実世界の電子商取引プラットフォームに対してそのような方策を構築するのは難しい。したがって、おおよそ最適な手法を学習するためにモデルフリー強化学習手法に頼る。CMDPを解決するための既存のモデルフリー強化学習手法は軌跡に基づく: これらの手法は軌跡全体に渡って制約違反信号を伝播することで方策を更新する。残念ながら、ほとんどの手法は制約を満たすことに失敗する。この問題を解決するため Tessler et al. は、軌跡の制約を状態ごとの罰則に分解し、重みを動的に調整する報酬制約付方策最適化(RCPO)を提案する。軌跡のすべての罰則が与えられた制約を満たすことを保証するため、制約違反信号もまた軌跡全体に渡って逆伝播される。しかし適応的表示問題を伴う広告では、状態レベル(リクエストレベル)と軌跡レベル(プラットフォームレベル)双方の制約を満たす必要がある。RCPOは軌跡レベルの制約のみを考慮するため、ここでは直接適用できない。
本稿では、まず適応的表示問題を伴う広告を状態ごとの制約付CMDP(psCMDP)としてモデル化する。そして状態レベルと軌跡レベルの制約双方を満たす最適な広告方策を学習するため、制約付2段階強化学習フレームワークを提案する。このフレームワークでは、軌跡レベルの制約と状態レベルの制約は学習過程で異なるレベルに分割される。より高レベルの方策は軌跡を複数の部分軌跡に分割し、それぞれの部分軌跡が軌跡レベルの制約の下で報酬の合計を最大化するために制約を選択する問題に取り組む。それぞれの部分軌跡は部分軌跡レベルの制約と状態レベルの制約双方を伴う独立した最適化問題を識別する。ここで、部分軌跡制約を別の状態レベルの制約として扱うことで、方策の最適性を犠牲にしてこの部分軌跡最適化問題を単純化する。この方法で、部分軌跡制約と元の状態レベル制約を用意に組み合わせることができ、深層決定論的方策勾配のようなオフポリシー手法と補助タスクを用いてより低レベルの方策を学習することができる。また、より低レベルの方策の学習を促進するため、制約付Hindsight Experience Replay
(CHER) を提案する。このフレームワークはそれぞれの部分軌跡を多くの部分軌跡にさらに分解することで、自然に拡張することができることに留意してほしい。したがってレベルの数を増やす時、学習された方策の質が向上する、つまりより低レベルにおけるそれぞれの部分軌跡の長さが減少することが期待される。したがってこのフレームワークは学習効率と方策の最適性の折衷を作り出すのに十分に柔軟である。本稿ではこのフレームワークを2段階に設定した。この2段階フレームワークのもう1つの利点は、軌跡レベルの制約が調整される場合に、より低レベルの方策を容易に再利用してより高レベルの制約選択方策を学習することができることである。この手法をTaobaoプラットフォームからの現実世界のデータセットを用いてオフライン、オンライン双方で評価する。この手法は双方のレベルの制約を満たしつつ、広告収益と広告主の収益を増加させ得る。より低レベルでは、CHER機構が学習速度を大幅に改善し、状態ごとの制約の偏差を減少させ得ることを検証する。さらにより高レベルでは、この手法は異なるプラットフォームレベルの制約に関してより高いレベルの方策を学習するためにより低いレベルの方策集合をうまく利用することができる。
2 はじめに: 制約付強化学習
強化学習(RL)では、エージェントが累積報酬を最大化するように順次的に行動し報酬を観察することで、環境と対話する。RLはマルコフ決定過程(MDP)として定式化でき、これは(S, A, R, P)のタプルとして定義される。Sは状態空間でありAは行動空間である。即時報酬関数はR: S × A × S → ℝである。Pは状態遷移確率S × A × S → [0, 1]である。Aには方策πが存在し、これはエージェントの行動を決定する。エージェントは環境と対話するために方策を利用し、軌跡τ : {s_0, a_0, r_0, s_1, . . .s_t, a_t, r_t, s_t+1, . . . }を生成する。目的は初期状態において期待される報酬を最大化する最適な方策π^*を学習することである:
数式(1)
ここでγ ∈ [0, 1]は割引率であり、Tは軌跡の長さである。制約付マルコフ決定過程(CMDP)は一般にこの状況に対応するのに使われ、それは実現可能な方策を制限することによる。具体的には、CMDPは補助コスト関数CT, S × A × S → ℝと上限u_Tによって強化される。J_C_T(π)を方策πの累積的に割引されたコストとする。期待される割引された報酬は次のように定義される:
数式(2)
CMDPの実現可能な定常方策の∈は:
数式(3)
方策は等式1において方策π ∈ Π_Cを制限することで最適化される。DRLの手法に対してAchiam et al.は最適化の目的と制約を代理関数で置き換え、信頼領域方策最適化を利用して、それぞれのイテレーションで制約を近似的に満たすことを達成する新しい手法を提案する。Tessler et al.はWeiDMPに近い手法を用いる。WeiMDPは重み変数ζ ∈ [0, 1]と次のように定義される導出された重み付き報酬関数r′_tを導入する。
数式(4)
ここでr_tと C_T(s_t, a_t, s_t+1)はそれぞれ報酬と 遷移(s_t
, a_t, s_t+1)における近似コストである。固定されたζに対してこの新しい制約なしMDPは標準的な手法、例えばQ学習によって解くことができる。Tessler et al.は重みζを価値関数への入力として用い重みを逆伝播によって動的に調整する。
3 適応的表示による広告
3.1 適応的表示機構
電子商取引プラットフォームではユーザーのリクエストQ =
{q_1, q_2, ..., q_M}は順次的に来る。ユーザーが購入リクエストq_iを送る時、ユーザーの購買履歴と個人的な好みの基でN_i個の商品がリクエストに対して表示される。N_i個の商品は広告と推薦商品から構成される。より多くの広告を表示すると広告収益が増大するかもしれない。しかし、ユーザーに表示された広告は必ずしもユーザーの好きな商品や必要な商品ではない。したがって、それぞれのユーザーのリクエストに対して表示される広告の数は制限するべきである。
それぞれのリクエストq_iに対して、伝統的な電子商取引システムは広告を表示するのに固定された位置を使う: N_i^d = K, ∀_1 ≤ i ≤ M、ここでKは固定された位置の数である。しかし、この広告機構が最適でないのは明らかである。異なる消費者は異なる購買習慣と、異なる商品と広告の好みを持つ。したがって、より広告商品をクリックし購入しそうなユーザに対してはより多くの広告商品を表示する(これは広告収益を増大させる)ことができ、逆もまた然りである。
この目的に対して、最近のTaobao(中国最大の電子商取引プラットフォームのひとつ)は広告表示と商品推薦のためにより柔軟で混合された表示機構を適用し始めている(図1)。具体的には、それぞれのリクエストq_iに対して、推薦広告システムはまずスコアリングシステムに基づいて上位N^r個と上位N^d個の商品を独立に選択する(図1、ステップ(2)とステップ(3))。そしてこれらの商品はスコアに応じて降順に並べ替えられ(図1、ステップ(5))、上位N_i個の商品がこのリクエストに対して表示される(図1、ステップ(6))。
その間、ユーザーの購買体験を保証するため、次の制約を課す必要がある:
- プラットフォームレベル制約C_platform、1日に表示される広告の合計割合は一定の閾値αを超えてはならない:数式(5)
- リクエストレベル制約C_request、それぞれのリクエストに対して表示される広告の割合はある閾値βを超えてはならない:数式(6)
ここでα ≦ βである。これは、この不等式要件を利用して異なる数の広告を異なる数のリクエストに、ユーザーのプロファイルに応じて表示することができることを意味する、例えば、より広告に興味があり平均広告収益を増大させ得るユーザーにはより多くの広告を表示し、他のユーザーにはより少ない広告を表示することである。一方では、それぞれのリクエストに対してN_i^dのサイズは候補広告と商品の質に応じて自動的に調整することができる。他方では、N_i個の商品の位置が商品と広告の質に応じて決定され、これはユーザー体験をさらに最適化し得る。この方法で、リクエストレベルとプラットフォームレベル双方の制約を満たしながら、総広告収益を増大させることができる。推薦側と広告側双方のスコアリングシステムはブラックボックスと見なせる。しかし、広告の観点からはそれぞれの広告の相対順位と最終的に表示される広告の数を変更するために、それぞれの広告のスコアを適応的に調整することができる(図1, ステップ4)。
適応的表示機構は潜在的に広告収益を増大させ得るが、多くの挑戦に直面する。第1に、広告スコア調整戦略は推薦システムの動き(例: システムアップグレード)と広告システムのその他の構成要素(例: 候補広告選択機構がアップグレードされるかもしれない)に対して非常に繊細である。私たちの広告システムはこの制約を満たす必要がある。第2に、実際のビジネスはその時々に変化する必要がある(プラットフォームレベル制約とリクエストレベル制約に対する調整)、したがって私たちの広告システムはその時々に変化する。これらの挑戦のため、私たちはより柔軟なアルゴリズムを設計せざるを得ない。
3.2 定式化
3.2.1 問題の説明
広告の観点から、上述の広告表示問題は入札問題として見ることができる: それぞれのユーザーリクエストに対して表示される商品は、広告システムのスコア(入札額)と推薦商品(入札額によってランク付けされ、入札額が高いほど表示されやすい)によって決定され、広告システムは制約を満たし収益(オークションの結果)を増大させるため元の広告(オークションの入札)のスコアを調整する。私たちはDisplay Advertising [9, 39]の入札問題の設定に従い、それを適応的表示を伴う広告問題に拡張する。形式的には、リクエストQ_iのj番目の広告 d_j ∈ D_iに対して、スコアは次のように調整される:
数式(7)
ここでη_i,j = b(q_i, d_j; θ)である。bは入札関数でありθはbのパラメータである。score_i,jはリクエストq_iのd_jに対して広告システムから与えられる元のスコアである。広告システム内のみにおいては、広告(スコアがすでに調整されている)が最終的にリクエストに対して表示されるかどうか直接解決できない。ただシャッフルシステム(図1, ステップ(5))から最終的な表示結果を得ることができるだけである。したがってw(b(q_i, d_j; θ), q_i, dj_) = E_ϕ[I(b(q_i, d_j; θ), ϕ)]を入札リクエスト(q_i, d_j)に対して入札調整率b(q_i, d_j; θ)において勝利する確率と定義する、ここでϕは推薦システムのパラメータであり、I(b(q_i, d_j; θ), ϕ)は広告d_jがリクエストq_iにおいて推薦システムのパラメータϕを考慮して最終的に表示されるかどうかを示す。v(b(q_i, d_j; θ), q_i, d_j)をリクエストq_iにおいて広告商品d_jの期待される収益価値を示すものとして使う。制約C_requestとC_platformを満たす前提で、広告システムの最適化目標は次のように書ける:
数式(8)
リクエストは時系列順に到着する。制約C_platform(プラットフォームの1日に表示される広告の最大割合)を満たすために、システムが早期に多すぎる広告を表示する場合、後ではより少ない広告を表示するべきである。したがって上述の問題は自然、順次的意思決定問題である。
問題の定式化
このような順次的意思決定問題を解くための1つの典型的な手法は、問題をMDPまたはCMDPとしてモデル化し、問題を解くために強化学習の手法を用いることである。実際にはv(b(q_i, d_j; θ), q_i, d_j)やw(b(q_i, d_j; θ), q_i, d_j)のような環境情報を前もって得ることも正確に推論することもできないので、モデルフリー強化学習の手法に頼る。しかし、プラットフォームレベルとリクエストレベル双方の制約があるため、伝統的なCMDPはここでは直接適用できない。状態ごとの制約付CMDP(psCMDP)と呼ぶ特殊なCMDPを提案する。形式的にはpsCMDPはタプル(S, A, R, P, C_T, C_S)として定義できる。元のCMDPと比べると、ここでの違いはそれぞれの軌跡τに対して、psCMDPは軌跡レベルの制約C_T:
数式(9)
だけでなく、状態ごとの制約C_S:
数式(10)
をそれぞれのリクエストにわたって満たす必要があることにある、ここでC_S: S × A × S → ℝであり、u_sはC_Sの上界である。したがってpsCMDPに対する可能な定常方策の集合は:
数式(11)
である。psCMDPの構成要素は次のように詳細に説明される:
- S: この状態は原則として環境と制約双方を反映するべきである。私たちの設定では、s_tに対して次のような統計を考慮する: 1) 現在のリクエストq_iに関連する情報、例えば候補広告の特徴量; 2) システム文脈情報、例えば時間tまでに表示された広告の数
- A: システムがそれぞれのリクエストに対してすべての商品のスコアによって商品を選択することを考慮して、すべての候補広告のスコアを一度に調整する。それに応じて、a_t = (η_1^qi, η_1^qi, ..., η_N^d^qi))を示す、ここでη_j^qiはリクエストq_iに対するj番目の広告d_jの係数であり、1 ≤ j ≤ N^dである。
- R: R(s_t, a_t) =Σ_d∈D_st^at v(s_t, d)、ここでa_tは状態d_t, D_st^atにおけるスコア調整行動であり、D_st^atはs_tにおいて最終的に表示される広告の集合であり、v(s_t, d)はs_tにおいて広告dの表示に対する収益額であり、v(s_t, d)を広告商品と推薦商品が実際に並べ替えられた後の一般化されたセカンドプライスとして設定する。
- P: リクエストの訪問順序とシステム情報の変化の動きをモデル化する状態遷移。状態遷移におけるa_tの影響は次のように反映される: s_tにおいて異なるa_tは異なる広告につながり、表示されてきた広告の総数にもまた影響する(s_t+1の構成要素である)。状態遷移をモデル化する似た手法は以前にもCai et al.[9]、Jin et al.[19]、Wu et al.[37]で適用されてきた。
具体的には、制約に対して:
- C_T: プラットフォームレベルの制約C_platform - 1日(軌跡)にわたる広告表示の制約として定義され、割引係数γを1に設定する、CT: Σ_1 ≤ i≤M^N_i^d / Σ_1 ≤ i ≤ M^N^i ≤ α。
- C_S: リクエストレベルの制約C_request - それぞれのリクエスト(状態)にわたる広告表示制約として定義され、割引係数γを1に設定する、CS: N_i^d / N_i ≤ β, ∀_i ∈ ℕ。
上述のすべての定義に伴い、最適な方策π^*は次のように定義される:
数式(12)
この問題は、電子商取引の文献でよく研究されている文脈的bandit問題にも似ている。しかし1つの大きな違いは、文脈的bandit問題は主に広告を表示するかどうか、どこに表示するかのような固定された既知の可能な行動の集合から行動を選択することを研究する。しかし私たちの場合、累積報酬を最大化するために数億もの商品のスコア（連続変数である）を調整しなければならず、状態遷移を明確にモデル化せざるを得ない。文脈banditではなく強化学習を適用するほかの理由は次の通りである: 1) Wu et al. [37]は、強化学習は自然に制約の変化を長期的に追跡することができ、長期的な決定ができるため、軌跡の制約を強化学習にモデル化することはより大きな利点があることを示した。 2) Hu et al. [16] はさらに、強化学習の手法は文脈banditの手法より、電子商取引の推薦商品をランク付けするうえでより長期的により高い報酬をもたらすことを確認した。
3.3 解法: 制約付2段階強化学習
制約付広告最適化問題を解決するために、制約付2段階強化学習フレームワークを提案する。全体構造は図2に示され、フレームワークはアルゴリズム1で説明される。1. 全体軌跡を多くの部分軌跡に分割する。より高レベルの最適化タスクは、全体軌跡CTに渡る制約を満たすことを保証しつつ、長期的な報酬を最大化するために異なる部分軌跡に対する制約を選択するための最適化方策π_C_Tを学習することである (アルゴリズム1, 行4)。より高レベルから部分軌跡制約C_STが与えられると、より低レベルは部分軌跡制約C_STと状態ごとの制約C_S双方を満たしつつ、部分軌跡にわたって最適化方策π_b(s_t; C_ST)を学習する責任を持つ (アルゴリズム1, 行2～3)。この方法で、元のpsCMDP最適化問題は2つの独立した最適化サブ問題に分割することにより簡略化される。
適応的表示学習問題をこのような2レベルの方法で分割することで、より高い適応性を獲得し、動的に変化する電子商取引環境に素早く応答することができる。より遅い応答は企業にとって多額の財政的損失につながり得るため、この特性は重要である。第1に、プラットフォームレベルの制約は企業のビジネス戦略の変化によって頻繁に変わるかもしれない。この場合、学習したより低レベルの方策は再利用することができ、より高レベルの方策のみが再学習される必要がある。第2に、推薦システムや広告システムの他の構成要素は頻繁に変化するかもしれず、調整する方策もそれに応じて更新される必要がある。この場合、より高レベルの部分は維持しつつ、より低レベルの方策のみを再学習する必要がある。
3.3.1 低レベル制御
より低レベルでは、より高レベルの部分より提供される特定の部分軌跡制約C_STの下で、最適な広告方策を学習するサブ問題を解決しなければならない。この手法では、より正確な操作のためにそれぞれのC_STの制約を簡単に状態レベルの制約に変換する。部分軌跡制約C_STを状態レベル制約として扱うことで方策の最適性を犠牲にして、部分軌跡の最適化問題を簡略化する。明らかに、元の状態レベル制約C_SはC_STより厳格である。したがって、C_STとC_Sは簡単に1つの状態レベル制約C_STに変換できる。明らかに、状態レベル制約が満たされれば、より高レベルの制約は同時に満たされる。したがって、より高レベルの方策から部分軌跡制約C_STが与えられると、状態レベルにおけるより低レベルの方策を直接最適化できる。CMDPにおける1つの自然な手法は、それぞれの即時報酬に対して状態ごとの制約に関連する補助的な値を加えることでエージェントの方策更新を先導することである (等式4)。そして方策更新に際して、現在と未来の罰則値双方が考慮される。しかしより低レベルでは、それぞれの遷移が制約C_Sを独立に満たすため、それぞれの行動の選択は未来の状態ごとの制約C_Sを考慮する必要はない。
補助タスクで制約を強制する。
上述の理由を考慮して、状態ごとの制約に基づく補助損失関数を加えることで補助タスク [18]に似た手法を提案する。 強化学習損失関数と状態ごとの制約C_Sの損失関数をそれぞれ示すためにL_RLとL_C_Sを使う。学習中、方策は上述の2つの重み付き和を最小化する方向に更新される:
数式(13)
ここで、w_1とw_2は重み、θは値のネットワークのパラメータである。例えば、DDPG [24]の価値関数の部分に対しては、価値損失関数は:
数式(14)
であり、状態ごとの制約に対する追加の損失関数は次のように定義できる:
数式(15)
ここで、θ、θ^πとθ'はそれぞれオンライン価値ネットワークのパラメータ、方策ネットワークのパラメータ、目的価値ネットワークのパラメータであり、δ(s_t, a_t, s_t+1 | C_s)はC_sの関数である。δ(s_t, a_t, s_t+1 | C_s)の値は制約に違反した際にQ関数が更新される度合を調整するのに使われる。例えば、それぞれのリクエストのpvrを0.4に近い値に制限したい時、δ(s_t, a_t, s_t+1 | C_s) = -(pvr_t - 0.4)^2と設定することができる、ここで、pvr_tはリクエストq_tのpvr値である。直感的に、(s_t, a_t, s_t+1)が目的pvrから逸脱するほど、対応するQ値はより減少する。似た手法が、マージン分割損失を使うことでexpert demonstrationの最適性を保証するのに使われてきた [15]。
制約付Hindsight Experience Replay。
標本の効率を向上させるため、hinsight experience replay (HER) [5]の考えを利用することで、異なる部分軌跡制約に対する最適な方策の学習を促進することを提案する。HERは遷移を再利用することでDRL学習における標本の非効率性問題を緩和する。この遷移は報酬を変更するために異なる目的を使用することで得られる。この考え方を拡張して制約付Hindsight Experience Replay (CHER)を提案する。HERと違い、CHERは報酬を直接変更しない。その代わりに、CHERは学習中の追加の損失L_C_Sを定義するために異なる制約を使う。CHERにおけるより低レベルの方策を学習するアルゴリズム全体はアルゴリズム2に示される。制約C_S(それぞれの状態固有の制約)を満たすための方策を学習する時、CHERは遷移を得る: (s_t, a_t, r_t, s_t+1, c_s) (アルゴリズム2, 行5 - 8)。c_sを別の制約c_s'で置き換えることができ、制約c_s'を満たす方策を学習するためにそれらの標本 (s_t, a_t, r_t, s_t+1, c_s′)とδ(s_t, a_t, s_t+1 | c_s′)を再利用する(アルゴリズム2, 行12)。
3.3.2 高レベル制御
より高レベルのタスクは元の軌跡制約C_Tを満たしつつ、期待される長期の広告収益を最大化するために、それぞれの部分軌跡に対する軌跡レベルの制約を決定することである。それぞれの決定時点で、より高レベルの方策(制約選択方策, CCPと呼ぶ)は次の部分軌跡に対する制約を選択し、対応するより低レベルの方策はその部分軌跡の中でそれぞれのリクエストに対する広告調整スコアを引き継ぎ決定する。より低レベルの方策の実行が終わった後、その部分軌跡に渡る累積報酬が抽象化された即時報酬r^abとして返される。上述のステップは軌跡の終わりに到達するまで繰り返し、軌跡全体に渡って表示された広告の実際のパーセンテージを得る。そのパーセンテージは重みw_2を伴う追加報酬r^τとして軌跡制約と比較できる。
数式(16)
WeiMDP [13]と似て、より高レベルの方策の最適化にはDQN [27]を使う。より発展的な強化学習手法(CPO [1]、SPSA[29]のような)もうまく適用し得る。私たちのより高レベルの制御は階層的強化学習(HRL)[7, 20]の一時的な抽象化に近いことに留意されたい。しかし、HRLにおいて選択肢をどのように切り替えるかを学習すること[7]や疎な報酬の問題[20]を緩和することとは対照的に、この研究は異なる制約を異なるレベルに分解するために階層の考え方を利用する。
4 実験
4.1 実験準備
この実験は中国最大の電子商取引プラットフォームTaobaoの実データセット上で実施され、データの収集方法はセクション3における問題の説明と整合している。図1で、広告システムから提供された商品のスコア調整は推薦システムから提供された候補商品の選択とスコアリングに影響しないことを示した。広告システムから提供された商品のスコア調整は、候補商品と比較した時の広告の相対順位と最終的な混合された並べ替え結果にのみ影響する。したがって、プラットフォームから収集したオンラインデータは元の推薦商品と再評価された広告商品の混合の再並び替えを通じたスコア調整の影響を評価するのに再利用することができる。似た設定は関連研究[9, 19, 28, 39]にも見られる。具体的には、ユーザーのリクエストをシミュレートするためにユーザーのアクセスログを時系列順に再現する。psCMDPの状態はすべての候補広告の特徴量とシステムの文脈情報を統合することで表現される。行動は候補広告に対するスコア調整率として定義される。最後に、それぞれの制約に対する報酬と満足度はセクション3.2の定義にしたがって計算される。すべての詳細は付録で見ることができる。
4.2 CHERはパフォーマンスを改善するか？
CHERの効果を検証するために同じネットワーク構造とパラメータの下で、学習速度と安定性についてベースラインのDDPG [24]とCHERの使用のインパクトを比較する。C_Sがそれぞれのリクエストに対して表示される広告の数であり5を超えないという前提で、C_Sは5つの制約からなると設定する。PVR_i = 0.3, 0.35, 0.4, 0.45, 0.5のそれぞれの目的はリクエストごとに表示される広告の期待される平均を表現する。直感的には制約を入力の一部として使うことができ、すべての制約を満たすためにネットワークを使う。DDPGを使うため、評価学習の間L_CをL_Criticに加える。
数式(17)
数式(18)
ここで、wは10に設定し、PVR_iはi番目のリクエストq_iに対して表示される広告のパーセンテージである。4つの異なる乱数シードを設定し、実験結果は図3に示される。紙面の制約のため、PVR_i = 0.35, 0.4, 0.45の結果のみを示す。アルゴリズムの基準は、その結果が目的の制約に近ければより良い。異なる制約の下ではCHER付DDPGはDDPGより学習速度において優れており、制約を満たして安定化させることが見て取れる。学習後の方策の合理性を理解するため、データセット内のいくつかのユーザー訪問をランダムサンプリングした。これらのユーザー訪問における広告のスコア調整行動を記録することで(図4)、この手法の学習は直感的に次のように理解できる: 広告商品がより高い値(ecpm, 価格)を持っていれば、スコアはより高く調整される。
4.3 制約付2段階強化学習を検証する
2段階構造が収益の増加をもたらし得ることを検証するため、異なるプラットフォームレベル制約 PVR = 0.35, 0.41, 0.46(それぞれの日の広告表示率の上限はそれぞれ0.35, 0.41, 0.46, C_T = 0.35, 0.41, 0.46)と固定された状態レベル制約(PVR_i = 0.5, それぞれのリクエストの広告表示率の上限は0.5, C_S = 0.5)の下で異なる手法のパフォーマンスを比較する。新しい適応的表示機構を考慮するため、比較にふさわしい既存の手法は存在しない。本稿では、次の2つの手法をベースラインとして考慮する: 1). 手動: 広告のスコアは人間の専門家によって手動で調整される。 2). CHER + DDPG: セクション4.2で事前学習されたモデル。これは軌跡全体に対して適応的調整なしで固定されたリクエストレベル制約を使う方策に対応する。DDPGのパフォーマンスは大きく変化するため、補完的にCHERをDDPGに加え、より安定したPVR_iを達成するためこの最適化された手法(CHER + DDPG)を使う。
より高レベルの制御はパフォーマンスを改善するか？
行動方策集合の中で異なる方策を区別するため、異なるプラットフォームレベル制約PVR = 0.3, 0.35, 0.4, 0.45, 0.5の下でセクション4.2で事前学習した異なるより低レベルの方策(DDPG + CHER)を参照するためにπ_0, π_1, π_2, π_3, π_4を使う。一時的な抽象値を1時間に設定する、これはより高レベルのCCPが時間ごとに決定を下すことを意味する。サブ軌道制約を選択した後、状態レベルの行動方策は固定されたサブ軌道制約で次の時間の広告調整に対して活性化される。この実験ではCCPを学習させるために2つのDQN構造を対立構造と組み合わせる。CCPの状態はタイムスタンプ、時間ごとのeCPM、00:00から現在時刻までのPVRなどの時間情報からなる。より高レベルの方策の目的は: (1) 目的のPVRの広告表示とほぼ同じ回数を達成する; (2) 収益を可能な限り増加させる。詳細な結果は表2と図5 - 7に示される、ここでは同じ制約C_Tの下でCCPが手動とDDPG + CHERの方策に比べてそれぞれの日の収益を増加させ得ることが分かる。したがってこの手法が異なる期間で異なる数の広告を表示することを学習する、つまりリクエストにおける広告価値がより高い時、より多くの広告が表示されるほど、他の期間ではより少ない広告が表示される、ということを実証する。
なぜより高レベルの制御がパフォーマンスを改善し得るのか？
1日におけるそれぞれのリクエストの最終的に表示された広告とすべての対応する候補広告を分析する。第1に、それぞれのリクエストに対する広告表示率を固定値0.35に設定する。そしてその日の1時間ごとの総広告表示数のうち最終的に表示される広告の割合を計算する、これは図8でFix方策として示される。1日の総広告表示数をちょうど同じに維持し、Oracleはすべてのリクエストのすべての候補をスコアにしたがって再度並び替え、上位35%を表示する広告として選択することで計算される。図8で示されるOracle方策は1日に広告を表示する可能な最良の戦略であることに留意されたい。明らかに、8時から12時の期間でOracle方策の広告表示率は35%を超える。つまり収益を増加させるためにこの期間により多くの広告を表示するべきであることが分かる。それに応じて、17時から20時と22時から23時の期間では、Oracle方策の広告表示率は35%未満である。つまり見込みのない広告の数を減らしこの機会をより価値ある広告に残すべきである。それぞれの時間の詳細な広告表示パフォーマンスは表3に示される。明らかに、ベースライン方策とこの手法の収益の隔たりは主に8時から12時の間に現れる; その上、この手法は8時から12時と15時から16時の間でよりコスト効率の良い広告表示を獲得し得る。この手法は1日のPVR制約を満たしつつ、異なる期間に対応して広告表示数を動的に調整できる。
4.4 オンライン実験結果
最後に、本番環境でのA/Bテストについても報告する、このテストはTaobaoのオンラインプラットフォームでこの手法のパフォーマンスを現在デプロイされているベースライン(すべてのユーザーに固定数の広告を表示する)と比較した。実験は「好みを推測する」セクションで執り行い、そこでは推薦と広告の混合がユーザーに表示される。この手法は広告の数と位置を固定しない。今回設計した機構を、異なる数の広告を異なるユーザーに対して異なる位置に表示するように、異なるユーザーに対してそれぞれの広告のスコアを適応的に調整するよう適用した。さらなる詳細はセクション3.1に示される。公平な比較のため、すべての手法に対して同じプラットフォームレベルの制約を維持する。結果として、この手法はあらかじめ設定した制約を完全に満たしつつ、異なるユーザーに対して異なる数の広告を異なる位置に表示することが分かった。その上、RPM (Revenue Per Mille)、CTR (Clickthrough rate)、GMV (Gross Merchandise Value)においてそれぞれ9%、3%、2%の改善を観測した。これはこの適応的表示機構がプラットフォームの収益(RPM)だけでなく広告主の収益(GMV)も著しく増加させることを示している。詳細なオンライン実験の工程についても付録で示した。
5 結論
はじめに広告表示に固定位置を使う伝統的な電子商取引システムの欠陥を調査し、さらに固定位置の欠陥を緩和するより柔軟な広告表示手法(適応的表示機構)を提案する。さらに、適応的表示機構を実際のシナリオに適用する時に一連の努力があることを強調しておく。はじめに異なるレベルの制約を伴うpsCMDP問題としてモデル化し、この問題を解決するために制約付2段階強化学習フレームワークを提案する。このフレームワークは動的に変化する電子商取引環境に対して高度な適応性と素早い応答を提供する。また、新しいreplay buffer mechanism、CHERを、より低レベルでの方策学習を促進するために提案する。ここで設計した適応的表示機構はオフラインシミュレーション環境とオンライン検証において一連の制約を満たしつつ、より柔軟な広告表示手法を提供することができることを実証した。同時に、制約付2段階強化学習フレームワークは、制約を満たしつつプラットフォームの収益とユーザー体験を改善するために適応的表示機構を効果的に利用できることを検証した。
A 付録
A.1 考察: 適応的表示機構
現在の動的広告表示の研究はスポンサードサーチ、ニュースフィードにおけるストリーム広告などに注目している。これらの手法の動的広告表示は主に、固定された選択可能な広告位置に広告を表示するために適切な位置と量をどのように選択するか、またはユーザーの閲覧履歴の中でフィードの中にどのように動的に広告を挿入するかに注目している。スポンサードサーチと比べて、私たちの機構は広告位置を制限しない。その代わりに、スコア並び替えの平均によって数と位置を選択する、つまりこの手法はより柔軟性をもたらす。ニュースフィードにおけるストリーム広告と比べて、推薦商品と広告商品双方が顧客に対して共に表示され、表示順序は相対順位によって決定される混合表示シナリオを考慮する。
A.2 関連研究
A.2.1 Real-Time Biddingにおける入札最適化。
電子商取引広告のReal-Time Bidding (RTB)の設定では、インプレッション値、例えばclick-through rate (CTR) [25]、conversion rate (CVR) [22]を推論するために多くの研究が示されてきた、それらの研究はインプレッション値をより正確に推論することで入札効果の改善を助ける。その上、ユーザーのインプレッション分析、入札最適化はRTBにおけるもっとも重要な問題のひとつであり、その目的は何らかのkey performance indicator (KPI)(たとえばCTR)を最大化することを狙ってそれぞれのオークションに対してより適切な入札額を動的に設定することである[36]。しかし、現実世界の入札状況で最適化問題を解く上で制約は避けられない。したがって、より高いKPI値(たとえば累積インプレッション値)を達成するためにより賢い入札戦略が必要である、それは強化学習手法[9, 28, 39]によって達成される。これらの手法では、固定された予算制約の下で入札戦略を最適化し、予算はそれぞれの回の始めにリセットされる。Perlich et al. [28]とZhang et al. [39]は事前に収集したログデータの分布分析に基づいた静的な入札最適化フレームワークを提案する。しかし、この手法はデータ分布が不安定で極端な状況において設定が毎日変わるような設定にはうまく適用できない。このため、Cal eti al. [9]は入札問題をMDPとしてモデル化し、予算配分を線形決定問題とみなした。実験結果は動的なオークション環境下におけるこの強化学習手法の堅牢性を示す。
対照的に、私たちはより現実的なビジネス制約を考慮するより汎用的な深層強化学習フレームワークをはじめて提案する。この設定では、実用的な適応的表示機構を伴う広告表示に集中する。軌跡レベルの制約C_Tだけでなく、状態レベルの制約C_Sも考慮する。これが、従来の手法がこの設定に適用できない主な理由である。
A.2.2 制約付強化学習。
私たちは制約付最適化問題に注目し、多くの研究者がこの問題を研究してきた。ひとつの典型的な解は制約付強化学習である。Uchibe and Doya [35]は有効な制約を強制する勾配射影を使う方策勾配アルゴリズムを提案する。しかし、この手法は学習の最初に方策が不安定になることを防げない。その後、Ammar et al. [4]は安全な制約下での生涯学習のための戦略的に動機づけられた方策勾配手法を提案する。残念ながら、Ammar et al.は半正定値プログラムの最適化を含む高コストなインナーループを複雑にし、DRLの設定に対して不安定にする。同様に、Chow et al. [12]はリスク制約付強化学習のためのprimal-dual sub-gradient手法を提案する、この手法はより低いリスクのために報酬を交換する方策勾配ステップを実行すると同時に、交換係数(dual variables)を学習する。
より最近、制約付最適化問題を解決するために多くのDRLベースの手法が提案されてきた。Achiam et al.[34] は報酬制約付方策最適化(RCPO)を提案する。この手法は軌跡制約を状態ごとの罰則に変換し、学習手続きの間に制約違反信号を軌跡全体に渡って伝播することで、それぞれの状態ごとの罰則の重みを動的に調整する。
この研究は複数制約問題に異なる視点から取り組み、異なる制約間の関係を考慮に入れる。私たちは元の複数制約付最適化問題を相互に独立した単独の制約最適化問題に分離し、制約付2段階強化学習フレームワークを提案する。より重要なことには、この2段階フレームワークは非常に汎用的であり、どのような最先端強化学習アルゴリズムも双方のレベルの学習手続きに柔軟に適用できる。
A.3 ネットワーク構造と学習パラメータ
A.3.1 CHER。
actorネットワークとcriticネットワークはどちらも4層全結合ニューラルネットワークであり、それぞれ2つの隠れ層は20ニューロンから構成され、隠れ層の出力にはReLU活性化関数が適用される。調整されたスコアのサイズを制限するため、actorネットワークの出力層にはtanh関数が適用される。actorネットワークとcriticネットワークの入力は、リクエストの候補広告商品と現在表示されている商品の数からなる46の代表的な特徴量ベクトルの形状のテンソルである。actorネットワークとcriticネットワークの出力はそれぞれ15の行動と対応するQ値である。acotrの学習率は0.001、criticの学習率は0.0001、replay bufferのサイズは50000である。探索率は1から始まり50000ステップの後0.001近くまで減衰する。私たちはスコア調整操作がビジネスロジックに沿うことを保証するために、行動に対して一定の値を加える、一定のスケーリングを施すといった一定の調整をする。したがって、行動の出力は実際の調整されたスコアではない。私たちはこの調整部分を環境ロジックの一部と見なす。この調整部分はネットワークの学習には影響しない。
A.3.2 高レベル制御。
DQNネットワークは3層ニューラルネットワークを持つ。隠れ層は20ニューロンから構成され、隠れ層の出力にはReLU活性化関数が適用される。私たちは隠れ層の出力を、1) 行動と同じ数のノード、action advantage value Aをシミュレートするのに使われる、2) 単一ノード、state value Vをシミュレートするのに使われる、に接続する。最終的にQ(s, a) = V(S) + (A(s, a) - 1 / |A| Σ_a'A(s, a'))を得る。replay bufferのサイズは5000である。replay bufferをサンプリングするのに優先されるreplayを使う。学習率は0.0006である。探索率は1から始まり1000ステップのあと0.001近くまで減衰する。また、割引率γ = 1に設定する。
A.4 実験の設定
ログデータに基づき、それぞれのリクエストに対して、15の推薦商品、推薦システムによるそれらのスコア、15の広告商品の次のような情報: eCPM(有効なcost per mille)、価格、予測Click-Through-Rate(pCTR)、初期スコア、を収集する。実際のデータ量が非常に大きいため、経験的評価のためにデータの一部をサンプリングし、サンプリングされたデータが実際のデータセットを代表することを検証する。学習と評価双方の段階で、事前に収集されたデータを日ごとに分割し、シミュレーションのためにリクエストを時系列順に再現する。午前00:00から翌日までのデータの流れを軌跡と見なす。それぞれの日の始めに、広告の数が表示されリクエストの数は0にリセットされた。それぞれの日の終わりに、1日に表示された広告の数を数え、軌跡レベル制約C_Tが満たされているか判断する。
1つの状態は15の候補広告の特徴: eCPM、価格、pCTR、表示された広告の数、を含む46次元から構成される。actionは15の広告のスコアを調整する係数 action = {η_1, η_2, ..., η_15}である。actionでスコアを調整した後、15の候補広告商品と15の候補推薦商品は新しいスコアに基づいて並び替えられる。報酬は最初の表示回数10回以内の広告によって計算される。このアルゴリズムの効果をオフラインで学習しテストするためにデータを2つの方法で再現できる: 1) スコアを調整した後、表示回数10回以内の商品の広告の量がC_TとC_Sを満たすか、2) 表示された広告の報酬。実際に広告の位置はユーザー行動に強く影響する。たとえば、前面の広告はよりクリックされやすいなど。したがって報酬は次のように定義される:
数式(1)
ここで、eCPM(d)は広告sのeCPM値、fp(d)は異なる位置の影響を考慮してeCPMを修正する。f_p(d)は実際のデータを使ってfitされる(図9)。
A.5 オンライン実験
Taobaoのオンラインエンジンのアーキテクチャのため、プラットフォーム内で勾配ベースのDDPGをより広く使われている gradient-free Cross Entropy Method (CEM, 進化ベースの遺伝的アルゴリズム)に置き換えた。このアルゴリズムをオンライン環境にデプロイする時、2つの分離された工程を考慮する: (1) online servingとデータ収集; (2) オフライン学習。(1)のため、定期的に更新されるオンラインデータを記録するためにBlink(電子商取引シナリオに特化するようよう設計され最適化されたオープンソースストリーム処理フレームワーク)を使う。その上、CEMのパラメータ空間を完全に探索するため、オンライントラフィックを多くのバケットに分割し、異なるパラメータ設定の集合を同時にデプロイする。異なるバケットは異なるパラメータにより制御される。それぞれのユーザーのリクエストを処理した後、新たに生成されたデータはBlinkによって対応するデータテーブルに記録される。(2)のため、集中型学習器は最新の記録されたデータに基づいてパラメータを定期的に更新し、異なるバケットに対して異なるパラメータ集合を生成し、それらをパラメータサーバーに同期する。同時に、それぞれのバケットにデプロイされたオンライン検索エンジンは定期的にパラメータサーバーに対して最新パラメータを要求する。