(57)【要約】  凸包設定部８１は、候補になる行動ベクトルの集合である行動集合の凸包を設定する。重心スパナ設定部８２は、凸包に含まれる行動ベクトルの次元数の要素をその凸包の重心スパナとする。分解問題解決部８３は、上記要素および凸包に関して、その要素のそれぞれを次元数のポイントに分解するための分解問題を解決する。行動選択部８４は、試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、フェーズに分割されたラウンド数分のポイントを行動として選択する。経験的推定量算出部８５は、選択された行動に基づいて、損失ベクトルの経験的推定量を算出する。線形最適化問題解決部８６は、経験的推定量および凸包に関して、上記要素およびその経験的推定量により算出される損失を最小化するための線形最適化問題を解決する。凸包更新部８７は、線形最適化問題の解決により得られた最適化要素に基づいて、凸包を小さくするように更新する。
2020235049.tif 000002
【特許請求の範囲】
【請求項１】
バンディット問題を最適化する最適化装置であって、
候補になる行動ベクトルの集合である行動集合の凸包を設定する凸包設定部と、
前記凸包に含まれる前記行動ベクトルの次元数の要素を当該凸包の重心スパナとする重心スパナ設定部と、
前記要素および前記凸包に関して、当該要素のそれぞれを前記次元数のポイントに分解するための分解問題を解決する分解問題解決部と、
試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、前記フェーズに分割された前記ラウンドの数のポイントを行動として選択する行動選択部と、
選択された行動に基づいて、損失ベクトルの経験的推定量を算出する経験的推定量算出部と、
前記経験的推定量および前記凸包に関して、前記要素および当該経験的推定量により算出される損失を最小化するための線形最適化問題を解決する線形最適化問題解決部と、
前記線形最適化問題の解決により得られた最適化要素に基づいて、前記凸包を小さくするように更新する凸包更新部とを備えた
ことを特徴とする最適化装置。
【請求項２】
行動選択部は、ポイントの重みに応じて選択する行動の回数を決定し、決定された回数に基づいて、分解された前記ポイントを行動として選択する
請求項１記載の最適化装置。
【請求項３】
凸包更新部は、フェーズごとに凸包の更新を行い、
行動選択部は、順次実行されるフェーズに含まれるラウンドが２の階乗のオーダで増加するように、フェーズに含まれるラウンド数を決定する
請求項１または請求項２記載の最適化装置。
【請求項４】
凸包更新部は、損失の値が行動ベクトルのノルムの上界および損失ベクトルのノルムの上界に基づいて決定される範囲内になるように凸包を更新する
請求項１から請求項３のうちのいずれか１項に記載の最適化装置。
【請求項５】
線形最適化問題解決部は、線形最適化オラクルを実行する装置に対して算出された経験的推定量を送信する制御を行い、当該装置から最適化要素を取得することにより線形最適化問題を解決する
請求項１から請求項４のうちのいずれか１項に記載の最適化装置。
【請求項６】
バンディット問題を最適化する最適化方法であって、
候補になる行動ベクトルの集合である行動集合の凸包を設定し、
前記凸包に含まれる前記行動ベクトルの次元数の要素を当該凸包の重心スパナとし、
前記要素および前記凸包に関して、当該要素のそれぞれを前記次元数のポイントに分解するための分解問題を解決し、
試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、
前記フェーズに分割された前記ラウンドの数のポイントを行動として選択し、
選択された行動に基づいて、損失ベクトルの経験的推定量を算出し、
前記経験的推定量および前記凸包に関して、前記要素および当該経験的推定量により算出される損失を最小化するための線形最適化問題を解決し、
前記線形最適化問題の解決により得られた最適化要素に基づいて、前記凸包を小さくするように更新する
ことを特徴とする最適化方法。
【請求項７】
ポイントの重みに応じて選択する行動の回数を決定し、決定された回数に基づいて、分解された前記ポイントを行動として選択する
請求項６記載の最適化装置。
【請求項８】
バンディット問題を最適化するコンピュータに適用される最適化プログラムであって、
前記コンピュータに、
候補になる行動ベクトルの集合である行動集合の凸包を設定する凸包設定処理、
前記凸包に含まれる前記行動ベクトルの次元数の要素を当該凸包の重心スパナとする重心スパナ設定処理、
前記要素および前記凸包に関して、当該要素のそれぞれを前記次元数のポイントに分解するための分解問題を解決する分解問題解決処理、
試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、前記フェーズに分割された前記ラウンドの数のポイントを行動として選択する行動選択処理、
選択された行動に基づいて、損失ベクトルの経験的推定量を算出する経験的推定量算出処理、
前記経験的推定量および前記凸包に関して、前記要素および当該経験的推定量により算出される損失を最小化するための線形最適化問題を解決する線形最適化問題解決処理、および、
前記線形最適化問題の解決により得られた最適化要素に基づいて、前記凸包を小さくするように更新する凸包更新処理
を実行させるための最適化プログラム。
【請求項９】
コンピュータに、
行動選択処理で、ポイントの重みに応じて選択する行動の回数を決定させ、決定された回数に基づいて、分解された前記ポイントを行動として選択させる
請求項８記載の最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バンディット問題を効率的に解決する最適化装置、最適化方法および最適化プログラムに関する。
【背景技術】
【０００２】
バンディット問題における線形最適化（以下、バンディット線形最適化と記す。）は、多くの分野で幅広く利用される重要な問題である。バンディット線形最適化は、具体的には、以下に述べる試行を繰り返す。【０００３】
プレイヤーには、試行開始時に、ｄ次元の（試行の）行動ベクトル集合Ａ⊆ＲｄとＴラウンドの試行が与えられる。各ラウンドｔ∈［Ｔ］：＝｛１，２，…，Ｔ｝において、プレイヤーは、行動ａｔ∈Ａを選択する。そして、ラウンドごとに変化し得る未知の損失ベクトルｌｔのもとで、プレイヤーは、損失ｌｔＴａｔを観測する。【０００４】
バンディット線形最適化の特別な応用例として、様々なオンライン意思決定問題を扱うことができる。例えば、グラフＧ＝（Ｖ，Ｅ）およびｓ，ｔ∈Ｖが与えられ、ｓ−ｔ間のパスのすべての特徴ベクトルの集合となるＡ⊆Ｒ｜Ｅ｜が設定されたとする。これにより、この問題を、バンディット最短経路、または、適応ルーティング（Ａｄａｐｔｉｖｅ  ｒｏｕｔｉｎｇ）とみなすことができる。この設定では、ｌｔ∈Ｒ｜Ｅ｜がパスの（未知の）長さに対応し、バンディットフィードバックｌｔＴａｔが、選択されたｓ−ｔ間のパスの長さを意味する。【０００５】
上記応用以外に、バンディット線形最適化は、例えば、最小スパニングツリー、最小カット、ナップサック問題などの組み合わせ最適化問題や、線形計画法、半正定値計画法などの連続最適化問題のバンディット版を含む。【０００６】
プレイヤーの性能は、以下に示す式１で定義されるような後悔ＲＴ（ａ＊）（ただし、ａ＊∈Ａ）により評価される。式１は、プレイヤーの決定｛ａｔ｝に対する累積損失と、任意の固定された戦略ａ＊に対する累積損失との間の差を意味する。バンディット線形最適化の最優先事項は、任意のａ＊に対して小さな後悔を得ることである。【０００７】
【数１】
2020235049.tif 000003
【０００８】
バンディット問題を効率的に解くための方法が各種知られている。例えば、非特許文献１には、オーダＯ〜（Ｔ１／２）で後悔限界を得るため、確率的および敵対的多腕バンディット問題を効率的に解く方法が記載されている。非特許文献１に記載された方法では、セミバンディットフィードバックの下での確率的設定において、問題特有の後悔下限を導出し、そのスケーリングを決定空間の次元で扱う。なお、Ｏ〜はＯの上付きチルダであり、Ｏ〜表記をした場合、ｄおよびｌｏｇ（Ｔ）における多項式の因子は無視する。【０００９】
また、オーダＯ〜（Ｔ１／２）のアルゴリズムは、最悪の場合に、少なくともΩ（Ｔ１／２）の後悔を黙認することが知られている。これは、オーダＯ〜（Ｔ１／２）の後悔限界を有するアルゴリズムが、Ｔに依存して最適な性能を達成することを意味する。【００１０】
なお、非特許文献２には、線形計画法および整数計画法の理論について記載されている。また、非特許文献３には、不透明なフィードバックにおけるオンライン線形最適化のためのアルゴリズムが記載され、非特許文献４には、ｎ次元の対数分布からサンプリングするための効率的なアルゴリズムが記載されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Richard Combes, et al., “Combinatorial Bandits Revisited”, In Advances in Neural Information Processing Sysytems, pp.2116-2124, 2015.
【非特許文献２】A.Schrijver, “Theory of linear and integer programming”, John Wiley & Sons, 1998.
【非特許文献３】B. Awerbuch, R. D. Kleinberg, “Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches”, Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pp.45-53. ACM, 2004.
【非特許文献４】L. Lovasz, S. Vempala, "The geometry of logconcave functions and sampling algorithms", Random Structures & Algorithms, 30(3), pp.307-358, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、非特許文献１に記載された方法のように、行動ベクトル集合Ａが指数関数的に大きい場合や無限集合である場合、計算上の問題を有する。すなわち、プレイヤーの選択可能な行動の種類が指数関数的に大きい場合、非特許文献１に記載された方法をコンピュータの機能で実現しようとしても、現実的な時間で解くことができないという問題がある。そのため、コンピュータの機能の改善させるためには、取得できる後悔限界をより小さくできるように、効率的にバンディット問題を解くことができる方法が望まれている。【００１３】
そこで、本発明は、効率的に解けるようにバンディット問題を最適化できる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明による最適化装置は、バンディット問題を最適化する最適化装置であって、候補になる行動ベクトルの集合である行動集合の凸包を設定する凸包設定部と、凸包に含まれる行動ベクトルの次元数の要素をその凸包の重心スパナとする重心スパナ設定部と、上記要素および凸包に関して、その要素のそれぞれを次元数のポイントに分解するための分解問題を解決する分解問題解決部と、試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、フェーズに分割されたラウンドの数のポイントを行動として選択する行動選択部と、選択された行動に基づいて、損失ベクトルの経験的推定量を算出する経験的推定量算出部と、経験的推定量および凸包に関して、上記要素およびその経験的推定量により算出される損失を最小化するための線形最適化問題を解決する線形最適化問題解決部と、線形最適化問題の解決により得られた最適化要素に基づいて、凸包を小さくするように更新する凸包更新部とを備えたことを特徴とする。【００１５】
本発明による最適化方法は、バンディット問題を最適化する最適化方法であって、候補になる行動ベクトルの集合である行動集合の凸包を設定し、凸包に含まれる行動ベクトルの次元数の要素をその凸包の重心スパナとし、上記要素および凸包に関して、その要素のそれぞれを次元数のポイントに分解するための分解問題を解決し、試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、フェーズに分割されたラウンドの数のポイントを行動として選択し、選択された行動に基づいて、損失ベクトルの経験的推定量を算出し、経験的推定量および凸包に関して、上記要素およびその経験的推定量により算出される損失を最小化するための線形最適化問題を解決し、線形最適化問題の解決により得られた最適化要素に基づいて、凸包を小さくするように更新することを特徴とする。【００１６】
本発明による最適化プログラムは、バンディット問題を最適化するコンピュータに適用される最適化プログラムであって、コンピュータに、候補になる行動ベクトルの集合である行動集合の凸包を設定する凸包設定処理、凸包に含まれる行動ベクトルの次元数の要素をその凸包の重心スパナとする重心スパナ設定処理、上記要素および凸包に関して、その要素のそれぞれを次元数のポイントに分解するための分解問題を解決する分解問題解決処理、試行回数を示すラウンドをｌｏｇオーダのフェーズに分割し、フェーズに分割されたラウンドの数のポイントを行動として選択する行動選択処理、選択された行動に基づいて、損失ベクトルの経験的推定量を算出する経験的推定量算出処理、経験的推定量および凸包に関して、上記要素およびその経験的推定量により算出される損失を最小化するための線形最適化問題を解決する線形最適化問題解決処理、および、線形最適化問題の解決により得られた最適化要素に基づいて、凸包を小さくするように更新する凸包更新処理を実行させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、効率的に解けるようにバンディット問題を最適化できる。
【図面の簡単な説明】
【００１８】
【図１】本発明による最適化装置の第一の実施形態の構成例を示すブロック図である。
【図２】第一の実施形態の最適化装置の動作例を示すフローチャートである。
【図３】本発明による最適化装置の第二の実施形態の構成例を示すブロック図である。
【図４】第二の実施形態の最適化装置の動作例を示すフローチャートである。
【図５】本発明による最適化装置の概要を示すブロック図である。
【図６】少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態を図面を参照して説明する。第一の実施形態では、線形最適化オラクルと呼ぶ（コールする）ことができるという仮定の下、オーダＯ（Ｔ１／２）の後悔限界を達成することを目的とする。オラクル（神託）は、オフラインでＡについての線形最適化問題を解くことができる概念上の装置に対応する。すなわち、損失ベクトルｌ∈Ｒｄが与えられると、オラクルは、以下の式２に示すａ＊を出力する。
【００２０】
【数２】
2020235049.tif 000004
【００２１】
なお、この想定（すなわち、オラクルの呼び出し）はオンライン最適化の文脈で知られており、劣線形な後悔を取得する効率的なバンディットのアルゴリズムを展開するための最小要件である。実際、効率的な劣線形の後悔バンディットアルゴリズムが与えられると、オフライン問題に対する効率的なアルゴリズムを構築できる。これは、オフライン問題が計算上困難（例えば、ＮＰ困難）である場合、バンディット問題もまた困難であることを意味する。
【００２２】
多くの応用例において、バンディットアルゴリズムを効率的に計算するには、“オラクル複雑度”に強く依存する。ここでは、“オラクル複雑度”とは、線形最適化オラクルを呼び出す回数である。この傾向は、オフライン線形最適化問題を解くための計算時間（すなわち、オラクルから答えを得るための時間）が他の計算時間を支配するのに十分大きい場合、特に顕著である。そこで、本実施形態では、“オラクル複雑度”を小さくして、バンディット問題を効率的に解けるようにするためのアルゴリズムを説明する。
【００２３】
また、第一の実施形態では、後述する確率的（stochastic）な設定のために、高確率でオーダＯ〜（（ｄ３Ｔ）１／２）の後悔を達成し、オーダＯ（ｐｏｌｙ（ｄ）ｌｏｇＴ）のオラクル複雑度を有するアルゴリズムを説明する。
【００２４】
まず、以下の定理を定める。なお、以下の説明では、非公式（ｉｎｆｏｒｍａｌ）な定理についても、単に定理と記す。
【００２５】
＜定理１＞
ｔ＝１，２，…，ＴにおいてｌｔがＲｄ上の分布に従うと仮定する。このとき、以下に示すアルゴリズムが存在する。
（１）アルゴリズムの出力が、全てのａ＊∈Ａにおいて、高確率でＲＴ（ａ＊）＝Ｏ〜（（ｄ３Ｔ）１／２）を満たす。
（２）アルゴリズムは、線形最適化オラクルをオーダＯ（ｐｏｌｙ（ｄ）ｌｏｇＴ）回数分呼び出す。
（３）線形最適化オラクルを除く計算時間は、Ｏ（ｐｏｌｙ（ｄ，Ｔ））のオーダである。
【００２６】
一般的に知られたＯ〜（Ｔ１／２）の後悔を得るアルゴリズムでは、少なくとも、Ω（Ｔ）オラクル複雑度を必要とする。また、第一の実施形態で示すアルゴリズムは、Ｔにおいて準線形であるＯ〜（Ｔ１／２）の後悔限界とオラクル複雑度を持つアルゴリズムである。
【００２７】
さらに、第二の実施形態では、後述する非確率的（stochastic）な設定のために、期待されるオーダＯ〜（（ｄ３Ｔ）１／２）の後悔を達成し、オーダＯ（ｐｏｌｙ（ｄ）Ｔ）のオラクル複雑度を有するアルゴリズムを説明する。そこで、以下の定理を定める。
【００２８】
＜定理２＞
以下に示すアルゴリズムが存在する。
（１）アルゴリズムの出力が、全てのａ＊∈Ａにおいて、Ｅ［ＲＴ（ａ＊）］＝Ｏ〜（（ｄ３Ｔ）１／２）を満たす。
（２）アルゴリズムは、線形最適化オラクルをオーダＯ（ｐｏｌｙ（ｄ）Ｔ）回数分呼び出す。
（３）線形最適化オラクルを除く計算時間は、Ｏ（ｐｏｌｙ（ｄ，Ｔ））のオーダである。
【００２９】
実施形態１．
まず、第一の実施形態の最適化装置について説明する。第一の実施形態におけるポイントは、行動の段階的な排除を組み合わせること、および、重心スパナである。段階的な排除に基づくアルゴリズムでは、意思決定のラウンドをフェーズ（ラウンドのセグメント化したもの）に分割する処理が行われる。また、各フェーズの最後で、可能な行動が排除されるため、有望な行動だけが残される。
【００３０】
段階的な排除を行うアルゴリズムでは、各フェーズで選択されたすべてのａｔがフェーズの最初に決定される。これは、オラクル複雑度が、ラウンドの数に依存するのではなく、フェーズの数に依存することを意味する。第一の実施形態で示すアルゴリズムでは、フェーズの数が、Ｏ（ｐｏｌｙ（ｄ）ｌｏｇＴ）のオーダであり、また、重心スパナに対する効率的なアルゴリズムにより、各フェーズにおけるオラクルの呼び出し回数は、Ｏ（ｐｏｌｙ（ｄ））のオーダになる。結果、全体として、オーダＯ（ｐｏｌｙ（ｄ）ｌｏｇＴ）のオラクル複雑度になる。
【００３１】
また、第一の実施形態では、バンディット線形最適化において確率的（stochastic）な設定を想定する。確率的な設定とは、損失ベクトルｌｔが、ラウンドｔ＝１，２，…，Ｔにおいて、互いに独立で、Ｗ⊆Ｒｄ上の同一の確率分布Ｄに従うことを想定するものである。アルゴリズムの性能は、損失ベクトルｌｔのランダム性およびアルゴリズムの内部的なランダム性に関して、上記式１における後悔ＲＴ（ａ＊）の期待値により評価される。
【００３２】
以下、バンディット線形最適化の問題設定について再掲する。
【００３３】
ゲームが開始する前に、プレイヤーには、Ｔラウンドの試行、ｄ次元の行動ベクトル集合Ａ（行動集合と記すこともある。）Ａ⊆Ｒｄ、並びに、行動ベクトルａｔ（以下、単に行動ａｔと記すこともある。）∈Ｋのノルムの上界Ｌ＞０および損失ベクトルｌｔ∈Ｗのノルムの上界Ｒ＞０が与えられる。
【００３４】
各ラウンドｔ＝１，２，…，Ｔにおいて、プレイヤーは、行動ａｔ∈Ｋを選択する。一方、環境によって損失ｌｔベクトルが選択されることで、プレイヤーは、損失ｌｔＴａｔを観測する。また、プレイヤーは、線形最適化オラクルＯＡにのみアクセスできる。言い換えると、本実施形態の最適化装置が、線形最適化オラクルＯＡを実現する装置を呼び出す処理を制御していると言える。なお、線形最適化オラクルＯＡを実現する装置は、本実施形態の最適化装置と同一の装置で実現されていてもよく、異なる装置で実現されていてもよい。
【００３５】
プレイヤーの目的は、より小さな後悔ＲＴ（ａ）を得ること（言い換えると、一定期間における報酬を最大化すること）である。ここで、後悔ＲＴ（ａ）は、任意のａ∈Ｋについて、以下に例示する式３により算出される、
【００３６】
【数３】
2020235049.tif 000005
【００３７】
また、本実施形態では、行動集合ＡがＲｄのコンパクトなサブセットであると仮定する。そして、ｗ∈Ｒｄの中の重みベクトルについてＡで線形最適化するためのアルゴリズム（オラクル）が存在することを想定する。そして、任意の入力ｗを線形最適化オラクルＯＡ：Ｒｄ→Ａに与えることができるものとし、そのオラクルは、以下に例示する式４を満たす点ＯＡ（ｗ）∈Ａを満たす点を出力する。
【００３８】
【数４】
2020235049.tif 000006
【００３９】
ここで、いくつかの仮定を行う。まず、以下の（ａ）〜（ｂ）を満たすような正の実数Ｌ，Ｒが存在するとする。
（ａ）すべてのｔ∈［Ｔ］について、||ｌｔ||≦Ｌである。
（ｂ）すべてのａ∈Ａについて、||ａ||２≦Ｒである。また、
（ｃ）Ｋ：＝Ｃｏｎｖ（Ａ）が、正の体積を有する。すなわち、∫Ｋ１ｄｘ＞０である。
【００４０】
上記（ａ）および（ｂ）についての仮定は、バンディット線形最適化では一般的である。また、Ａについての線形最適化オラクルが与えられた場合、一般性を失うことなく、上記（ｃ）を仮定できる。実際、Ａがｄよりも小さい次元のサブスペースに含まれている場合、線形最適化オラクルを多項式時間で呼び出すことにより、それを検出可能であり、冗長な次元を無視することで、Ｋを全次元にすることができる。
【００４１】
さらに、以下に示すように、有理数のサイズまたはビット長を定義する。
【００４２】
＜定義１＞
ｐおよびｑが相対的な素数である場合に、有理数ｒ＝ｐ／ｑについて、有理数ｒのサイズｓｉｚｅ（ｒ）を、以下に例示する式５で定義する。
【００４３】
【数５】
2020235049.tif 000007
【００４４】
また、有理数ベクトルｘ＝（ｘ１，…，ｘｄ）∈Ｑｄについて、ベクトルｘのサイズｓｉｚｅ（ｘ）を、以下に例示する式６で定義する。
【００４５】
【数６】
2020235049.tif 000008
【００４６】
また、サブセットＰが有限有理ベクトルの凸包である場合、Ｐは、有理ポリトープ（超多面体）である。同じように、Ｐが有理数によって表現された線形不等式の有限集合を用いて表現される非空のコンパクト集合である場合、すなわち、Ｐ＝｛ｘ∈Ｒｄ｜Ａｘ≦ｂ｝であるような、有理行列Ａ＝（ａｉｊ）i∈［ｍ］，ｊ∈［ｄ］∈Ｑｍ×ｄおよび有理ベクトルｂ＝（ｂｉ）ｉ∈［ｍ］∈Ｑｍが存在する場合、Ｐは有理ポリトープである。本実施形態では、有理不等式（Ａ，ｂ）のサイズｓｉｚｅ（（Ａ，ｂ））を、以下に例示する式７で定義する。
【００４７】
【数７】
2020235049.tif 000009
【００４８】
なお、各ｘ∈Ａのサイズが高々φであるような有理数の有限集合Ａに対して、ＰがＰ＝Ｃｏｎｖ（Ａ）として表される場合、Ｐは、サイズが高々ｐｏｌｙ（ｄ，φ）である線形不等式によって表現され得る。また、||ｘ||≦Ｒであるようなｘ∈Ｒｄが与えられた場合、以下に例示する式８および式９に示すようなｘ〜（ｘの上付きチルダ）∈Ｑを得ることができる。
【００４９】
【数８】
2020235049.tif 000010
【００５０】
次に、コンパクト凸体Ｐ⊆Ｒｄにおける、線形最適化問題ＬＰ（linear optimization problem）、分離問題ＳＰ（separation problem）および分解問題ＤＰ（decomposition problem ）を、以下のように定義する。これらの問題が、線形最適化オラクルで解決可能な問題である。
【００５１】
＜線形最適化問題：ＬＰ＞
ベクトルｗ∈Ｒｄが与えられたときに、ｗＴｘ＊＝ｍｉｎｘ∈ＰｗＴｘであるようなベクトルｘ＊∈Ｐを発見する。
【００５２】
＜分離問題：ＳＰ＞
ベクトルｙ∈Ｒｄが与えられたときに、ｙがＰに属するか否かを判断し、さらに、ｙがＰに属さない場合に、ｗＴｙ＜ｍｉｎｘ∈ＰｗＴｘであるようなベクトルｗ∈Ｒｄを発見する。
【００５３】
＜分解問題：ＤＰ＞
ベクトルｘ∈Ｒｄが与えられたときに、ｘ＝λ０ｘ０＋…＋λｄｘｄであるようなＰの頂点ｘ０，…，ｘｄおよびλ０，…，λｄ≧０を発見する。
【００５４】
上記３つの問題の処理を軽減させる有名な楕円体法では、以下の関係を示している。
ＬＰ：解決可能  ⇔  ＱＰ：解決可能  ⇒  ＤＰ：解決可能。
【００５５】
なお、非特許文献２には、Ｐ⊆Ｒｄが高々φのサイズの線形不等式で定義できる有理ポリトープである場合において、以下に示す定理３（ａ），定理３（ｂ）および定理３（ｃ）が記載されている。
【００５６】
定理３（ａ）：分離問題を解決するアルゴリズムＳＥＰが存在する場合、ＳＥＰを高々ｐｏｌｙ（ｄ，φ，ｓｉｚｅ（ｗ））回呼び出すことによって、ｗ∈Ｑｄについての線形最適化問題を解決できる。
定理３（ｂ）：線形最適化問題を解決するアルゴリズムＯＰＴが存在する場合、ＯＰＴを高々ｐｏｌｙ（ｄ，φ，ｓｉｚｅ（ｙ））回呼び出すことによって、ｙ∈Ｑｄについての分離問題を解決できる。
定理３（ｃ）：線形最適化問題を解決するアルゴリズムＯＰＴが存在する場合、ＯＰＴを高々ｐｏｌｙ（ｄ，φ，ｓｉｚｅ（ｘ））回呼び出すことによって、ｘ∈Ｑｄについての分解問題を解決できる。
【００５７】
次に、重心スパナに関する定義および定理を記載する。
【００５８】
＜定義２＞
線形スパンがＲｄであるサブセットをＳ∈Ｒｄとし、Ｃ＞１とする。ここで、すべてのｘ∈Ｓが、範囲［−Ｃ，Ｃ］の中の係数を用いてＸの要素の線形結合として表せる場合、集合Ｘ＝｛ｘ１，…，ｘｄ｝⊆Ｓは、Ｓに関するＣ−重心スパナである。
定理４：Ｐ⊆Ｒｄが、適切な線形部分空間に含まれていないコンパクトな集合であるとする。任意のＣ＞１についてＬＰについてのアルゴリズムＯＰＴが与えられた場合、ＯＰＴへの呼び出しをオーダＯ（ｄ２ｌｏｇＣ（ｄ））で行うことにより、ＰについてのＣ−重心スパナを多項式時間で計算できる（非特許文献３参照）。
【００５９】
次に、対数凹分布のアルゴリズムについて記載する。ｌｏｇｐが凸関数であるような確率密度関数ｐ：Ｋ→Ｒ＞０を、凸集合Ｋ∈Ｒｄ上の確率分布が有する場合、その確率分布を対数凹分布と呼ぶ。以下に示す定理５は、凸関数ｆ：Ｋ→Ｒの価値オラクルが与えられた場合、対数凹型分布ｐ（ｘ）∝ｅｘｐ（−ｆ（ｘ））からサンプルを近似できることを意味する。
【００６０】
定理５：Ｐが非ゼロのルベーグ測度を有する凸体であるとする。また、ｆ：Ｐ→Ｒが凸関数であり、ｐがｅｘｐ（−ｆ（ｘ））に比例する対数凹分布であるとする。さらに、ε＞０とする。Ｐのメンバーシップオラクルとｆの価値オラクルへのアクセスを与えられる場合、以下の（ｉ）および（ｉｉ）に示すようなｐから近似的にサンプルするアルゴリズムが存在する（非特許文献４参照）。
（ｉ）生成された分布とｐとの間の総変動距離が高々εである。
（ｉｉ）オーダＯ〜（ｄ５）の時間で前処理した後、各サンプルは、オーダＯ〜（ｄ４／ε４）の時間で生成される。
【００６１】
なお、分布ｐの平均をμ（ｐ）と記載し、分布ｐの共分散をＣｏｖ（ｐ）と記載する。上述する定理５は、効率的に、対数凹分布ｐの平均μ（ｐ）および共分散Ｃｏｖ（ｐ）を近似的に計算できることを意味する。
【００６２】
以上の定理および定義を適宜参照しながら、本実施形態の最適化装置の動作を説明する。上述するように、本実施形態では、ｔ＝１，２，…，Ｔについて、ｌｔが、Ｗ上の分布Ｄに従うと仮定する。また、ｌ＊を以下の式１０のように表記する。また、ξｔ＝ｌｔ−ｌ＊と表記する。
【００６３】
【数９】
2020235049.tif 000011
【００６４】
図１は、本発明による最適化装置の第一の実施形態の構成例を示すブロック図である。本実施形態の最適化装置１００は、初期化部１０と、最適化部２０とを備えている。
【００６５】
初期化部１０は、各種処理に必要な初期化処理を行う。具体的には、初期化部１０は、候補になるｄ次元の行動ａの集合（以下、行動集合と記す。）Ａ⊆Ｒｄの凸包Ｃｏｎｖ（Ａ）（＝Ｐ１）を設定する。また、初期化部１０は、小さな後悔（ｓｍａｌｌ  ｒｅｇｒｅｔ）を得る確率を制御するパラメータ（δ＞０）を設定する。
【００６６】
最適化部２０は、ラウンドＴを、Ｋ個＝Ｏ（ｌｏｇＴ）のフェーズに分割する。具体的には、最適化部２０は、ｋ番目のフェーズにラウンドがΘ（２ｋ）含まれるように、ラウンドＴを分割する。
【００６７】
また、最適化部２０は、ｋ番目のフェーズの開始時に、行動集合Ｐｋを再帰的に設定する。例えば、Ｐ１＝Ｃｏｎｖ（Ａ）と初期化された場合、最適化部２０は、ｋが大きくなるにつれて、ｌ＊Ｔｘの値がすべてのｘに対して小さくなるように（Ｐ１⊇Ｐ２⊇…⊇ＰＫになるように）Ｐｋを設定する。
【００６８】
また、最適化部２０は、ｋ番目のフェーズの開始時に、凸包Ｐｋの２−重心スパナＸｋ＝｛ｘｋ１，…，ｘｋｄ｝を計算する。なお、重心スパナＸｋに含まれる行動を実行できた場合、好ましいｌ＊の推定値を構築できる。ただし、Ｘｋに含まれる各要素は、特にＡが離散値の場合、通常Ａに属していない。これに対処するため、最適化部２０は、重みλｋｉ０，…，λｋｉｄ≧０について、λｋｉ０＋…＋λｋｉｄ＝１、かつ、λｋｉ０ｘｋｉ０＋…＋λｋｉｄｘｋｉｄ＝ｘｋｉを満たすように各ｘｋｉをポイント｛ｘｋｉ０，…，ｘｋｉｄ｝∈Ａに分解する。そして、最適化部２０は、各ｊ＝０，１，…，ｄについて、ｘｋｉｊを、Ｔｋｉｊ∝λｋｉｊ回実行する。以下、ｔラウンドで実行された行動をａｔと記す。
【００６９】
すなわち、最適化部２０は、上記要素Ｘｋのそれぞれおよび凸包Ｐ＝Ｃｏｎｖ（Ａ）についての分解問題（ＤＰ）を解き、ｘｋｉ＝λｋｉ０ｘｋｉ０＋…＋λｋｉｄｘｋｉｄになるような分解ｘｋｉ０，…，ｘｋｉｄ∈Ａおよびλｋｉ０，…，λｋｉｄを得る。また、最適化部２０は、各フェーズｋにおいて、行動ａｔ＝ｘｋｉｊを、（ｔｋｉｊ＋１）番目のラウンドから（ｔｋｉ，ｊ＋１）番目のラウンドまで、ちょうどＴｋｉｊ回選択する。なお、Ｔｋｉｊおよびｔｋｉｊは、以下に示す式１１および式１２で算出される。すなわち、最適化部２０は、ポイントの重みλに応じて選択する行動の回数を決定していると言える。
【００７０】
【数１０】
2020235049.tif 000012
【００７１】
最適化部２０は、ｋ番目のフェーズで得られたフィードバック（すなわち、選択された行動）に基づいて、ｌ＊の経験的推定量ｌ＾ｋを以下の式１３を用いて計算する。なお、ｌ＾は、上付きハットである。
【００７２】
【数１１】
2020235049.tif 000013
【００７３】
最適化部２０は、以下の式１４に示すように、損失ｌ＾Ｔｋｘを最小化するようなベクトルｘ＊ｋを見つけるため、Ｐ＝Ｐｋおよびｗ＝ｌ＾ｋについての線形最適化問題（ＬＰ）を解く。具体的には、最適化部２０は、線形最適化オラクルを実行する装置（図示せず）に対して算出された経験的推定量ｌ＾ｋを送信する制御を行い、その装置から最適化された要素（以下、最適化要素と記す。）ｘ＊ｋを取得することにより線形最適化問題を解決する。
【００７４】
【数１２】
2020235049.tif 000014
【００７５】
ｘ＊ｋの算出後、最適化部２０は、線形最適化問題の解決により得られたｘ＊ｋに基づいて、以下の式１５に基づいて、凸包Ｐｋを小さくするように更新する。
【００７６】
【数１３】
2020235049.tif 000015
【００７７】
初期化部１０と、最適化部２０とは、プログラム（最適化プログラム）に従って動作するコンピュータのプロセッサ（例えば、ＣＰＵ（Central Processing Unit ）、ＧＰＵ（Graphics Processing Unit））によって実現される。
【００７８】
例えば、プログラムは、最適化装置１００が備える記憶部（図示せず）に記憶され、プロセッサは、そのプログラムを読み込み、プログラムに従って、初期化部１０および最適化部２０として動作してもよい。また、最適化装置１００の機能がＳａａＳ（Software as a Service ）形式で提供されてもよい。
【００７９】
初期化部１０と、最適化部２０とは、それぞれが専用のハードウェアで実現されていてもよい。また、各装置の各構成要素の一部又は全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組合せによって実現されもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各装置の各構成要素の一部又は全部は、上述した回路等とプログラムとの組合せによって実現されてもよい。
【００８０】
また、最適化装置１００の各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【００８１】
次に、本実施形態の最適化装置の動作を説明する。図２は、本実施形態の最適化装置１００の動作例を示すフローチャートである。本動作例において、行動集合Ａ⊆Ｒｄ、δ＞０、Ｌ＞０およびＲ＞０であるとする。
【００８２】
初期化部１０は、行動集合Ａ⊆Ｒｄの凸包Ｃｏｎｖ（Ａ）（＝Ｐ１）を設定する。また、初期化部１０は、ラウンド数ｔを０に設定する（ステップＳ１）。以降、最適化部２０は、各フェーズｋについて、ステップＳ２からステップＳ１６までの処理を繰り返す。
【００８３】
最適化部２０は、Ｘｋ＝｛ｘｋ１，…，ｘｋｄ｝⊆Ｐｋを、Ｐｋの２−重心スパナとする（ステップＳ３）。また、最適化部２０は、パラメータζｋを、以下に示す式１６のように設定する（ステップＳ４）。
【００８４】
【数１４】
2020235049.tif 000016
【００８５】
また、最適化部２０は、各ｄについて、ステップＳ５からステップＳ１２までの処理を繰り返す。
【００８６】
最適化部２０は、凸包Ｐ＝Ｃｏｎｖ（Ａ）およびｘ＝ｘｋｉについての分解問題（ＤＰ）を解き、ｘｋｉ＝λｋｉ０ｘｋｉ０＋…＋λｋｉｄｘｋｉｄになるような分解ｘｋｉ０，…，ｘｋｉｄ∈Ａおよびλｋｉ０，…，λｋｉｄを得る（ステップＳ６）。
【００８７】
さらに、最適化部２０は、各ｄについて、ステップＳ７からステップＳ１０までの処理を繰り返す。
【００８８】
最適化部２０は、ラウンドの選択回数を算出する。具体的には、最適化部２０は、選択回数Ｔｋｉｊと、選択するラウンドｔｋｉｊを上記に示す式１１および式１２に基づいて算出する（ステップＳ８）。この処理によって、最適化部２０が、順次実行されるフェーズｋに含まれるラウンドが２の階乗のオーダで増加するように、フェーズに含まれるラウンド数を決定していると言える。最適化部２０は、行動ａｔ＝ｘｋｉｊを、（ｔｋｉｊ＋１）番目のラウンドから（ｔｋｉ，ｊ＋１）番目のラウンドまで、Ｔｋｉｊ回選択する（ステップＳ９）。
【００８９】
最適化部２０は、選択するラウンドｔｋｉｊを、ｔｋ，ｉ＋１，０＝ｔｋｉ，ｄ＋１と更新する（ステップＳ１１）。
【００９０】
最適化部２０は、ｌ＊の経験的推定量ｌ＾ｋを上記に示す式１３を用いて計算する（ステップＳ１３）。
【００９１】
最適化部２０は、上記の式１４に示すベクトルｘ＊ｋを見つけるため、凸包Ｐ＝Ｐｋおよびｗ＝ｌ＾ｋについての線形最適化問題（ＬＰ）を解く（ステップＳ１４）。最適化部２０は、Ｐｋを、上記の式１５に基づいて更新する（ステップＳ１５）。すなわち、最適化部２０は、フェーズごとに凸包Ｐの更新を行う。
【００９２】
次に、本実施形態の最適化装置１００を用いた場合の後悔（Ｒｅｇｒｅｔ）について、分析結果を具体的に説明する。具体的には、上記アルゴリズムで達成される後悔上限を与える次の定理を示す。
【００９３】
＜定理６＞
ｌｔがＴ≧２でｔ＝１，…，Ｔの独立同分布に従うと仮定し、｛ａｔ｝ｔ＝１Ｔが上述する処理で与えられると仮定する。この場合、少なくとも１−δの確率で、後悔は以下の式１７に示すように限界がある。
【００９４】
【数１５】
2020235049.tif 000017
【００９５】
次に、オラクル複雑度についての分析を説明する。
上述するように、最適化部２０は、２−重心スパナＸｋを計算する必要があった。一方、上述する定理４より、Ｐ＝Ｐｋについての線形最適化問題（ＬＰ）を解くアルゴリズムを、オーダＯ（ｐｏｌｙ（ｄ））の回数分呼び出すことによって、最適化部２０は、２−重心スパナを構築できる。さらに、上述する定理３（ａ）は、Ｏ（ｐｏｌｙ（ｄ））のオーダで分離問題（ＳＰ）を解くことによって、線形最適化問題（ＬＰ）を解くことができることを意味する。
【００９６】
Ｐ＝Ｐｋについての分離問題（ＳＰ）は、以下に示す手順で解くことができる。
【００９７】
１．ｙ∈Ｐ１か否か決定する。そして、ｙ∈Ｐ１でない場合、ｗＴｙ＜ｍｉｎｘ∈Ｐ１ｗＴｘのようなｗ∈Ｒｄを出力する。上述する定理３（ｂ）より、この処理は、ＡについてのＬＰオラクルをオーダＯ（ｐｏｌｙ（ｄ））の回数分呼び出すことによって行うことができる。一方、ｙ∈Ｐ１である場合、以下の２．の処理が行われる。
【００９８】
２．ｊ＝１，…，ｋ−１について、ｌ＾ｊＴ（ｙ−ｘｋ＊）＞ＬＲ２−ｊである場合には、ｌ＾ｊを出力する。すべてのｊ＝１，…，ｋ−１について、ｌ＾ｊＴ（ｙ−ｘｋ＊）≦ＬＲ２−ｊである場合には、ｙ∈Ｐｋであることを意味する。
【００９９】
上記１．および２．の手順では、ＬＰオラクルを、オーダＯ（ｐｏｌｙ（ｄ））の回数分呼び出し、Ｏ（ｐｏｌｙ（ｄ，Ｋ））＝Ｏ（ｐｏｌｙ（ｄ，ｌｏｇＴ））の回数分実行する。したがって、最適化部２０は、図２に示すステップＳ３において、ＫについてのＬＰオラクルをＯ（ｐｏｌｙ（ｄ））回数分呼び出す効率的な処理を行う。
【０１００】
同様に、図２に示すステップＳ６およびステップＳ１４をｃＡについてのＬＰオラクルをＯ（ｐｏｌｙ（ｄ））回数分呼び出すことによって、実行できる。他のステップでは、オラクルにアクセスする必要がなく、効率的に処理が行うことができる。また、ｋを基準とする反復回数Ｋは制限されているので、ＡについてＬＰを解くためのオラクル呼び出しの回数は、Ｏ（ｐｏｌｙ（ｄ）Ｋ）＝ Ｏ（ｐｏｌｙ（ｄ）ｌｏｇＴ）である。
【０１０１】
以上のように、本実施形態では、初期化部１０が、行動集合Ａの凸包Ｐを設定し、最適化部２０が、凸包Ｐに含まれる（行動ベクトルの）次元数ｄ個の要素Ｘを、その凸包Ｐの重心スパナとし、最適化部２０が、要素Ｘおよび凸包Ｐに関して、その要素のそれぞれを次元数のポイントに分解する分解問題（ＤＰ）を解決する。また、最適化部２０が、ラウンドＴをｌｏｇ（Ｔ）オーダのフェーズｋに分割し、フェーズに分割されたラウンドの数のポイントを行動として選択し、選択された行動に基づいて、損失ベクトルの経験的推定量ｌ＾ｋを算出する。そして、最適化部２０が、経験的推定量ｌ＾ｋおよび凸包Ｐに関して、要素Ｘおよび経験的推定量ｌ＾ｋにより算出される損失を最小化する線形最適化問題（ＬＰ）を解決し、得られた最適化要素ｘ＊ｋに基づいて、凸包Ｐを小さくするように更新する。よって、効率的に解けるようにバンディット問題を最適化できる。
【０１０２】
また、本実施形態では、最適化部２０が、線形最適化オラクルＯＡを実行する装置に対して算出された経験的推定量ｌ＾ｋを送信する制御を行い、その装置から最適化要素ｘ＊ｋを取得することにより線形最適化問題を解決する。よって、線形最適化オラクルを実行する装置に対する呼び出し回数を抑制して計算時間を抑制できるため、バンディット問題を解決するコンピュータの機能を改善できる。言い換えると、本実施形態の最適化装置は、装置としてのオラクルに行う指示を適切に制御する装置であるともいえる。
【０１０３】
実施形態２．
次に、第二の実施形態の最適化装置について説明する。第二の実施形態では、バンディット線形最適化において非確率的（non-stochastic）な設定を想定する。非確率的な設定とは、確率的な設定とは対照的に、いかなる生成モデルも仮定しない設定である。例えば、損失ベクトルｌｔは前の行動ａ１，…，ａｔ−１に応じて敵対的な方法で選択される可能性も存在する。
【０１０４】
図３は、本発明による最適化装置の第二の実施形態の構成例を示すブロック図である。本実施形態の最適化装置２００は、初期化部３０と、最適化部４０とを備えている。
【０１０５】
本実施形態の最適化装置２００は、凸集合Ｋｔ（ｊ）⊆ＲｄをＡ⊆Ｋｔ（ｊ）であるように維持する。なお、ｔは、ラウンドに対応し、ｊ∈｛０，１，…｝は、インデックスである。また、最適化装置２００は、各ラウンドにおいて、増加する重みの更新に基づいて、凸関数ｚｔ：Ｒｄ→Ｒ≧０を更新する。なお、ｚｔの正式な定義は後述される。
【０１０６】
また、以下の説明では、関数ｚｔに比例するＫｔ（ｊ）上の分布の確率密度関数をｑｔ（ｊ）と記す。すなわち、ｑｔ（ｊ）は、以下の式１８に示す性質を満たす。
【０１０７】
【数１６】
2020235049.tif 000018
【０１０８】
また、ｑｔ（ｊ）の平均μｔ（ｊ）∈Ｒｄおよびｑｔ（ｊ）の共分散行列Σｔ（ｊ）∈Ｒｄ×ｄを、それぞれ以下に示す式１９で表す。
【０１０９】
【数１７】
2020235049.tif 000019
【０１１０】
ここで、上述する定理５と同様の想定のもと、以下に補助定理を示す。
＜補助定理＞
少なくとも１−δになる確率で、以下に示す式２０を得るようにｐｏｌｙ（ｄ，１／ε，ｌｏｇ（１／δ））でμ＾（μの上付きハット）およびΣ＾（Σの上付きハット）を出力する。なお、ベクトルｘ∈Ｒｄおよび正の半正定値行列Ａ∈Ｒｄ×ｄにおいて、||ｘ||Ａ：＝（ｘＴＡｘ）１／２と定義する。
【０１１１】
【数１８】
2020235049.tif 000020
【０１１２】
上記補助定理より、最適化装置２００は、以下に示す式２１が少なくとも（１−δｔ（ｊ））の確率で成り立つようにμｔ（ｊ）およびΣｔ（ｊ）の推定量を計算できる。なお、δｔ（ｊ）∈（０，１）は、δｔ（ｊ）＝１／Ｔｋ（ｋ＋１）として表され、ｋは、μｔ（ｊ）およびΣｔ（ｊ）が計算されるごとに値が増加される。
【０１１３】
さらに、Ｂｔ（ｊ）＝（ｂｔ１（ｊ），…，ｂｔｄ（ｊ））∈Ｒｄ×ｄをＢｔ（ｊ）Ｂｔ（ｊ）Ｔ＝Σ＾ｄ（ｊ）を満たすような行列であるとし、εｔ（ｊ）⊆Ｒｄを、以下の式２１により定義する。
【０１１４】
【数１９】
2020235049.tif 000021
【０１１５】
したがって、本実施形態の最適化装置は、μ＾から予め定めた範囲（１／４ｅ（ｂｔｉ（ｊ）））内（すなわち、有限集合εｔ（ｊ））の任意のベクトルｙと凸集合とを分離する超平面を導出するための分離問題を解決する。また、このベクトルの含まれる範囲は、凸集合の分布の確率密度関数の共分散行列を導出する行列Ｂの要素（ｂｔ１（ｊ），…，ｂｔｄ（ｊ））に基づいて決定される。
【０１１６】
初期化部３０は、各種処理に必要な初期化処理を行う。具体的には、初期化部３０は、凸集合Ｋ（＝Ｋ１（０））を設定する。すなわち、初期化部３０は、行動集合を含むような凸集合を設定する。また、初期化部３０は、学習率η＞０や、誤差限界ε＞０を設定してもよい。なお、本実施形態において、Ｔは、対象期間Ｔ∈Ｎを表わす。
【０１１７】
最適化部４０は、ｙ∈εｔ（ｊ）およびＰ＝Ｋ：＝Ｃｏｎｖ（Ａ）についての分離問題（ＳＰ）を解き、Ｋｔ（ｊ）を更新する。ここでは、Ｋと任意のｙを隔てる超平面が存在することとする。すなわち、最適化部４０は、ベクトルｙと凸集合とを分離する超平面を導出するための分離問題を解決する。なお、以下では、ｓｔが（while loopの）繰り返し処理の回数を表すものとし、繰り返し処理後は、εｔ：＝εｔ（ｓｔ）⊆Ｋが得られるものとする。また、繰り返し処理後の平均、共分散行列および行列を、それぞれ、μ＾ｔ＝μ＾ｔ（ｓｔ），Σ＾ｔ＝Σ＾ｔ（ｓｔ），および，Ｂｔ＝Ｂｔ（ｓｔ）と記す。
【０１１８】
また、最適化部４０は、εｔからｘをランダムに選択する。具体的には、最適化部４０は、ランダムに、一様に、正負の値を示すパラメータσｔ∈｛−１，１｝および選択された行動ベクトルの次元数内の値ｉｔ∈［ｄ］を選択する。最適化部４０は、ｘ＝μ＾ｔ＋（σｔ／４ｅ）ｂｔｉｔとし、選択されたｉｔおよびσｔに基づいてｘを算出する。そして、最適化部４０は、このｘおよび凸集合Ｐ＝Ｋについて、分割問題（ＤＰ）を解き、ｘの分割を得る。具体的には、最適化部４０は、λｔ０＋…＋λｔｄ＝１、かつ、λｔ０ｘｔ０＋…＋λｔｄｘｔｄ＝μ＾ｔ＋（σｔ／４ｅ）ｂｔｉｔを満たすようなｘｔ０，…，ｘｔｄ∈Ｋおよびλｔ０，…，λｔｄ≧０を計算する。
【０１１９】
そして、最適化部４０は、分解されたポイントの重みλｔｓの確率で行動ａｔ＝ｘｔｓを実行し、フィードバック（損失）ｌｔＴａｔを得る。そのフィードバックに基づき、最適化部４０は、損失ベクトルｌｔの推定量ｌ＾ｔを、以下に示す式２２により算出する。
【０１２０】
【数２０】
2020235049.tif 000022
【０１２１】
最適化部４０は、算出された推定量ｌ＾ｔによって、関数ｚｔを、以下に示す式２３により算出する。
【０１２２】
【数２１】
2020235049.tif 000023
【０１２３】
補助定理のアルゴリズムを使用すると、上述する式２０は、少なくとも１−δｔ（ｊ）の確率で成立する。ここで、δｔ（ｊ）は、以下に示す式２４で表される。
【０１２４】
【数２２】
2020235049.tif 000024
【０１２５】
なお、初期化部３０と、最適化部４０とは、プログラム（最適化プログラム）に従って動作するコンピュータのプロセッサによって実現される。
【０１２６】
次に、本実施形態の最適化装置の動作を説明する。図４は、本実施形態の最適化装置２００の動作例を示すフローチャートである。本動作例において、凸集合Ｋｔ（ｊ）⊆Ｒｄ（Ａ⊆Ｋｔ（ｊ））、学習率η＞０、誤差限界ε＞０、対象期間Ｔ∈Ｎ、Ｌ＞０およびＲ＞０であるとする。
【０１２７】
初期化部３０は、凸集合Ｋ１（０）←Ｂ（０,Ｒ）に設定する（ステップＳ１０１）。
【０１２８】
最適化部４０は、ｔ＝１，２，…，Ｔについて、以下のステップＳ１０２からステップＳ１１６までの処理を繰り返す。はじめに、最適化部４０は、ｊ←０に設定する（ステップＳ１０３）。
【０１２９】
さらに、最適化部４０は、任意のｙ∈εｔ（ｊ）について、以下の式２５に示す超平面ｗ∈Ｒｄが存在する間、ステップＳ１０４からステップＳ１０７までの処理を繰り返す。
【０１３０】
【数２３】
2020235049.tif 000025
【０１３１】
最適化部４０は、Ｋの内容を更新する。具体的には、最適化部４０は、Ｋの範囲を超平面ｗに基づいて縮小させるように、以下に示す式２６を用いて更新し（ステップＳ１０５）、ｊ←ｊ＋１とする（ステップＳ１０６）。なお、γはパラメータである。すなわち、最適化部４０は、導出された超平面に基づいて凸集合Ｋをより小さな凸集合に更新する。
【０１３２】
【数２４】
2020235049.tif 000026
【０１３３】
ステップＳ１０４からステップＳ１０７のループを抜けた後、最適化部４０は、ｓｔ←ｊに設定し（ステップＳ１０８）、Ｋｔ←Ｋｔ（ｓｔ）に設定する（ステップＳ１０９）。最適化部４０は、ランダムに、一様にσｔ∈｛−１，１｝およびｉｔ∈［ｄ］を選択する（ステップＳ１１０）。
【０１３４】
次に、最適化部４０は、Ｐ＝Ｋおよびｘ＝μ＾ｔ＋（σｔ／４ｅ）ｂｔｉｔについての分割問題（ＤＰ）を解き、ｘの分割を得る。具体的には、最適化部４０は、λｔ０＋…＋λｔｄ＝１、かつ、λｔ０ｘｔ０＋…＋λｔｄｘｔｄ＝μ＾ｔ＋（σｔ／４ｅ）ｂｔｉｔを満たすような分割ｘｔ０，…，ｘｔｄ∈Ａおよびλｔ０，…，λｔｄ≧０を計算する（ステップＳ１１１）。
【０１３５】
最適化部４０は、λｔｓ（ただし、ｓ＝０，…，ｄ）の確率で行動ａｔ＝ｘｔｓを実行し（ステップＳ１１２）、損失ｌｔＴａｔを得る（ステップＳ１１３）。そのフィードバックに基づき、最適化部４０は、損失ベクトルｌｔの推定量ｌ＾ｔを、上記に示す式２２により算出する（ステップＳ１１４）。そして、最適化部４０は、Ｋｔ＋１（０）←Ｋｔ（ｓｔ）に更新する（ステップＳ１１５）。
【０１３６】
次に、本実施形態の最適化装置２００を用いた場合の後悔（Ｒｅｇｒｅｔ）について、分析結果を具体的に説明する。具体的には、上記アルゴリズムによる後悔上限を以下に示す。まず、ψを以下に示す式２７のように定義する。
【０１３７】
【数２５】
2020235049.tif 000027
【０１３８】
ここで、以下の式２８に示すパラメータεおよびηで図４に例示する処理によってａｔが与えられたとする。
【０１３９】
【数２６】
2020235049.tif 000028
【０１４０】
このとき、全てのａ＊∈Ａについて、以下の式２９に示す期待値が得られる。
【０１４１】
【数２７】
2020235049.tif 000029
【０１４２】
式２９において、ＳＴは、ｔ＝１からＴまでのＫｔ（ｊ）の更新数を表わす。なお、上述するψは、Ｋが半径ｒ＞ ０の球ｌ２を含む場合に、ψ≦ｌｏｇ（Ｒ／ｒ）を満たす。
【０１４３】
次に、オラクル複雑度についての分析を説明する。具体的には、図４に例示する処理で線形最適化オラクルの呼び出しがＯ（Ｔｐｏｌｙ（ｄ））のオーダであることを示す。
【０１４４】
図４に例示する処理を実装するためには、線形最適化オラクルは、ステップＳ１０４およびステップＳ１１１のみで必要とされる。ステップＳ１０４では、ｘがＫの要素でないようなｘ∈εｔ（ｊ）が存在するかどうか決定するために分離問題（ＳＰ）が必要である。上記の式２１に示すεｔ（ｊ）の定義から、εｔ（ｊ）における要素の数は、各ｔおよびｊについて２ｄに等しいため、分離問題を解決すべきトータルの数は、以下に示す式３０で算出される。
【０１４５】
【数２８】
2020235049.tif 000030
【０１４６】
ＳＴの数は、オーダＯ（Ｔ）で制限できる。その結果、分離問題（ＳＰ）を解決すべきトータルの数のオーダは、Ｏ（ｄＴ）である。
【０１４７】
また、ステップＳ１１１では、各ラウンドｔにおいて分割問題（ＤＰ）を解く。そのため、分割問題（ＤＰ）を解決すべきトータルの数は、Ｔに等しい。線形最適化オラクルを、ｐｏｌｙ（Ｔ）呼び出すことによって、分離問題（ＳＰ）および分割問題（ＤＰ）を解決できるため、線形最適化オラクルを、Ｏ（Ｔｐｏｌｙ）のオーダで呼び出すことで図４に例示する処理を実装できる。
【０１４８】
以上のように、本実施形態では、初期化部３０が、行動集合Ａを含むような凸集合Ｋを設定し、最適化部４０が、任意のベクトルｙと凸集合とを分離する超平面ｗを導出するための分離問題（ＳＰ）を解決し、導出された超平面ｗに基づいて凸集合をより小さな凸集合に更新する。また、最適化部４０は、行動ベクトルの次元数内の値ｉｔ∈［ｄ］および正負の値を示すパラメータσｔ∈｛−１，１｝を選択し、選択されたｉｔおよびσｔにより決定される要素ｘ（＝μ＾ｔ＋（σｔ／４ｅ）ｂｔｉｔ）および凸集合Ｋに関して、その要素ｘのそれぞれを行動ベクトルの次元数のポイントに分解する分解問題（ＤＰ）を解決する。そして、最適化部４０が、分解されたポイントの重みの確率λで、そのポイントを行動ａとして実行し、実行された行動により得られる損失に基づいて、損失ベクトルの推定量を算出する。よって、効率的に解けるようにバンディット問題を最適化できる。
【０１４９】
また、本実施形態では、最適化部４０は、線形最適化オラクル（分離問題を解決するオラクル）を実行する装置（図示せず）に対してベクトルｙおよび凸集合を送信する制御を行い、その装置から超平面ｗを取得することにより分離問題を解決する。よって、線形最適化オラクルを実行する装置に対する呼び出し回数を抑制して計算時間を抑制できるため、バンディット問題を解決するコンピュータの機能を改善できる。言い換えると、本実施形態の最適化装置は、装置としてのオラクルに行う指示を適切に制御する装置であるともいえる。
【０１５０】
次に、本発明の概要を説明する。図５は、本発明による最適化装置の概要を示すブロック図である。本発明による最適化装置８０は、バンディット問題を最適化する最適化装置（例えば、最適化装置１００）であって、候補になる行動ベクトルの集合である行動集合（例えば、Ａ）の凸包を設定する凸包設定部８１（例えば、初期化部１０）と、凸包に含まれる行動ベクトルの次元数（例えば、ｄ）の要素をその凸包の重心スパナ（例えば、２−重心スパナ）とする重心スパナ設定部８２（例えば、最適化部２０）と、上記要素および凸包に関して、その要素のそれぞれを次元数のポイント（例えば、｛ｘｋｉ０，…，ｘｋｉｄ｝∈Ａ）に分解するための分解問題（例えば、ＤＰ）を解決する分解問題解決部８３（例えば、最適化部２０）と、試行回数を示すラウンド（例えば、ｔ）をｌｏｇオーダのフェーズ（例えば、Θ（２ｋ））に分割し、フェーズに分割されたラウンドの数のポイントを行動として選択する行動選択部８４（例えば、最適化部２０）と、選択された行動に基づいて、損失ベクトルの経験的推定量（例えば、ｌ＾ｋ）を算出する経験的推定量算出部８５（例えば、最適化部２０）と、経験的推定量および凸包に関して、上記要素およびその経験的推定量により算出される損失を最小化するための線形最適化問題（例えば、ＬＰ）を解決する線形最適化問題解決部８６（最適化部２０）と、線形最適化問題の解決により得られた最適化要素（例えば、ｘ＊ｋ）に基づいて、凸包を小さくするよう（例えば、上記式１５に示すように）に更新する凸包更新部８７（例えば、最適化部２０）とを備えている。
【０１５１】
そのような構成により、効率的に解けるようにバンディット問題を最適化できる。
【０１５２】
また、行動選択部８４は、ポイントの重みに応じて選択する行動の回数を（例えば、上記式１１に基づいて）決定し、決定された回数に基づいて、分解されたポイントを行動として選択してもよい。
【０１５３】
また、凸包更新部８７は、フェーズごとに凸包の更新を行い、行動選択部８４は、順次実行されるフェーズに含まれるラウンドが２の階乗のオーダで増加するように、フェーズに含まれるラウンド数を決定してもよい。
【０１５４】
また、凸包更新部８７は、損失の値が行動ベクトルのノルムの上界（例えば、Ｌ）および損失ベクトルのノルムの上界（例えば、Ｒ）に基づいて決定される範囲内（例えば、ＬＲ２−ｋ）になるように凸包を更新してもよい。
【０１５５】
また、線形最適化問題解決部８６は、線形最適化オラクル（例えば、ＬＰ、ＳＰ、ＲＰを解決するオラクル）を実行する装置に対して算出された経験的推定量を送信する制御を行い、その装置から最適化要素を取得することにより線形最適化問題を解決してもよい。そのような構成によれば、線形最適化オラクルを実行する装置に対する呼び出し回数を抑制して計算時間を抑制できるため、バンディット問題を解決するコンピュータの機能を改善できる。
【０１５６】
図５は、少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。コンピュータ１０００は、プロセッサ１００１、主記憶装置１００２、補助記憶装置１００３、インタフェース１００４を備える。
【０１５７】
上述の最適化装置８０は、コンピュータ１０００に実装される。そして、上述した各処理部の動作は、プログラム（最適化プログラム）の形式で補助記憶装置１００３に記憶されている。プロセッサ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、当該プログラムに従って上記処理を実行する。
【０１５８】
なお、少なくとも１つの実施形態において、補助記憶装置１００３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例としては、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ（Compact Disc Read-only memory ）、ＤＶＤ−ＲＯＭ（Read-only memory）、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００が当該プログラムを主記憶装置１００２に展開し、上記処理を実行してもよい。
【０１５９】
また、当該プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、当該プログラムは、前述した機能を補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで実現するもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【０１６０】
１０，３０  初期化部
２０，４０  最適化部
１００，２００  最適化装置
【図１】
2020235049.tif 000031
【図２】
2020235049.tif 000032
【図３】
2020235049.tif 000033
【図４】
2020235049.tif 000034
【図５】
2020235049.tif 000035
【図６】
2020235049.tif 000036
【国際調査報告】
2020235049.tif 000037
2020235049.tif 000038