1.はじめに
本記事では、ダイナミックプライシングに使用可能なアルゴリズムのまとめとして、機械学習の一般的問題設定をベースとして、過去の記事も交えていろいろと紹介していきたいと思います。
ただ並べるだけではあまりに貧相な「過去記事まとめ」にしかならないため、できる限り統一的な定義を用いて、解説を行ってみたいと思います。どれが確率変数で、時間の取り方をどうするか、などを説明していきます。
前提知識は、一般的なAI エンジニアやセールスエンジニアの強化学習知識と、高校レベルの集合論です。
1.1 離散時間と連続時間
時間の単位には、離散時間と連続時間という二つの種類が考えられます。
1.1.1 離散時間
一般的な強化学習はすべてこちらにあたります。
時間を一つ一つ数えられるのは、すべて離散時間です。\( ^{\ast 1}\)
例えばデジタル時計、ストップウォッチ、パソコンの時間等、私たちが日常で触れている時間の単位は、すべて離散時間であるといえます。
具体的な単位としては、秒や日、分など。それに加えて、ゲームにおける「ターン」や「手」「ピリオド」「フェイズ」なども、この離散時間の１単位とみなすことができます。
\( ^{\ast 1} \)数学用語で可算といいます。
1.1.2 連続時間
実際に私たちの生きている世界の時間(と考えられているもの) です。どんなに細かく区切っても、さらに細かい区切り方が存在します。\( ^{\ast 2} \)
より実情に沿ったダイナミックプライシングが可能で、値段変更のタイミング等も自由にできますが、理論的整備の難易度が離散時間の比ではありません。この理論整備において、弊社は先頭を走っているといえるでしょう。
数学的によくない解説ですが、取る範囲が数値の上と下を示した区間なら無限個、列挙なら有限個という認識で、この記事を読むにあたっては困りません。
\( ^{\ast 2} \)実はこの条件を満たす時間単位でも、離散時間になるものは構成できます。厳密な十分条件は「連続の公理」で検索してください。
1.2 有限行動と無限行動
取りうる行動の種類が有限の時、これを有限行動。無限の時、無限行動と呼ぶことにします。
厳密にはどんなに区切っても1 円単位でしか値段を変えることができませんが、Ai の出力としては無限の細かさにできますので、そういったものは無限行動とみなします。
1.3 確率的要素
確率論の基礎について簡単に解説します。
確率変数はランダムに値が変わる変数です。例えば\(X\)にあたるのは、今から投げるコインの裏表など、とにかくランダムに決定される未来の\( ^{\ast 3} \)まだわからない値です。
\( ^{\ast 3} \)ここも数学的厳密性を著しく欠く説明ですが、入門記事を読む場合としてはこの認識で十分です。後日アップロードする記事にて、確率過程と増大情報系等について解説します。
1.3.1 【発展】確率空間と確率変数
集合\(\Omega\)に対して、\( ^{\ast 4}\)部分集合族という、\(\Omega\)の部分集合の集合\( ^{\ast 5} \mathcal{F}\)は次の条件を満たすとします。
- \(\phi \in F\)
- \(A \in F \to A^c \in \mathcal{F}\)
- 可算個の\(\{A_n\}_n\)がそれぞれすべて\(A_n \in \mathcal{F}\)を満たすなら、\(\cup _n A_n \in \mathcal{F}\)
このとき、\(\mathcal{F}\)を\(\sigma\)加法族といいます。
さらに、写像\(P:\mathcal{F}\to[0,1]\)が次の条件を満たすとき、\(P\)を確立測度といいます。
- \(P(\Omega)=1\)
- \(\{A_n\}_n \)に対して、\(P(\cup_n A_n) = \Sigma _n P(A_n)\)
\((\Omega , \mathcal{F}, P)\)の組み合わせを確率空間といいます。また、\((\Omega,\mathcal{F})\)の組み合わせを可測空間といいます。
確率空間\((\Omega_1 , \mathcal{F}_1, P)\)で定義される、可測空間\((\Omega_2 \mathcal{F}_2)\)上の確率変数とは、写像\(X:\Omega_1 \to \Omega_2\)が次の条件を満たすことを言います。\( ^{\ast 6} \)
(1)
任意の\(B \in \mathcal{F}_2 \)に対して、\(X^{-1}(B) \in \mathcal{F}_1 \)
これを可測性といいます。
また、増大情報系\(\{\mathcal{F}_t\}_t\)というものを定義します。
これは任意の\(A \in \mathcal{F}_s\)に対して\(s < t\)なら\(A \in \mathcal{F}_t,\mathcal{F} \)となるような、「\(\mathcal{F}\)より小さな\(\sigma\)加法族」です。
簡単に言えば\(\mathcal{F}_t\)は、時刻\(t\)で我々が持っている情報です。
\(\mathcal{F}_t \)に対する確率変数は、もはやランダムではなく、その値がはっきりわかります。\(^{\ast 7} \)
1.4 確率変数になりうるもの
まず、今回強化学習において、重要な変数について説明します。
- \(s:\)今の状態。
- \(a:\)行動
- \(s^\prime:\)次の状態
- \(r:\)即時報酬
ここに時刻を付け加えると、時刻\(t\)の状態を\(s_t\)と書き表せます。\(s_{t}^{\prime}=s_{t+1}\)です。
詳しい定義などはコチラを参照してください。
\( ^{\ast 4} \)\(\omega\)が何者かという問いはかなり難しいです。アカシックレコード的なものだと思っていただいてもかまいません。
\( ^{\ast 5} \)この書き方もかなりまずいですが、今はこう表記させてください。
\( ^{\ast 6} \)当然、\(\mathcal{F}\)を挿げ替えれば、確率変数かどうか変わります。この辺が、確率過程論等では非常に重要です。
\( ^{\ast 7} \)コインを投げる前が\(\mathcal{F}_s\)、投げた跡が\(\mathcal{F}_t\)と考えればわかりやすいと思います。時刻\(s\)ではまだ可測性を満たさない（可測じゃない）確率変数だが、時刻\(t\) には可測になっている\(\to\)値がわかる、ということです。厳密には、その値がわかるという情報を入れた状態が\(\mathcal{F}_t\)です。
2 アルゴリズムの主な種類
ここでは、ダイナミックプライシングの代表的なアルゴリズムを、どの変数が確率変数か、時間が連続か離散か、行動が無限か有限かという観点で分類していきます。
2.1 ルールベース
機械学習とは言えない手法ですが、単純なやり方で済む状況であればこちらのほうが良いこともまれにあります。ダイナミックプライシングの一種です。
確率変数になるのは\(s^\prime, r\)です。理屈の上では\(a\)も確率変数にできますが、私の知る限りではそのようなアルゴリズムを採用しているものは見たことがありません。\( ^{\ast 8} \)
\(a\)の取る範囲は基本的には有限個。ただし稀に無限個のパターンもあります。\( ^{\ast 9} \)
\(t\)のとる範囲は離散時間です。
\( ^{\ast 8} \)学習を行わないので、乱択にする意味がありません。
\( ^{\ast 9} \)例えばECサイトのダイナミックプライシングで、ユニークアクセス数などを参照している場合。
2.2 統計的機械学習手法
強化学習とルールベースの中間に位置すると言える手法です。教師あり、と呼ばれることも。
高い結果は出しづらいですが、安定しています。これで十分なこともけっこうあったりします。
非常に有名な論文”Customized Regression Model for Airbnb Dynamic Pricing”はここに分類される手法であるといえるでしょう。
確率変数になるのはルールベースと同じく\(s^\prime , r\)です。\(a\)は手法によります。例えば上記のAirbnbの論文の手法では確率変数です。
\(a\)の取る範囲は有限、無限どちらでも対応できますが、ニューラルネットで回帰するのが基本である以上、無限のほうがより性能を発揮できると考えられます。
分類は現時点ではいずれも離散時間ですが、連続時間対応も不可能ではないと考えられます。
2.3 強化学習（DQN）
DQN (Deep Q Network)はコチラなどで解説しています。
確率変数になるのは\(s^\prime, r\)。手法によっては\(a\)も確率変数になります。*10
\(a\)の取る範囲は必ず有限個になります。
時間の取る範囲は離散時間ですが、連続時間への対応も可能です。
\( ^{\ast 10} \)弊社オリジナル技術であるイプシロン-ゼロもここは確率変数です。
2.4 強化学習（DDPG）
別の研究員が書いた記事ですが、DDPGの詳しい解説はコチラなどを参照ください。
こちらは、\(s^\prime, r, a\)が全て確率変数になります。
\(a\)の値が取る範囲は無限個です。
連続時間、離散時間両方への対応が可能です。
3 強化学習型ダイナミックプライシングの展望
ここまで、ダイナミックプライシングの一般的なアルゴリズムに関する解説を行いました。ここからは、今後の研究に期待を持ち、弊社も調査研究を進めている分野について、同様に分類をさせていただきます。
3.1 連続時間型強化学習
現在弊社の主な研究テーマになっている研究領域です。
過去の解説は下記をご覧ください。
2020年11月時点、現在論文を準備中なので、もうしばらくお待ちください。三部作くらいになりそうです。
確率変数なのは、\(s^\prime , a, r ^{\ast 11}\)です。時間の区切りは連続時間固定。行動は基本的には無限のほうがやりやすいと考え られます。\(^{\ast 12}\)
\( ^{\ast 11} \)実はこの手法のみ、\(r_t\)は確率超過程となり、古典的に定義できません。時間積分の累積報酬\(R_t\)となって初めて古典的な確率過程として記述ができます。
\( ^{\ast 12} \)連続時間の即物的な利点は、「任意のタイミングで値段を変更できる」というところにあります。理論的正当化の難易度は離散時間の比では ありません。飛躍型確率微分方程式に新しい領域を開拓する必要があります。
3.2 部分観測マルコフ決定過程
過去の解説としては、「POMDP～制限情報下での強化学習について～」などがあります。
これは唯一、\(s\)が確率変数になる（可測でない）という極めて珍しい手法です。
しかし、手法としては珍しくとも、現実的な状況としては自然であるとも考えられます。
ダイナミックプライシングに必要な値段決定のファクターは、とてもじゃありませんがスクレイピングで観測しきれません。
ある程度売り上げへの影響が大きい要素は観測できても、100％にはなりえません。
そこで、「実際の状況は観測できないが、情報の一部は入ってくるので、それを使う」というのがこの部分観測マルコフ決定過程の手法となります。
専門的解説は「POMDP～制限情報下での強化学習について～」をご覧ください。
\(s, s^\prime, r, a\)すべてが確率変数。時間は現状は離散時間固定。
行動のとりうる範囲は有限でも無限でも可能です。
3.3 リスク評価型強化学習
分布型強化学習については「強化学習における報酬分布の近似アルゴリズムについて」などの解説記事があります。
これは、普通の強化学習が報酬の期待値のみを見ているのに対して、この手法は分散などを検証することができ、上振れは少なくとも安定している行動を適切に選ぶことができます。
確率変数なのは\(s ^\prime , r, a\)で、\(a\)は有限でも無限でも対応可能。
現状時間の区切りは離散時間のみです。
3.3.1 イプシロン-ゼロ
2020年11月時点、スルーへの実装を進めている新手法「イプシロン-ゼロ」は、このリスク評価型強化学習によるダイナミックプライシングを簡単に行えるようになる手法です。
DQNへの導入については、もう社会実験段階。DDPG への導入はアルゴリズムを詰めております。\(^{\ast 13}\)
4 まとめ
新展開の項目についてですが、それぞれが共存不可能な項目ではありません。極端な話、「連続時間部分観測リスク評価型強化学習」といった全部乗せも可能です。\(^{\ast 14}\)
さて、ここまでいろんな手法についてまとめてきましたが、これらを踏まえて分類を表にしました。
基本的には、代表的な要素を書いていますので、例外は存在しえます。
なかなかこういった、専門家向けではないけれどもなにもわかっていない人向けではない、という記事には、難易度調整に骨が折れます。かなり書くのが難しかった記事であると言えるでしょう。
次回からしばらくの間、一般的なエンジニアやセールスエンジニア向けの高等数学入門記事を公開していきます。どうかお待ちください。
\( ^{\ast 13} \)DQNへの実装難易度ですが、実はめちゃくちゃ簡単です。すでにDQN がある状況であれば10分くらいでできます。
\( ^{\ast 14} \)理論解析が地獄になりそうですが。Zakai方程式が出てきそうです。