二分探索よりお得なオンライン価格戦略

オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です．

出典は R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.1 です． この記事自体は Haifeng Xu 先生の講義スライド の第 1 回をかなり参考にしてます． ゲーム理論と機械学習の様々な興味深いトピックが網羅されていておすすめです．

問題設定

• あなたは A さんに $N$ 個のリンゴ を，$1$ 日 $1$ 個ずつ売りに行きます．$N$ は事前に分かっています．
• A さんはリンゴの価値を $v$ 円だと思っています．簡単のため $0 \le v \le 1$ とします．$v$ の値は $N$ 日間を通して一定です．
• あなたは $0 \le v \le 1$ であることは知っていますが，正確な $v$ の値を知りません．
• あなたは $t$ 日目に販売価格 $p_t$ を決めます．
  • $p_t \le v$ であれば A さんはリンゴを買い，あなたは $p_t$ 円を得ます．
  • $p_t > v$ であればリンゴは売れず，稼ぎは $0$ 円です．

あなたは毎日上手く価格 $p_t$ を設定することで，$N$ 日間の合計売上をできるだけ大きくしたいと考えます． 良い価格戦略を見つけたいという問題です．

戦略の評価尺度：リグレット

上の問題は，いわゆるオンライン学習の一種です． この分野でよく用いられる戦略の評価尺度としてリグレットというものがあります． 今回の問題の場合リグレットは以下のように定義されます． $$\mathrm{Regret}(N) = Nv - \sum_{t=1}^N p_t \mathbf{1}({p_t \le v}).$$ ただし， $$\mathbf{1}({p_t \le v}) = \begin{cases} 1 & \text{if} &\text{$p_t \le v$ } \\ 0 & \text{else} & \end{cases}$$ です． また，$v$ は「あなたが戦略を決める前に，A さんの心の中で任意の $0$ 以上 $1$ 以下の値に固定される」と考え，$v$ が事前にどう選ばれたとしても，リグレットの意味で良い戦略を見つけることを目指します．

リグレットの第一項は「 $v$ を知っていた場合の最適戦略の合計売上」と見ることができます． $v$ を知っていれば毎日 $p_t = v$ 円で売れば良いので，合計売上は $Nv$ 円ですね．

第二項は実際に $p_1,\dots, p_N$ 円と価格設定したときの合計売上を表しています．

このリグレットは「 $v$ を知らないことで何円売上を損し得るか」という観点で，$p_t$ を決める戦略を評価しています． リグレット（の上界）が小さいほど良い戦略と言えます．

自明な $\mathrm{O}(N)$ リグレット戦略

まずは自明な戦略から見ていきます．高い値段でリンゴが売れると嬉しいので，とりあえず毎日 $p_t = 1$ に設定したとします． 運良く $v = 1 = p_t$ なら $Nv = N$ 円の合計売上を得ることができて，リグレットは $0$ です．

しかし，$v$ は $0$ 以上 $1$ 以下の任意の値を取り得るため，$v=1$ 以外のケースも考えなければなりません． 例えば，$v = 0.9999$ なのに毎日 $p_t = 1$ に設定すると，リンゴは一個も売れず合計売上は $0$ です．一方 $Nv = 0.9999N$ ですので，リグレットの値は $0.9999N$ です． 仮に $N = 10000$ 日間リンゴを売り続けたとすると，$9999$ 円も損をしてしまいます．

このように，価格を決め打ちする戦略のリグレットは，最悪の場合 $N$ に比例することになります． リグレット上界は $\mathrm{O}(N)$ ということです． $N$ が大きな値になると，とても損してしまいます．

二分探索による $\mathrm{O}(\log N)$ リグレット戦略

もう少し賢い戦略を考えます．伝家の宝刀†二分探索†です．

具体的には， 最初は $l=0$, $u=1$ としておき，$t$ 日目には $p_t = (l+u)/2$ 円でリンゴを売ってみて，

• 売れれば $l = p_t$
• 売れなければ $u = p_t$

と更新していきます．

大雑把に解析してみます． まず，常に $v\in[l,u]$ が成り立ちます． また，その区間長 $u-l$ は毎日半分になっていくため， およそ $\log N$ 日間探索すれば，$u - l = 1/N$ まで区間を絞ることができます． そして $\log N$ 日目より後は $p_t = l$ 円で売り続けたとすると，毎日高々 $1/N$ 円しか損をしません．

この戦略なら，たとえ最初の $\log N$ 日間の売上が $0$ 円でも，合計売上は $$0\times \log N + (v - 1/N)\times(N - \log N) \ge Nv -\log N -1$$ 円です．よって $\mathrm{Regret}(N) = \mathrm{O}(\log N)$ となることが分かります．これなら $N = 10000$ 日間売っても高々 $15$ 円程度しか損をしません． だいぶ良い戦略になりました．

二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略

前置きが長くなりましたが，ここからが本題です．

よくある「$N$ 個の値の中から真の $v$ を見つける」タイプの問題の場合，比較回数のオーダーを $\log N$ より良くする事はできません．†二分探索†が最強です．

一方，リグレット上界を小さくしたいという今回の設定の場合，二分探索戦略に少し手を加えて $\mathrm{O}(\log \log N)$ リグレット上界を達成することができます．

重要なポイントは，売れなかったときの稼ぎは $0$ 円だが，売れれば $p_t$ 円稼げるということです．$v$ を当てることに失敗しても，売ることができた場合の方が傷は浅いのです． この観察を踏まえると「ちょっと安めに $p_t$ を設定して，手堅く稼いだ方がいいんじゃないか？」という気がしてきます．

実際その通りです．次のような戦略を考えます．

• 二分探索と同様に区間 $[l_t, u_t]$ を持っておく．初期値は $l_1 = 0$, $u_1=1$．
• ステップ幅 $\Delta_t$ も持っておく．初期値は $\Delta_1=1/2$．
• $t$ 日目には $p_t = l_t + \Delta_t$ 円に設定．結果に応じて次のように更新：
  • 売れれば $l_{t+1} = p_t$, $u_{t+1} = u_t$, $\Delta_{t+1} = \Delta_t$．
  • 売れなければ $l_{t+1} = l_t$, $u_{t+1} = p_t$, $\textcolor{red}{\Delta_{t+1} = (\Delta_t)^2}$．

$\Delta_t < 1$ ですので，二乗するとステップ幅は小さくなることに注意してください．

売れる限りはステップ幅は変えず $$p_t = l_t+ \Delta_t, \quad p_{t+1} = l_t+2\Delta_t, \quad\dots$$ と徐々に値段を上げていき， 売り損ねたら保持している区間の上限とステップ幅を小さくする，ということをしています．

以上を $u_t - l_t \le 1/N$ となるまで繰り返します． $u_t - l_t \le 1/N$ となってからは，二分探索戦略と同様に $p_t = l_t$ 円で売り続けます．

この戦略のリグレット上界を調べてみます．

一度 $u_t - l_t \le 1/N$ になれば，二分探索戦略の場合と同様に，その後に損する額の合計は高々 $N \times 1/N = 1$ 円です（リグレットの増分は定数です）．

以下では，$u_t - l_t \le 1/N$ になるまでにどれくらいリグレットが増えるかを，いくつかの補題を示しながら見ていきます．

補題 1

$\Delta_t$ は必ず $2^{-2^{i}}$ ($i=0,1,\dots$) という形で書ける．

これは $\Delta_1 = 1/2$ と $\Delta_{t+1} =$ $\Delta_t$ or $(\Delta_t)^2$ から分かります．

補題 2

$\Delta_{t+1} = (\Delta_t)^2$ と更新されたとき，$u_{t+1} - l_{t+1} = \sqrt{\Delta_{t+1}}$ が成立．

これは，売れなかった場合の更新規則から $$u_{t+1} = p_t = l_t + \Delta_t = l_{t+1} + \sqrt{\Delta_{t+1}}$$ ですので成り立ちます．

以上を踏まえて，$u_t - l_t \le 1/N$ に至るまでのステップ幅の値の種類数を考えます． 一度も売り損ねない場合は $\Delta_t = 1/2$ の $1$ 種類のみですので， 一度は売り損ねて $\Delta_{t+1} = (\Delta_t)^2$ の更新が起こるとします． ステップ幅が更新された直後のうち，初めて $u_t - l_t \le 1/N$ となるまでに取り得るステップ幅の値は，補題 1, 2 と $$2^{-2^{i}} = 1/N \Leftrightarrow i = \log \log N$$ から高々 $\mathrm{O}(\log \log N)$ 種類です．

よって， $u_t - l_t \le 1/N$ となるまでのステップ幅の値の種類数は $\mathrm{O}(\log \log N)$ で抑えられます． あとは，各ステップ幅の値 $\Delta$ におけるリグレットの増分が定数なら（次の補題 3 が成り立つなら）$\mathrm{Regret}(N) = \mathrm{O}(\log \log N)$ です．

補題 3

どの $\Delta$ についても，ステップ幅の値が $\Delta$ の間のリグレットの増分は定数．

この補題を示します． リンゴが売れずステップ幅が $\Delta_{t+1} = \Delta$ に更新されるときの $l_{t+1}$, $u_{t+1}$ をそれぞれ $l$, $u$ とします． 補題 2 から $u - l = \sqrt{\Delta}$ です． また，二分探索のときと同様に $v \in [l, u]$ が成り立っています．

ステップ幅の値が $\Delta$ になってからは，次に売れなくなるまで $$p_t = l+ \Delta, \quad p_{t+1} = l+2\Delta, \quad \dots$$ と値段を上げていきます． ステップ幅の値が $\Delta$ である間に損をするのは次の 2 パターンです．

• 売れない場合：売り損ねるとステップ幅は更新されるため，ステップ幅が $\Delta$ の間に売り損ねるのは高々 $1$ 回．損をする額は最大 $1$ 円．
• 売れる場合：$v \in [l, u]，$$u - l = \sqrt{\Delta}$ より，一度売れると最大 $\sqrt{\Delta}$ 円損をする．売れる度に $\Delta$ ずつ $p_t$ を増やすため，ステップ幅が $\Delta$ である間に売れる回数は高々 $(u - l)/\Delta = 1/\sqrt{\Delta}$ 回．よってトータルで損する金額は高々 $\sqrt{\Delta} \times 1/\sqrt{\Delta} = 1$ 円．

以上より，ステップ幅の値が $\Delta$ の間に損をする額は高々 $2$ 円です．

これで補題 3 も示され，$\mathrm{Regret}(N) = \mathrm{O}(\log \log N)$ となりました！ めでたしめでたし．

まとめ

今回のようなオンライン学習の手法を設計する上では，exploration と exploitation のバランスを調整することが重要です．上の結果は「二分探索は exploration の手法としては最適だが，exploitation とのバランスを取るにはもっと良い方法がある」とも捉えられます．

R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.3 では，この問題に対するリグレット下界が $\mathrm{\Omega}(\log \log N)$ であることが示されています． つまり，上で紹介した戦略はリグレットのオーダーの意味で最適です． 往々にして，リグレット下界を示す方が上界を示すよりもずっと大変です． こういうシンプルな手法で上下界が一致する結果はとても綺麗で素晴らしいですね👏

この結果の存在は NII の藤井さん に教えてもらいました． 面白い話題を提供してくれたことに感謝します．