#### 論文の概要、ライセンス

 # (参考訳) 制約下でのサブセット選択のためのマルチアーム帯域幅アプローチ [全文訳有] A Multi-Arm Bandit Approach To Subset Selection Under Constraints ( http://arxiv.org/abs/2102.04824v1 ) ライセンス: CC BY 4.0 Ayush Deva, Kumar Abhishek, Sujit Gujar (参考訳) 中央プランナーがエージェントのサブセットを選択する必要がある問題の種類を,それぞれ異なる品質とコストで検討する。 プランナーは、選択したエージェントの平均品質が一定のしきい値を超えていることを保証しながら、そのユーティリティを最大化したいです。 エージェントの品質が分かっているとき、我々はこの問題を整数線形プログラム(ilp)として定式化し、決定論的アルゴリズム、すなわち我々のilpの厳密な解を提供する \dpss\ を提案する。 次に,エージェントの質が不明な場合の設定について考察する。 我々はこれをマルチアームバンドイット(MAB)問題としてモデル化し、複数ラウンドで品質を学習するために「newalgo\」を提案する。 一定の回数のラウンドの後、$\tau$, \newalgo\ は平均品質制約を満たすエージェントのサブセットを高い確率で出力することを示した。 次に、$\tau$ の境界を提供し、$\tau$ ラウンドの後、アルゴリズムは $O(\ln T)$ の後悔を招き、$T$ がラウンド総数であることを証明します。 さらに、シミュレーションを通じて \newalgo\ の有効性を示す。 計算上の制限を克服するために、我々は多項式時間勾配アルゴリズムである \greedy を提案し、このアルゴリズムは ILP に近似解を提供する。 また、実験を通じて \dpss\ と \greedy\ のパフォーマンスを比較する。 We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents' quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely \dpss\ that provides an exact solution to our ILP. We then consider the setting when the qualities of the agents are unknown. We model this as a Multi-Arm Bandit (MAB) problem and propose \newalgo\ to learn the qualities over multiple rounds. We show that after a certain number of rounds, $\tau$, \newalgo\ outputs a subset of agents that satisfy the average quality constraint with a high probability. Next, we provide bounds on $\tau$ and prove that after $\tau$ rounds, the algorithm incurs a regret of $O(\ln T)$, where $T$ is the total number of rounds. We further illustrate the efficacy of \newalgo\ through simulations. To overcome the computational limitations of \dpss, we propose a polynomial-time greedy algorithm, namely \greedy, that provides an approximate solution to our ILP. We also compare the performance of \dpss\ and \greedy\ through experiments. 公開日: Tue, 9 Feb 2021 13:48:57 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

#### 翻訳結果

Page: /

A Multi-Arm Bandit Approach To Subset Selection Under Constraints 制約下でのサブセット選択のためのマルチアーム帯域幅アプローチ 0.66
Ayush Deva Ayush Devá 0.69
Sujit Gujar Sujit Gujar (複数形 Sujit Gujars) 0.33
ayushdeva97@gmail.co m ayushdeva97@gmail.co m 0.67
kumar.abhishek@resea rch.iiit.ac.in kumar.abhishek@resea rch.iiit.ac.in 0.39
sujit.gujar@iiit.ac. in sujit.gujar@iiit.ac. in 0.47
1 2 0 2 b e F 9 1 2 0 2 b e F 9 0.85
] G L . ] G L。 0.79
s c [ 1 v 4 2 8 4 0 sc [ 1 v 4 2 8 4 0 0.68
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
Abstract We explore the class of problems where a central planner needs to select a subset of agents, each with diﬀerent quality and cost. 概要 中央プランナーがエージェントのサブセットを選択する必要がある問題の種類を,それぞれ異なる品質とコストで検討する。 0.57
The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. プランナーは、選択したエージェントの平均品質が一定のしきい値を超えていることを保証しながら、そのユーティリティを最大化したいです。 0.64
When the agents’ quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely DPSS that provides an exact solution to our ILP. エージェントの品質がわかっているとき、私たちは問題を整数線形プログラム(ILP)として定式化し、決定論的なアルゴリズム、すなわちIPLに正確なソリューションを提供するDPSSを提案します。 0.79
We then consider the setting when the qualities of the agents are unknown. 次に,エージェントの質が不明な場合の設定について考察する。 0.65
We model this as a Multi-Arm Bandit (MAB) problem and propose DPSS-UCB to learn the qualities over multiple rounds. 我々はこれをマルチアーム・バンドイット(MAB)問題としてモデル化し、DPSS-UCBを提案する。 0.70
We show that after a certain number of rounds, τ , DPSS-UCB outputs a subset of agents that satisfy the average quality constraint with a high probability. DPSS-UCBは,一定回数のラウンドの後に,平均品質制約を満たすエージェントのサブセットを高い確率で出力することを示した。 0.72
Next, we provide bounds on τ and prove that after τ rounds, the algorithm incurs a regret of O(ln T ), where T is the total number of rounds. 次に、τ 上の有界性を提供し、τ ラウンドの後にアルゴリズムが O(ln T ) を後悔させることを示す。

0.75
We further illustrate the eﬃcacy of DPSS-UCB through simulations. さらにシミュレーションによるDPSS-UCBの有効性について述べる。 0.62
To overcome the computational limitations of DPSS, we propose a polynomial-time greedy algorithm, namely GSS, that provides an approximate solution to our ILP. DPSSの計算上の限界を克服するために,IPLに近似解を提供する多項式時間勾配アルゴリズム GSS を提案する。 0.75
We also compare the performance of DPSS and GSS through experiments. また実験によりDPSSとGSSの性能を比較します。 0.77
1 Introduction Almost all countries have cooperative societies that cater to developing sectors such as agriculture and handicrafts. はじめに ほとんど全ての国は農業や手工業といった発展途上国に対応する協同組合を持っている。 0.60
We observed that some cooperatives, especially those that are consumer-oriented, such as Coop (Switzerland) or artisan cooperatives who operate their stores, lack a welldeﬁned system to procure products from its many members (manufacturers, artisans, or farmers). 我々は,一部の協同組合,特にcoop (switzerland) やartisan cooperatives (artisan cooperatives who their stores) のような消費者指向の組合は,多くの組合員(製造業者,職人,農家)から商品を調達するための明確な制度を欠いていることを見出した。 0.67
Since the production is highly decentralized and usually not standardized, each producer has a diﬀerent quality and cost of produce depending on various factors such as workmanship and the scale at which it operates. 生産は高度に分散しており、通常標準化されていないため、各生産者は、労働力や運用規模などの様々な要因によって異なる品質とコストを持つ。 0.79
The central planner (say, the cooperative manager) has to carefully trade-oﬀ between each producer’s qualities and cost to decide the quantity to procure from each producer so that it is most beneﬁcial for the society as a whole. 中央計画立案者(例えば共同経営者)は、各生産者から調達する量を決定するために、各生産者の品質とコストを慎重にトレードオフしなければならず、社会全体にとって最も有益である。 0.81
This problem is not limited to cooperatives, but it is also faced in other familiar marketplaces. この問題は協同組合に限らず、他の見慣れた市場でも直面している。 0.64
E-commerce platforms, like Amazon and Alibaba, have several sellers registered on their platform. AmazonやAlibabaのようなeコマースプラットフォームは、そのプラットフォームに複数の売り手を登録している。 0.60
For each product, the platform needs to select a subset of sellers to display on its 各製品について、プラットフォームは販売者のサブセットを選択する必要がある。

0.82
page while ensuring that it avoids low-quality sellers and does not display only the searched product’s high-cost variants. 品質の低い売り手を避けると同時に、検索した製品の高コスト版のみを表示することはない。 0.68
Similarly, a supermarket chain may need to decide the number of apples to procure from the regional apple farmers, each with a diﬀerent quality of produce, to maximize proﬁts while ensuring that the quality standards are met. 同様に、スーパーマーケットチェーンは、品質基準が満たされていることを保証しながら利益を最大化するために、地域のリンゴ農家から調達するリンゴの数を決定する必要があるかもしれない。 0.65
We formulate this as a subset selection problem where a central planner needs to select a subset of these sellers/producers, whom we refer to as agents. 私たちは、中央プランナーがこれらの売り手/プロデューサーのサブセットを選択する必要があるサブセット選択問題としてこれを定式化します。 0.70
In this paper, we associate each agent with its quality and cost of production. この論文では、各エージェントをその品質と生産コストと関連付けます。 0.81
The agent’s quality refers to the average quality of the units produced by it; however, the quality of an individual unit of its product could be stochastic, especially in artistic and farm products. エージェントの品質は、その製品が生産するユニットの平均品質を指すが、製品の個々のユニットの品質は、特に芸術製品や農場製品において、確率的である可能性がある。 0.80
Thus, it becomes diﬃcult to design an algorithm that guarantees constraint satisfaction on the realized qualities of the individual units procured. これにより、個々のユニットの実現された品質に対する制約満足度を保証するアルゴリズムの設計が困難になる。 0.80
Towards this, we show that we achieve probably approximately correct (PAC) results by satisfying our constraint on the expected average quality of the units procured. これに対して、調達するユニットの平均品質に対する制約を満たすことにより、ほぼ正しい(PAC)結果を達成することが示されています。 0.69
Every unit procured from these agents generates revenue that is a function of its quality. これらのエージェントから調達されるすべてのユニットは、その品質の機能である収益を生み出す。 0.68
The planner aims to maximize its utility (i.e., revenue - cost) while ensuring that the procured units’ average quality is above a certain threshold to guarantee customer satisfaction and retention [1, 29]. 計画者は、調達されたユニットの平均品質が顧客満足度と保持を保証するために一定のしきい値を超えることを保証しながら、その有用性(すなわち収益 - コスト)を最大化することを目指しています[1, 29]。 0.64
When the agents’ quality is known, we model our problem as an Integer Linear Program (ILP) and propose a novel algorithm, DPSS that provides an exact solution to our ILP. エージェントの品質がわかっているとき、私たちは問題を整数線形プログラム(ILP)としてモデル化し、IPLに正確なソリューションを提供する新しいアルゴリズムDPSSを提案します。 0.85
Often, the quality of the agents is unknown to the planner beforehand. 多くの場合、エージェントの品質は、プランナーが事前に知らない。 0.69
An E-commerce platform may not know its sellers’ quality at the time of registration, and an artisan’s quality of work may be hard to estimate until its products are procured and sold in the market. eコマースプラットフォームは、登録時に販売者の品質を知らないかもしれないし、artisanの作業品質は、製品が市場で調達され販売されるまで見積もるのは難しいかもしれない。 0.70
Thus, the planner needs to carefully learn the qualities by procuring units from the agents across multiple rounds while minimizing its utility loss. したがって、プランナーは複数のラウンドにまたがってエージェントからユニットを入手し、実用的損失を最小限に抑えることで、その品質を注意深く学ぶ必要がある。 0.54
Towards this, we model our setting as a Multi-Arm Bandit (MAB) problem, where each agent represents an independent arm with an unknown parameter (here, quality). これに向けて,我々は,各エージェントが未知のパラメータ(以下,品質)を持つ独立アームを表すマルチアームバンディット(mab)問題として設定をモデル化する。 0.83
To model our subset selection problem, we consider the variant of the classical MAB setting where we may select more than one agent in a single round. 部分集合選択問題をモデル化するために、我々は1つのラウンドで複数のエージェントを選択することができる古典的なmab設定の変種を考える。 0.72
This setting is popularly referred to as a Combinatorial MAB (CMAB) problem [12, 17, 24]. この設定は、一般に a Combinatorial MAB (CMAB) problem [12, 17, 24] と呼ばれる。 0.83
In studying CMAB, we consider the semi-bandit feedback model where the algorithm observes the quality realizations corresponding to each of the selected arms and the overall utility for selecting the subset of arms. CMABの研究において,選択したアームのそれぞれに対応する品質実現をアルゴリズムが観測する半帯域フィードバックモデルと,アームのサブセットを選択するための全体的な有用性について考察する。 0.71
The problem becomes more interesting when we also need to ensure our quality constraint in a CMAB problem. CMAB問題における品質制約を確実にする必要がある場合、問題はより興味深いものになります。 0.65
We position 1 位置を 1 0.73

our work with respect to the existing literature in Section 2. 第2節の既存の文学に関する私たちの仕事。 0.71
Typically, in a CMAB problem, the planner’s goal is to minimize the expected regret, i.e., the diﬀerence between the expected cumulative utility of the best oﬄine algorithm with known distributions of an agent’s quality and the expected cumulative reward of the algorithm. 典型的には、cmab問題において、プランナーの目標は、期待される後悔、すなわち、エージェントの品質の既知の分布を持つ最高のオフラインアルゴリズムの期待累積効能と、アルゴリズムの期待累積報酬との差を最小化することである。 0.74
However, the traditional deﬁnition of regret is not suitable in our setting as an optimal subset of agents (in terms of utility) may violate the quality constraint. しかし、(実用性の観点から)エージェントの最適部分集合としての設定では、後悔の定義は、品質制約に反する可能性がある。 0.60
Thus, we modify the regret deﬁnition to make it compatible with our setting. したがって、後悔の定義を変更して、設定と互換性を持たせる。 0.63
We propose a novel, UCB-inspired algorithm, DPSS-UCB, that addresses the subset selection problem when the agents’ quality is unknown. エージェントの品質が不明な場合のサブセット選択問題に対処する,UBBに基づく新しいアルゴリズムであるDPSS-UCBを提案する。 0.79
We show that after a certain threshold number of rounds, τ , the algorithm satisﬁes the quality constraint with a high probability for every subsequent round, and under the revised regret definition, it incurs a regret of O(ln T ), where T is the total number of rounds. 我々は、あるしきい値のラウンド数 τ の後、アルゴリズムは、続くラウンド毎に高い確率で品質制約を満たすことを示し、改訂された後悔定義の下では、t がラウンドの総数である o(ln t ) の後悔をもたらす。 0.71
To address the computational challenges of DPSS which has a time complexity of O(2n), we propose a greedy-based algorithm, GSS that runs in polynomial time O(n ln n), where n is the number of agents. O(2n) の時間複雑性を持つ DPSS の計算上の課題に対処するため,n がエージェント数である多項式時間 O(n lnn) で実行される greedy-based algorithm GSS を提案する。 0.84
We show that while the approximation ratio of the utility achieved by GSS to that of DPSS can be arbitrarily small in the worst case, it achieves almost the same utility as DPSS in practice, which makes GSS a practical alternative to DPSS especially when n is large. 本研究では, GSS と DPSS の近似比は, 最悪の場合には任意に小さいが, 実際には DPSS とほぼ同じ実用性を実現し, 特に n が大きい場合には GSS を DPSS の実用的な代替として用いることを示した。 0.89
In summary, our contributions are: • We propose a framework, SS-UCB, to model subset selection problem under constraints when the properties (here, qualities) of the agents are unknown to the central planner. 要約すると、 • エージェントのプロパティ(ここでは品質)が中央プランナーに知られていない場合に制約の下でサブセット選択問題をモデル化するフレームワークss-ucbを提案します。 0.76
In our setting, both the objective function and the constraint depends on the unknown parameter. 我々の設定では、目的関数と制約の両方が未知のパラメータに依存する。 0.76
• We ﬁrst formulate our problem as an ILP assuming the agents’ quality to be known and propose a novel, deterministic algorithm, namely DPSS(Algorithm 1) to solve the ILP. •我々はまず,エージェントの品質が分かっていると仮定してこの問題を ilp として定式化し,新しい決定論的アルゴリズム,すなわち dpss(algorithm 1) を提案する。 0.85
• Using DPSS, we design DPSS-UCB which addresses the setting where the agents’ quality is unknown. •DPSSを用いて,エージェントの品質が不明な設定に対処するDPSS-UCBを設計する。 0.79
We prove that after a certain number of rounds, τ = O(ln T ), DPSS-UCB satisﬁes quality constraint with high probability. DPSS-UCB は一定回数のラウンドで τ = O(ln T ) を満たすと、高い確率で品質制約を満たすことが証明される。 0.69
We also prove that it achieves a regret of O(ln T ) (Theorem 2). また、それが O(ln T ) (Theorem 2) の後悔を達成することも証明する。 0.74
• To address the computational limitation of DPSS, we propose an alternative greedy approach, GSS and GSS-UCB, that solves the known and the unknown settings, respectively. DPSSの計算限界に対処するため, 既知設定と未知設定をそれぞれ解決する, GSS と GSS-UCB の2つの手法を提案する。 0.70
We show that while the greedy approach may not be optimal, it performs well in practice with a huge computational gain that allows our framework to scale to settings with a large number of agents. 欲望のアプローチは最適ではないかもしれないが、我々のフレームワークが多数のエージェントで設定にスケールできる巨大な計算利得で実際にうまく機能することを示している。 0.71
The remaining of the paper is organized as follows: In Section 2, we discuss the related works. 論文の残りは以下のとおりである:第2節では、関連する作品について議論する。 0.68
In Section 3, we deﬁne our model and solve for the setting when the quality of the agents are known. セクション3では、モデルを定義し、エージェントの品質がわかっているときに設定を解決します。 0.71
In Section 4, we address the problem when the quality of the agents is unknown. 第4節では,エージェントの品質が不明な場合に対処する。 0.59
In Section 5, we propose a greedy approach to our problem. 内 第5節 我々はこの問題に対する欲深いアプローチを提案する。 0.65
In Section 6, we discuss our simulation-based analysis and conclude the paper in Section 7. 第6節では,シミュレーションに基づく解析を議論し,第7節で結論づける。 0.77
2 Related Work Subset selection is a well-studied class of problems that ﬁnds its applications in many ﬁelds, for example, in retail, vehicle routing, and network theory. 2 関連作業 部分集合の選択はよく研究された問題のクラスであり、小売業、車両ルーティング、ネットワーク理論など多くの分野で応用されている。 0.79
Usually, these problems are modeled as knapsack problems where a central planner needs to select a subset of agents that maximizes its utility under budgetary constraints . 通常、これらの問題はknapsack問題としてモデル化され、中央プランナーは予算制約の下でその効用を最大化するエージェントのサブセットを選択する必要がある。 0.63
There are several variations to the knapsack, such as robustness , dynamic knapsacks , and knapsack with multiple constraints  studied in the literature. ナプサックには、堅牢性、動的ナプサック、および文学で研究された複数の制約を持つナプサックなど、いくつかのバリエーションがあります。

0.76
In this paper, we consider a variant where the constraint is not additive, i.e., adding another agent to a subset doesn’t always increase the average quality. 本稿では,制約が加法的でない変種を考える。つまり,サブセットに別のエージェントを追加することで,平均品質が常に向上するとは限らない。 0.82
When online learning is involved, the stochastic multiarmed bandit (MAB) problem captures the exploration vs. exploitation trade-oﬀ eﬀectively [19, 23, 21, 22, 28, 32, 31, 6]. オンライン学習に関わる場合、確率的マルチアームバンディット(MAB)問題は、探索と搾取のトレードオフを効果的に捉える[19, 23, 21, 22, 22, 28, 32, 31, 6]。 0.71
The classical MAB problem involves learning the optimal agent from a set of agents with a ﬁxed but unknown reward distribution [7, 28, 3, 30]. 古典的MAB問題は、固定だが未知の報酬分布[7, 28, 3, 30]を持つエージェントの集合から最適なエージェントを学ぶことである。 0.75
Combinatorial MAB (CMAB) [10, 16, 8, 13, 9] is an extension to the classical MAB problem where multiple agents can be selected in any round. 組合せ mab (cmab) [10, 16, 8, 13, 9] は、任意のラウンドにおいて複数のエージェントを選択できる古典的な mab 問題の延長である。 0.77
In [10, 17, 11], the authors have considered a CMAB setting where they assume the availability of a feasible set of subsets to select from. 著者らは[10, 17, 11]において、選択可能なサブセットセットが利用可能であることを前提としたCMABの設定を検討してきた。 0.72
The key diﬀerence with our setting is that our constraint itself depends on the unknown parameter (quality) that we are learning through MAB. 私たちの設定との大きな違いは、制約自体がMABを通じて学習している未知のパラメータ(品質)に依存していることです。 0.71
Thus, the feasible subsets that satisfy the constraint need to be learned, unlike the previous works. したがって、制約を満たす実現可能な部分集合は、以前の作品とは異なり、学ぶ必要がある。 0.58
[10, 17, 11] also assumes the availability of an oracle that outputs an optimal subset given the estimates of the parameter as input, whereas we design such an oracle for our problem. また、[10, 17, 11] は、パラメータを入力として見積もって最適なサブセットを出力する oracle の可用性を前提としています。

0.74
Bandits with Knapsacks (BwK) is another interesting extension that introduces constraints in the standard bandit setting [4, 5, 2, 22] and ﬁnds its applications in dynamic pricing, crowdsourcing, etc. Bandits with Knapsacks (BwK) もまた興味深い拡張で、標準の Bandit 設定 [4, 5, 2, 22] に制約を導入し、動的価格設定やクラウドソーシングなどにその応用を見出している。 0.78
(see [4, 2]). ([4, 2]参照)。 0.74
Typically, in BwK, the objective is to learn the optimal agent(s) under a budgetary constraint (e.g., a limited number of selections) that depends solely on the agents’ cost. 典型的には、BwK の目的は、予算的制約(例えば、限られた数の選択)の下で最適なエージェントを学習することであり、エージェントのコストにのみ依存する。 0.76
However, we consider a setting where the selected subset needs to satisfy a quality constraint that depends on the learned quantities. しかし、選択されたサブセットが学習した量に依存する品質制約を満たす必要がある設定を検討します。 0.76
The closest work to ours is  where the authors present an assured accuracy bandit (AAB) framework where the objective is to minimize cost while ensuring a target accuracy level in each round. 我々の最も近い研究は  で、著者は各ラウンドの目標精度レベルを確保しつつコストを最小化することを目的として、aab(assured accuracy bandit)フレームワークを提示します。 0.76
While they do consider a constraint setting similar to ours, the objective function in  depends only on the agents’ cost and not on the qualities of the agents that are unknown. 彼らは我々のものと同じような制約設定を検討しているが、の目的関数はエージェントのコストにのみ依存し、未知のエージェントの品質に依存しない。 0.77
Hence, it makes our setting diﬀerent and more generalizable with respect to both AAB and CMAB as in our setting, both the constraint and the utility function depend on the unknown parameter. したがって,AAB と CMAB の両方に関して,制約関数とユーティリティ関数の両方が未知のパラメータに依存しているため,設定を異なるものにし,より一般化することができる。 0.74
2 2 0.85

3 Subset Selection With Known 既知の3つのサブセット選択 0.77
3.2 Ensuring Quality Constraints 3.2 品質制約の確保 0.66
Qualities of Agents Here we assume that the agents’ quality is known and consider the problem where a central planner C needs to procure multiple units of a particular product from a ﬁxed set of agents. エージェントの質 ここで、エージェントの品質が知られていると仮定し、中央プランナーCが特定の製品の複数のユニットを固定されたエージェントから調達する必要がある問題を考える。 0.77
Each agent is associated with the quality and cost of production. 各エージェントは、生産の品質とコストに関連がある。 0.81
C’s objective is to procure the units from the agents such that the average quality of all the units procured meets a certain threshold. cの目標は、調達したすべてのユニットの平均品質が一定のしきい値を満たすように、エージェントからユニットを取得することである。 0.74
We assume that there is no upper limit to the number of units it can procure as long as the quality threshold is met. 品質のしきい値を満たしている限り、調達できるユニット数に上限がないと仮定します。 0.62
In Section 3.1, we deﬁne the notations required to describe our model, formulate it as an integer linear program (ILP) in Section 3.3, and propose a solution to it in Section 3.4. 第3.1節では、モデルを記述するのに必要な表記法を定義し、第3.3節では整数線型プログラム(ILP)として定式化し、第3.4節ではそれに対する解を提案する。 0.61
3.1 Model and Notations 1. 3.1 Model and Notations 1 0.91
There is a ﬁxed set of agents N = {1, 2, . エージェント N = {1, 2, の固定集合が存在する。 0.70
. . , n} avail- . . , n} avail- 0.89
able for selection for procurement by planner C. プランナーCによる調達の選択が可能である。 0.67
2. Agent i has a cost of production, ci, and capacity, ki 2. エージェント i の生産コスト、ci、および容量、ki があります。 0.81
(maximum number of units it can produce). (生産できるユニットの最大数)。 0.62
3. The quality of the jth unit of produce by agent i is denoted by Qij, which we model as a Bernoulli random variable. 3. エージェント i による生成の j 番目の単位の質は Qij で表され、ベルヌーイ確率変数としてモデル化される。 0.78
4. For any agent i, the probability that Qij is 1 is deﬁned by qi, i.e., E[Qij] = qi for any unit j procured from agent i. qi is also referred to as the quality of the agent in the rest of the paper. 4. 任意のエージェント i に対して、qij が 1 である確率は qi によって定義され、すなわち e[qij] = qi はエージェント i から得られる任意の単位 j に対して定義される。

0.85
5. The utility for C to procure a single unit of produce from agent i is denoted by ri, which is equal to its expected revenue1 minus the cost of production, i.e., ri = Rqi−ci, where R is the proportionality constant. 5. C がエージェント i から生産の単元を調達するための実用性は ri によって表されるが、これは期待される収益に等しい。1 は生産コスト、すなわち R が比例定数である ri = Rqi−ci を最小にする。 0.83
6. The quantity of products procured by C from the ith 6. からCで調達した製品の数量です。 0.78
agent is given by xi. エージェントはxiから与えられる。 0.77
7. The average quality of products procured by C is 7. Cで調達した製品の平均品質は 0.86
therefore equal to したがって、同じです 0.50
8. We deﬁne qav = 8. qav = を定義する。 0.77
(cid:80)xi (cid:80)xi 0.84
j=1 Qij . i∈N xi j=1 Qij . i∈N xi 0.75
(cid:80) i∈N (cid:80) i∈N 0.69
(cid:80) (cid:80) (cid:80) (cid:80)(cid:80) 0.88
i∈N xiqi i∈N xi i∈N xiqi i∈N xi 0.65
average quality of the units procured by C. Cが調達した単位の平均品質。 0.77
, which is the expected 9. 予想通りです。 9. 0.60
C needs to ensure that the average quality of all the units procured is above a certain threshold, α ∈ [0, 1]. C は、得られたすべての単位の平均品質が、あるしきい値 α ∈ [0, 1] を超えることを保証する必要がある。

0.84
10. The total utility of C is given by, z =(cid:80) 10. C の総実効性は z =(cid:80) で与えられる。 0.80
i∈N xiri. Usually, an individual unit’s quality Qij may not be quantiﬁable and can only be characterized by observing whether it was sold. i∈N xiri。 通常、個々のユニットの品質Qijは定量化されておらず、それが販売されたかどうかを観察することでのみ特徴付けられる。

0.74
Hence, we model it as a Bernoulli random variable. したがって、ベルヌーリのランダム変数としてモデル化します。 0.67
In our setting, average quality (Section 3.1, point 7) is dependent on Qij, which is stochastic in nature. 我々の設定では、平均品質 (Section 3.1, point 7) は本質的に確率的な Qij に依存する。 0.77
In such a stochastic framework, it is more natural to work with expected terms than on a sequence of realized values. このような確率的枠組みでは、実現された値のシーケンスよりも、期待される条件で作業することがより自然である。

0.66
Towards this, we show that by ensuring our quality constraint on expected average quality, qav, instead, we can still achieve approximate constraint satisfaction with a high probability. そこで本研究では,期待される平均品質,qavに対する品質制約を確実にすることで,高い確率で近似的制約満足度を達成できることを示す。 0.78
Formally, we present the following lemma, 正式には、以下の補題を提示する。 0.50
Lemma 1. The probability that average quality is less than α−  given that qav ≥ α, can be bounded as follows: レマ1。 qav ≥ α の場合、平均品質が α− > より小さい確率は、次のように有界である。 0.67
(cid:33) j=1 Qij (cid:33) j=1 Qij 0.75
< α −  | qav ≥ α < α −  | qav ≥ α 0.85
≤ exp (−22m)), ≤exp(−2～2m)) 0.76
P i∈N (cid:32) (cid:80) (cid:80)xi (cid:80) where m =(cid:80) (cid:80) P i∈N (cid:32) (cid:80) (cid:80)xi (cid:80) ここで m =(cid:80) (cid:80) 0.73
Proof. Let, V = 証明。 V = とする。 0.71
i∈N xi E[V ] = i∈N xi E[V] = 0.77
i∈N xi, and  is a constant. i∈N xi と s は定数である。 0.79
i∈N (cid:80)xi (cid:80) (cid:80) (cid:80)xi (cid:80) i∈N (cid:80)xi(cid:80)xi (cid:80)xi(cid:80) 0.73
i∈N xi i∈N i∈N xi i∈N 0.65
j=1 Qij (cid:80) (cid:80) j=1 Qij (cid:80)(cid:80) 0.72
j=1 E[Qij] i∈N xi j=1 E[Qij] i∈N xi 0.78
= i∈N qixi i∈N xi = i∈N qixi i∈N xi 0.75
= qav Therefore, P(cid:0)V < α −  | E[V ] ≥ α(cid:1) ≤ P(cid:0)V < E[V ] − ) -qav そのため P(cid:0)V < α − > | E[V ] ≥ α(cid:1) ≤ P(cid:0)V < E[V ] − ) 0.76
= P(cid:0)V − E[V ] < −) ≤ exp(−22m) = P(cid:0)V − E[V ] < − ) ≤ exp(−2,2m) 0.88
The last line follows from the Hoeﬀding’s inequality . 最後の行は、Hoeffdingの不等式から続きます。 0.64
(cid:4) From the above lemma, we show that by ensuring qav ≥ α, we can achieve probably approximate correct (PAC) results on our constraint. (cid:4) 上記の補題から、qav ≥ α を保証することで、制約に対しておそらく近似的正解(PAC)が得られることを示す。 0.74
Hence, for the rest of the paper, we work with qav ≥ α as our quality constraint (QC). したがって、残りの論文では、品質制約(QC)としてqav ≥ αで作業する。 0.70
3.3 Integer Linear Program (ILP) 3.3 整数線形プログラム(ILP) 0.84
When the qualities of the agents are known, the planner’s subset selection problem can be formulated as an ILP where it needs to decide on the number of units, xi, to procure from each agent i so as to maximize its utility (objective function) while ensuring the quality and capacity constraints. エージェントの品質が分かっている場合、プランナーのサブセット選択問題は、各エージェントiから取得するユニットxiの数を決定する必要があるilpとして定式化でき、品質とキャパシティの制約を確保しながら、その有用性(目的機能)を最大化することができる。 0.77
The optimization problem can be described as follows: 最適化問題は次のように説明できる。 0.77
(cid:88) i∈N (cid:88) i∈N 0.69
max xi (Rqi − ci)xi マックス xi (Rqi − ci)xi 0.80
(cid:80) (cid:80) (cid:80)(cid:80) 0.73
i∈N qixi i∈N xi i∈N qixi i∈N xi 0.65
s.t. qav = s.t. qav = 0.78
qav ≥ α 0 ≤ xi ≤ ki xi ∈ Z qav ≥ α 0 ≤ xi ≤ ki xi ∈ Z 0.85
(1) ∀i ∈ N ∀i ∈ N (1) シイ ∈ N シイ ∈ N である。 0.68
3.4 Dynamic Programming Based Subset 3.4 動的プログラミングベースのサブセット 0.71
Selection (DPSS) 1We assume expected revenue to be proportional to the quality of the product. 選択(DPSS) 1 期待収益は製品の品質に比例すると仮定する。 0.75
It is a reasonable assumption as if qi is the probability of the product being sold and R is the price of the product, its expected revenue would be Rqi qi が製品が販売される確率であり、R が製品の価格であるなら、その予想収益は Rqi である、という合理的な仮定である。 0.82
In order to solve the ILP, we propose a dynamic programming based algorithm, called DPSS. ILPを解くために,DPSSと呼ばれる動的プログラミングに基づくアルゴリズムを提案する。 0.75
For ease of exposition, we consider ki = 1, i.e., each agent has a unit 公開を容易にするため、ki = 1、すなわち各エージェントが単位を持つと考える。 0.70
3 3 0.85

capacity of production. This is a reasonable assumption that doesn’t change our algorithm’s results, since, for an agent with ki > 1, we can consider each unit as a separate agent, and the proofs and discussion henceforth follows. 生産の容量。 これはアルゴリズムの結果を変えない合理的な仮定です。なぜなら、ki > 1のエージェントでは、各ユニットを別のエージェントと見なすことができ、その後の証明と議論が続くからです。 0.69
Formally, the algorithm proceeds as follows: 正式なアルゴリズムは次のとおりである。 0.73
1. Divide the agents into one of the four categories: 1. エージェントを4つのカテゴリの1つに分ける。 0.78
(a) S1: Agents with qi ≥ α and ri ≥ 0 (b) S2: Agents with qi < α and ri ≥ 0 (c) S3: Agents with qi ≥ α and ri < 0 (d) S4: Agents with qi < α and ri < 0 (a) s1: qi ≥ α と ri ≥ 0 (b) s2: qi < α と ri ≥ 0 (c) s3: qi ≥ α と ri < 0 (d) s4: qi < α と ri < 0 のエージェント 0.74
2. Let x = {xi}i∈N be the selection vector, where xi = 2. x = {xi}ihtmln を選択ベクトルとし、ここで xi = とする。 0.82
1 if the ith agent is selected and 0 otherwise. 1 ith エージェントが選択され、それ以外の場合は 0。 0.69
(cid:80) 3. (cid:80) 3. 0.82
Since an agent in S1 has a positive utility and above Let d = S1 のエージェントは正の効用を持ち、上述の d = 0.71
threshold quality, xi = 1, ∀i ∈ S1. しきい値 xi = 1, .i ∈ S1。 0.66
(qi − α) be the excess quality accumulated. (qi − α)は蓄積された過剰品質である。 0.79
i∈S1 4. Similarly, all units in S4 have a negative utility and i∈S1 4. 同様に、S4のすべての単位は負の効用を持ち、 0.67
below threshold quality. しきい値以下の品質。 0.65
Hence, xi = 0, ∀i ∈ S4. したがって、 xi = 0, si ∈ S4 である。 0.79
5. Let G be the set of the remaining agents (in S2 and S3). 5. g を(s2 と s3) の残りのエージェントの集合とする。 0.79
For each agent i ∈ G, we deﬁne di = qi − α. 各エージェント i ∈ g に対して、di = qi − α を定義する。 0.88
Thus, we need to select the agents i ∈ G that したがって、エージェント i ∈ G を選択する必要がある。 0.83
maximizes the utility, such that(cid:80) ユーティリティを最大化します(cid:80) 0.78
i∈G xidi ≤ d. i∈G xidi ≤ d。 0.84
6. For agents in G, select according to the DP function deﬁned in Algorithm 1 (Lines [8-16]). 6. g のエージェントは、アルゴリズム 1 で定義された dp 関数 (lines [8-16]) に従って選択する。 0.81
Here, dte denotes the access quality accumulated before choosing the next agent and xte refers to the selections made so far in the DP formulation ここでは、dteは次のエージェントを選択する前に蓄積されたアクセス品質を表し、xteはDP製剤でこれまでに行われた選択を指します。

0.79
5: ∀i ∈ S1, xi = 1; z = z + ri; d =(cid:80) 5: yi ∈ S1, xi = 1; z = z + ri; d =(cid:80) 0.89
Algorithm 1 DPSS 1: Inputs: N , α, R, costs c = {ci}i∈N , qualities q = {qi}i∈N 2: Output: Quantities procured x = (x1, . アルゴリズム 1 DPSS 1: 入力: N , α, R, cost c = {ci}i・N , quality q = {qi}i・N 2: Output: Quantities procured x = (x1, )。 0.89
. . , xn) 3: Initialization: ∀i ∈ N , ri = Rqi − ci, z = 0 4: Segregate S1,S2,S3,S4 as described in Section 4.1 (qi − α) 6: ∀i ∈ S4, xi = 0 7: G = S2 ∪ S3 ; ∀i ∈ G, di = qi − α 8: function dp(i, dte, xte, x(cid:63), zte, z(cid:63)) 9: . . , xn) 3: 初期化: .i ∈ N , ri = Rqi − ci, z = 0 4: Segregate S1,S2,S3,S4 as described in Section 4.1 (qi − α) 6: .i ∈ S4, xi = 07: G = S2 > S3 ; .i ∈ G, di = qi − α 8: function dp(i, dte, xte, x(cid:63), zte, z(cid:63)) 9: 0.89
if i == |G| and dte < 0 then return x(cid:63), z(cid:63) if i == |G| and dte ≥ 0 then i == |g| かつ dte < 0 ならば x(cid:63), z(cid:63) を返せば i == |g| かつ dte ≥ 0 となる。 0.76
i∈S1 10: 11: 12: i∈S1 10: 11: 12: 0.66
13: if zte > z(cid:63) then 13: zte > z(cid:63) ならば 0.87
z(cid:63) = zte; x(cid:63) = xte z(cid:63) = zte; x(cid:63) = xte 0.92
return x(cid:63), z(cid:63) return x(cid:63), z(cid:63) 0.92
x(cid:63), z(cid:63) = DP (i + 1, dte, [xte, 0], x(cid:63), zte, z(cid:63)) x(cid:63), z(cid:63) = DP (i + 1, dte + di, [xte, 1], x(cid:63), zte + ri, z(cid:63)) return x(cid:63), z(cid:63) x(cid:63), z(cid:63) = DP (i + 1, dte, [xte, 0], x(cid:63), zte, z(cid:63)) x(cid:63), z(cid:63) = DP (i + 1, dte + di, [xte, 1], x(cid:63), zte + ri, z(cid:63)) return x(cid:63), z(cid:63)) 0.99
14: 15: 16: 17: xG, zG = DP(0,d,[ ],[ ],0,0) 18: ∀i ∈ G, xi = xG 19: return x 14: 15: 16: 17: xG, zG = DP(0,d,[ ],[ ],0,0) 18: yi ∈ G, xi = xG 19: return x 0.81
i 4 Subset Selection with Unknown 私は 4 未知のサブセット選択。 0.68
Qualities of Agents In the previous section, we assumed that the qualities of the agents, qi, are known to C. We now consider a setting エージェントの質 前節では、エージェントの品質であるqiがcに知られていると仮定した。

0.64
4 when qi are unknown beforehand and can only be learned by selecting the agents. 4 qiが事前に不明で、エージェントを選択することでのみ学習できる場合。 0.79
We model it as a CMAB problem with semi-bandit feedback and QC. 半帯域フィードバックとQCを用いてCMAB問題としてモデル化する。 0.66
4.1 Additional Notations We introduce the additional notations to model our problem. 4.1 追加表記 問題をモデル化する追加の表記法を紹介します。 0.67
Similar to our previous setting, we assume that we are given a ﬁxed set of agents, N , each with its own average quality of produce, qi and cost of produce, ci. 以前の設定と同様に、我々はエージェントの固定セット、nを与えられたと仮定し、それぞれが平均生産品質、qi、生産コスト、ciを持っていると仮定します。 0.71
Additionally, our algorithm proceeds in discrete rounds t = 1, . さらに、このアルゴリズムは離散ラウンド t = 1 で進行する。 0.66
. . , T . For a round t: . . 、T。 ラウンドT: 0.70
• Let xt ∈ {0, 1}n be the selection vector at round t, i = 1 if the agent i is selected in round t and • xt ∈ {0, 1}n を円 t における選択ベクトルとし、i = 1 とする。

0.87
where xt xt i = 0 if not. ここで xt xt i = 0 である。 0.74
• The algorithm selects a subset of agents, St ⊆ N , referred to as a super-arm henceforth, where St = i = 1}. • このアルゴリズムは、エージェントのサブセットである、St = i = 1 {\displaystyle St=i=1} をスーパーアームとして選択する。 0.70
Let st be cardinality of selected {i ∈ N|xt super-arm, i.e., st = |St|. st を選択 {i ∈ N|xt スーパーアーム、すなわち st = |St| のカーディナリティとする。 0.66
• Let wt i denote the number of rounds an agent i has • wt を エージェントが持っているラウンドの数を表します 0.69
been selected until round t, i.e., wt ラウンドT、つまりWTまで 選ばれました 0.63
i =(cid:80) i =(cid:80) 0.88
y≤t xy i . • For each agent i ∈ St, the planner, C, observes its realized quality X j i ] = qi. y≤t xy i。 •各エージェント i ∈ St に対して、計画者 C は、その実現品質 X j i ] = qi を観測する。 0.77
For an agent i /∈ St, we do not observe its realized quality (semi-bandit setting). エージェント i /∈ St は、その実現した品質(セミバンド設定)を観察しません。 0.70
i , where j = wt i , ここで j = wt 0.85
i and E[X j i と E[X j] 0.92
i = 1 wt i i = 1 wt i 0.85
• The empirical mean estimate of qi at round t, • ラウンド T における qi の経験的平均推定値。 0.74
denoted by ˆqt dence bound (UCB) estimate is denoted by (ˆqt ˆqt i + qt dence bound (ucb) で表される推定値は (qt )qt i + で表される。 0.65
(cid:113) 3 ln t (cid:113) 3 ln t 0.92
is i . The upper conﬁi )+ = 俺か? 上面 confii )+ = 0.55
• Utility to C at round t is given by: • ラウンド t における c の効用は次のとおりである。 0.66
(cid:80) rq(St) = i∈St Rqi−ci, where q = {q1, q2, . (cid:80) rq(St) = i∈St Rqi−ci, ここで q = {q1, q2, 。 0.78
. . , qn} is the qual- . . , qn} は qual- である 0.86
i j=1 X j . 私は j=1xj . 0.73
2wt i (cid:80)wt 2wt i (cid:80)wt 0.86
ity vector. (cid:80) ityベクター。 (cid:80) 0.71
• The expected average quality of selected super-arm •選択されたスーパーアームの平均品質 0.77
at round t is given by: qt ラウンド t では qt が与えられます 0.70
av = 1 st i∈St qi. av = 1 st i∈St qi。 0.79
Following from Lemma 1, we continue to work with expected average quality instead of realized average quality. Lemma 1に続いて、平均品質を実現するのではなく、期待される平均品質で作業を続けます。 0.64
4.2 SS-UCB 4.2 SS-UCB 0.50
In this section, we propose an abstract framework, SSUCB, for subset selection problem with quality constraint. 本稿では,品質制約付きサブセット選択問題に対する抽象的なフレームワークであるSSUCBを提案する。 0.82
SS-UCB assumes that there exist an oﬄine subset selection algorithm, SSA, (e.g., DPSS), which takes a vector of qualities, q(cid:48), and costs, c(cid:48), along with the target quality threshold, α(cid:48), and proportionality constant, R, as an input and returns a super-arm which satisﬁes the quality constraint (QC) with respect to q(cid:48) and α(cid:48). SS-UCB は、品質のベクトル q(cid:48) とコスト c(cid:48) と目標品質のしきい値 α(cid:48) と比例定数 R を入力とし、q(cid:48) と α(cid:48) に関して品質制約 (QC) を満たすスーパーアームを返すオフラインサブセット選択アルゴリズム SSA(例:DPSS) が存在すると仮定している。 0.79
SS-UCB runs in two phases: (i) Exploration: where all the agents are explored for certain threshold number of rounds, τ ; (ii) Explore-exploit: We invoke SSA (line 10, i )+}i∈N , {ci}i∈N , α + 2 and R as Algorithm 2) with {(ˆqt the input parameters and select accordingly. SS-UCB は以下の2つのフェーズで実行される: (i) 探索: 全てのエージェントが特定のしきい値のラウンドに対して探索される τ ; (ii) 探索-探索: SSA (line 10, i )+}i・N , {ci}i・N , {ci}i・N , α + s2 および R をアルゴリズムとして呼び出す。 0.81
We invoke SSA with a slightly higher target threshold, α + 2, so that our algorithm is more conservative while selecting the ターゲット閾値がわずかに高いα+α2でSSAを起動するので、アルゴリズムは選択時により保守的である。 0.71

super-arm in order to ensure QC with a high probability (discussed in Section 4.3). 高い確率のQCを保障するために極度の腕(セクション4.3)で論議される)。 0.65
As we shall see in Section 4.3, the higher the value of 2, the sooner the SSA satisﬁes QC with a high probability but it comes with the cost of loss in utility. セクション4.3で見れば見るように、*2の価値が高いほど、SSAは高い確率でQCを満足しますが、実用性で損失の費用と来ます。 0.66
Thus, the value of 2 must be appropriately selected based on the planner’s preferences. したがって、計画者の好みに基づいて2の値を適切に選択する必要があります。 0.67
We refer to the algorithm as DPSS-UCB when we use DPSS (Algorithm 1) as SSA in the SS-UCB framework. このアルゴリズムは、 DPSS (Algorithm 1) を SS-UCB フレームワークの SSA として使用する際に DPSS-UCB と呼びます。 0.81
We show that DPSS-UCB outputs the super-arm that satisﬁes the QC with high probability (w.h.p) after a certain threshold number of rounds, τ , and incurs a regret of O(ln T ). DPSS-UCB は、ある閾値のラウンド数 τ の後に高い確率 (w.h.p) で QC を満たすスーパーアームを出力し、O(ln T ) を後悔することを示す。 0.73
22 2 i , qt 22 2 I, qt 0.75
; t = 0 Algorithm 2 SS-UCB 1: Inputs: N , α, 2, R, costs c = {ci}i∈N 2: For each agent i, maintain: wt i )+ i , (ˆqt 3: τ ← 3 ln T 4: while t ≤ τ (Explore Phase) do 5: 6: 7: 8: while t ≤ T (Explore-Exploit Phase) do 9: t = 0 です。 アルゴリズム 2 SS-UCB 1: 入力: N , α, sh2, R, cost c = {ci}i∂N 2: それぞれのエージェント i に対して、維持: wt i ) + i , (\qt 3: τ ) 3 ln T 4: while t ≤ τ (Explore Phase) do 5: 6: 7: 8: while t ≤ T (Explore-Exploit Phase) do 9: 0.92
Play a super-arm St = N Observe qualities X j t ← t + 1 スーパーアーム St = N Observe quality X j t > t + 1 を再生する 0.70
i ,∀i ∈ St and update wt (cid:113) 3 ln t i ,∀i ∈ St and update wt i ,\i ∈ St と update wt (cid:113) 3 ln t i ,\i ∈ St と update wt 0.85
i + i )+}i∈N , c, α + 2,R) i + i ) +}i∈N , c, α + ×2,R) 0.97
For each agent i, set (ˆqt St = SSA ({(ˆqt Observe qualities X j t ← t + 1 それぞれのエージェント i に対して、集合 (\qt St = SSA ({(\qt Observe quality X j t > t + 1) 0.80
i )+ = ˆqt i )+ = sqt 0.76
10: 11: 12: 10: 11: 12: 0.85
2wt i i , ˆqt i 2wt i I (複数形 Is) 0.58
i , ˆqt i I (複数形 Is) 0.27
4.3 Ensuring Quality Constraints 4.3 品質制約の確保 0.67
We provide Probably Approximate Correct (PAC) [18, 14] bounds on DPSS-UCB satisfying QC after τ rounds: Theorem 2. τラウンド後のQCを満たすDPSS-UCB上の確率近似補正(PAC) [18, 14] 境界: Theorem 2。 0.79
For τ = 3 ln T , if each agent is explored 22 2 τ number of rounds, then if we invoke DPSS with target i )+}i∈N as the input, the QC is threshold α + 2 and {(ˆqt (cid:88) approximately met with high probability. τ = 3 ln T の場合、各エージェントを 2 × 2 τ のラウンド数で探索すると、ターゲット i ) + 1 の DPSS を入力として呼び出すと、QC はしきい値 α + 2 のしきい値で、{(\qt (cid:88) は高い確率で満たされる。 0.84
(cid:32) (cid:33) (cid:32) (cid:33) 0.78
i )+ ≥ α + 2, t > τ (ˆqt i )+ ≥ α + >2, t > τ (\qt) 0.93
av < α − 1 | 1 qt st av < α − >1 | 1 qt st 0.90
P i∈St ≤ exp(−2 P i∈St ≤ exp(−) 0.77
1t). where wt min = mini wt all the agents, thus, wτ thus, we claim that wt √ 1t)。 ここで wt min = mini wt のすべてのエージェント、したがって、wt は wt であると主張します。 0.79
i. Since, for t < τ , we are exploring i ≥ wτ i , ∀t > τ , i = τ . 私は... t < τ に対して、我々は i ≥ wτ i , τ , i = τ を探索している。 0.60
Now, since wt min ≥ τ for t > τ . t > τ に対して wt min ≥ τ となる。 0.81
Hence, For τ = 3 ln T 22 2 それゆえ τ = 3 ln T 2 = 2 に対して 0.75
, we have, min 3 ln t(cid:112)2wt (cid:88) (cid:0)(ˆqt 俺達は... 分 3 ln t(cid:112)2wt(cid:88 ) 0.57
i∈St 1 st √ 3 ln T√ 2τ i∈St 1st 3 ln T です。 0.60
. ≤ (cid:1) ≤ 2. . ≤ (cid:1) ≤ ×2。 0.78
i )+ − ˆqt i )+ − sqt 0.74
i Lemma 4. ∀t > τ 私は レマ4。 t>τ 0.53
(cid:32) P (cid:32) P 0.82
av < α − 1 | 1 qt st (cid:80) av < α − 1 | 1 qt st (cid:80) 0.97
(cid:4) i ) ≥ α(cid:1)(cid:33) (cid:0)ˆqt (cid:4) i ) ≥ α(cid:1)(cid:33) (cid:0)>qt 0.79
(cid:0)(cid:88) (cid:0)(cid:88) 0.75
i∈St ≤ exp(−2 i∈St ≤ exp(−) 0.73
1t). i ] = E[X j 1t)。 i ] = E[X j] 0.89
i . Since E[ˆqt 私は... E[qt]以降 0.50
Proof. Let Y t = 1 st E[Y t] = qt 証明。 Y t = 1 st E[Y t] = qt とする。 0.76
i∈St ˆqt av. i∈Stのqt av。 0.68
Hence, we have, P(E[Y t] < α − 1) | Y t ≥ α) ≤ P(cid:0)Y t ≥ E[Y t] + 1) where wt =(cid:80) (cid:32) それゆえ 我々は P(E[Y t] < α − t1) | Y t ≥ α) ≤ P(cid:0)Y t ≥ E[Y t] + s1) ここで wt =(cid:80) (cid:32) 0.75
i, i.e., total number of agents selected till round t. Since we pull atleast one agent in each round, we can say that, wt ≥ t. Thus, ∀t > τ すなわち、ラウンドtまで選択されたエージェントの総数である。各ラウンドで1つのエージェントを引くので、wt > tと言うことができる。

0.72
≤ exp(−2 (cid:33)(cid:33) ≤ exp(−) (cid:33)(cid:33) 0.81
i ] = qi, i∈St wt i ] = qi, i∈St wt 0.78
1wt). P av < α − 1 | 1 qt st 1wt)。 P av < α − >1 | 1 qt st 0.87
i ) ≥ α ≤ exp(−2 i ) ≥ α ≤ exp(−) 0.86
1t). (cid:32)(cid:88) 1t)。 (cid:32)(cid:88) 0.81
i∈St (cid:0)ˆqt i∈St (cid:0) 0.73
From Lemma 3 and Lemma 4, the proof follows. Lemma 3 と Lemma 4 の証明は以下の通りである。 0.76
(cid:4) (cid:4) (cid:4) (cid:4) 0.78
where 1 is the tolerance parameter and refers to the planner’s ability to tolerate a slighty lower average quality than required. ここで1は公差パラメータであり、必要よりもわずかに低い平均品質を許容するプランナーの能力を指します。 0.76
Henceforth, a super-arm will be called correct if it sat- したがって、スーパーアームは座ると正しいと呼びます。 0.68
isﬁes the QC approximately as described above. 上記のようにおよそ QC を満たします。 0.75
4.4 Regret Analysis of DPSS-UCB 4.4 dpss-ucbの後悔分析 0.54
In this section, we propose the regret deﬁnition for our problem setting that encapsulates the QC. 本稿では,QCをカプセル化した問題設定に対する後悔の定義を提案する。 0.77
We then upper bound the regret incurred by DPSS-UCB to be of the order O(ln T ). 次に DPSS-UCB が起こした後悔を O(ln T ) という順序に上限付ける。 0.64
We deﬁne regret incurred by an algorithm A on round 我々は、アルゴリズムAがラウンドで起こした後悔を定義する 0.66
i )+ and that of ˆqt i )+ と sqt のそれ 0.66
Proof. The proof is divided into two parts. 証明。 証明は2つの部分に分けられる。 0.71
Firstly, we show that for each t > τ round, the average value of (ˆqt i of the agents i in selected super-arm St is less than 2. 第一に、各 t > τ ラウンドにおいて、選択されたスーパーアーム St におけるエージェント i の平均値は t > τ 未満であることが示される。 0.67
Secondly, we show that if the average of ˆqt i is guaranteed to be above the threshold, then the average of qi over the selected agents would not be less than α − 1 with a high probability. 第二に、i の平均がしきい値を超えることが保証された場合、選択されたエージェントに対するqi の平均は、高い確率で α − s1 以下でないことが示される。 0.78
Lemma 3. The diﬀerence between the average of (ˆqt and the average of ˆqt 2, ∀t > τ . レマ3。 平均(qt)と平均(qt)の差は、τ である。 0.56
Proof. We have, i )+ i over the agents i in St is less than 証明。 あります。 i ) + セントのエージェント i 上の i はより小さいです。 0.59
(cid:0)(ˆqt (cid:88) (cid:0) (cid:88) 0.76
i∈St 1 st i )+ − ˆqt i∈St 1st i )+ − sqt 0.69
i (cid:1) = 私は (cid:1) = 0.69
(cid:88) i∈St (cid:88) i∈St 0.69
1 st √ 3 ln t(cid:112)2wt 1st √ 3 ln t(cid:112)2wt 0.82
i ≤ √ 3 ln t(cid:112)2wt 私は ≤ √ 3 ln t(cid:112)2wt 0.77
min t as follows: 分 t 以下に示す。 0.61
Regt(A) = (cid:40) Regt(A) = (cid:40) 0.82
(rq(S(cid:63)) − rq(St)) L (rq(S(cid:63)) − rq(St)) L 0.96
if St satisﬁes QC otherwise. StがQCを満足するなら。 0.66
= S(cid:63) = S(cid:63) 0.85
are argmaxS∈Sf rq(S) は argmaxS∈Sf rq(S) 0.78
where maxS∈Sf (rq(S(cid:63)) − rq(S)) is some constant. ここで maxS∈Sf (rq(S(cid:63)) − rq(S)) は一定である。 0.86
Sf Sf = {S|S ⊆ N and Hence, the cumulative regret in T rounds incurred by the algorithm is: Sf Sf = {S|S > N and Hence, the cumulative regret in T rounds in in the algorithm is: 0.88
= Here, subsets which satisﬁes QC; = ここでは、QCを満たす部分集合 0.63
i∈s xiqi i∈s xi i∈s xiqi i∈s xi 0.65
(cid:80) (cid:80) (cid:80)(cid:80) 0.73
and L feasible the およびL 実現可能 はあ? 0.59
Regt(A). (2) Regt(A)。 (2) 0.82
≥ qav}. T(cid:88) ≥qav。 T(cid:88) 0.69
t=1 . 5 Reg(A) = t=1 . 5 Reg(A) = 0.78

We now analyse the regret when the algorithm, A, is アルゴリズムがAであるときの後悔を分析します。 0.67
DPSS-UCB. Reg(A) = DPSS-UCB。 Reg(A) = 0.75
Regt(A) + Regt(A) Regt(A) + Regt(A) 0.85
τ(cid:88) T(cid:88) τ(cid:88) T(cid:88) 0.84
t=1 T(cid:88) ≤ L · τ + ≤ L · 3 ln T t=1 T(cid:88) ≤ L · τ + ≤ L · 3 ln T 0.77
+ t=τ +1 22 2 + t=τ+1 22 2 0.70
T(cid:88) t=τ +1 T(cid:88) t=τ+1 0.69
t=τ +1 Regt(A) t=τ+1 Regt(A) 0.70
Regt(A). Since our algorithm ensures that St satisﬁes the approximate QC for t > τ with a probability greater than 1 − σ, where σ = exp(−2 (cid:88) (cid:124) Regt(A)。 我々のアルゴリズムは、St が t > τ の近似 QC を 1 − σ より大きい確率で満足していることを保証するので、σ = exp(−\2 (cid:88) (cid:124) である。 0.77
(cid:2)(1 − σ)(rq(S(cid:63)) − rq(St))(cid:3) (cid:125) (cid:2)(1 − σ)(rq(S(cid:63)) − rq(St))(cid:3) (cid:125) 0.92
E[Reg(A)] ≤ L · 3 log T E[Reg(A)] ≤ L · 3 log T 0.79
1t), we have,  1t)であった。  0.72
(cid:123)(cid:122) (cid:123)(cid:122) 0.75
22 2 t≥τ + 22 2 t≥τ + 0.71
+σL  . +σL  . 0.72
Regu(T ) where St ∈ Sf . Regu(T) 場所 St ∈ Sf 。 0.77
Now, (cid:88) さて (cid:88) 0.80
σL = t≥τ (cid:88) (cid:18) 1 σL = t≥τ (cid:88) (cid:18) 1 0.75
t≥τ ∼ O T a Le(−2 t≥τ > O T Le (複数形 Les) 0.48
(cid:19) 1τ ) (cid:19) 1τ ) 0.83
1t) ≤ Le(−2 1 − e(−2 1) 32 1 22 2 1t) ≤ Le(−\2 1 − e(−\2 1) 3\2 1 2\2 2 0.84
, where a = (3) a = である。 (3) 0.72
. Now we bound the cumulative regret incurred after t > τ rounds when QC is satisﬁed, i.e., Regu(T ). . さて、QC を満たすとき t > τ ラウンド後に生じる累積的後悔、すなわち Regu(T ) を束縛する。 0.76
Here we adapt the regret proof given by . ここでは が与えた後悔の証明に適応する。 0.68
We highlight the similarities and diﬀerences of our setting with theirs and use it to bound Regu(T ). 設定の類似点と相違点を強調して、Regu(T)のバインドに使用します。 0.61
Bounding Regu(T ): Bounding Regu(T): 0.79
 have proposed CUCB algorithm to tackle CMAB problem which they prove to have an upper bound regret of O(ln T ). は,O(ln T )の上界後悔を証明したCMAB問題に対処する CUCB アルゴリズムを提案している。 0.82
Following is the CMAB problem setting considered in : 以下はで考慮されたCMABの問題設定です。 0.65
• There exists a constrained set of super-arms χ ⊆ 2N • 制約付きスーパーアームの集合が存在して 2N となる。 0.66
available for selection. 選択のために利用できる。 0.58
• There exists an oﬄine (η, ν)-approximation oracle, (η, ν ≤ 1) s.t. • オフライン (η, ν) 近似の oracle, (η, ν ≤ 1) s.t が存在する。 0.87
for a given quality vector q(cid:48) as input, it outputs a super-arm, S, such P(rq(cid:48)(S) ≥ η·optq(cid:48)) ≥ ν, where optq(cid:48) is the optimal reward for quality vector q(cid:48) as input. 与えられた品質ベクトルq(cid:48)を入力として出力すると、P(rq(cid:48)(S)のようなスーパーアームSを出力し、オプトク(cid:48)を入力として品質ベクトルq(cid:48)に最適な報酬とする。 0.87
• Their regret bounds hold for any reward function that follows the properties of monotonicity and bounded smoothness (deﬁned below). • 彼らの後悔の境界は、単調性と境界平滑性の性質に従う任意の報酬関数を保持します(後述)。 0.68
• Similar to our setting, they assume a semi-bandit •我々の設定と同様、半バンドを想定する 0.75
feedback mechanism. フィードバックメカニズム。 0.67
Now, we state the reasons to adopt the regret analysis さて、我々は後悔分析を採用する理由を述べます。 0.73
provided by  to bound Regu(T ) 10]によってRegu(T)に束縛される 0.82
1. We have shown that after τ rounds, we get the constrained set of super-arms, χ, i.e., the set of superarms that satisﬁes QC), which forms a well deﬁned constrained set, to select from in future rounds (t > τ ). 1. 我々は τ ラウンドの後、制約付きスーパーアームの集合、すなわち QC を満たすスーパーアームの集合を、将来のラウンド (t > τ ) から選ぶために、明確に定義された制約付き集合として得ることを示した。 0.76
2. We remark here that the utility function considered in our problem setting follows both the required properties, namely, (i) Monotonicity: The expected reward of playing any super-arm S ∈ χ is monotonically non-decreasing with respect to the quality vector, i.e., let q and q be two quality vectors such that ∀i ∈ N , qi ≤ qi, we have rq(S) ≤ rq(S) for all S ∈ χ. 2. ここで、我々の問題設定で考慮される効用関数は、要求される性質、すなわち (i) 単調性、すなわち、任意のスーパーアーム s ∈ s をプレイする期待報酬は、品質ベクトルに関して単調に非負である、すなわち、q と q を 2 つの品質ベクトルとし、それは、すべての s ∈ n , qi ≤ qi に対して rq(s) ≤ rq(s) である。 0.84
Since our reward function is linear, it is trivial to note that it is monotone on qualities. 私たちの報酬関数は線形であるため、品質上の単調であることに注意することは自明です。 0.60
(ii) Bounded Smoothness: There exists a strictly increasing (and thus invertible) function f (. (ii) Bounded Smoothness: 厳密に増加する(したがって可逆)関数 f(.) が存在する。 0.87
), called bounded smoothness function, such that for any two quality vectors q and q, we have rq(S) − rq(S) ≤ f(Λ) if maxi∈S qi - qi ≤ Λ. は有界滑らか性函数と呼ばれ、任意の2つの品質ベクトル q と q に対して、最大値 S qi - qi ≤ φ に対して rq(S) − rq(S) ≤ f( ) となる。 0.86
As our reward function is linear in qualities, f (Λ) = nR × Λ is the bounded smoothness function for our setting, where n is the number of agents. 私たちの報酬関数は質が線形であるため、f (*) = nR × ^ は我々の設定の有界平滑化関数であり、ここでは n はエージェントの数である。 0.74
3. Oracle: Analogous to the oracle assumption in , we have assumed the existence of an algorithm SSA (Section 4.2). 3. Oracle: のオラクルの仮定に類似して、アルゴリズムSSA(Section 4.2)の存在を想定しています。 0.80
For DPSS-UCB, we use DPSS (Algorithm 1) as our SSA . DPSS-UCBでは、DPSS(Algorithm 1)をSSAとして使用しています。 0.62
As DPSS provides exact solution, it acts as an (η, ν)- approximate oracle for DPSS-UCB with η = 1 = ν. DPSS は正確な解を提供するので、 η = 1 = ν で DPSS-UCB の (η, ν)-近似オラクルとして機能する。 0.72
However, to ensure χ consists of all the correct superarms, we need one additional property that should be satisﬁed, namely -seperatedness property. しかし、すべての正しいスーパーアームで構成されていることを保証するには、満足すべき追加のプロパティが1つ必要である。 0.63
(cid:80) Deﬁnition 1. (cid:80) 定義1 0.87
We say q = (q1, q2, . q = (q1, q2, ) である。 0.77
. . , qn) satisﬁes i∈S qi s.t. . . qn) qi∈S qi s.t を満たす。 0.82
U (S) (cid:54)∈ seperatedness if ∀S ⊆ N , U (S) = 1 (α − , α) U (S) (cid:54)∈ seperatedness (U (S) = 1 (α − s, α) 0.72
s This suggests that there is no super-arm S ∈ χ, such i ≤ α. s このことは、i ≤ α のような超武装 s ∈ s は存在しないことを示唆する。 0.74
It is important for DPSSthat α −  ≤ 1|S| UCB to satisfy 1-seperatedness because if there exists such a super-arm, for which the average quality is between (α−1, α), DPSS-UCB will include it in χ due to tolerance parameter 1 while it would violate the QC. DPSSにとって重要なことは、平均品質が(α−*1, α)の間にあるような超腕が存在する場合、DPSS-UCBはQCに反する間、公差パラメータ *1 により ^1 に含められるので、 DPSS が ^1-分離を満たすことである。 0.66
i∈S qt (cid:80) i∈S qt (cid:80) 0.75
Theorem 5. seperatedness, then Regu(T ) is bounded by O(ln T ). Theorem 5. seperatedness, then Regu(T ) は O(ln T ) で有界である。 0.85
If qualities of the agents satisfy 1- もしその性質が エージェントは1を満足する 0.66
Proof. Following from the proof in , we deﬁne some parameters. 証明。 10] の証明に従うと、いくつかのパラメータを定義する。 0.68
A super-arm, S is bad if rq(S) < optq. 超腕 S は rq(S) < optq ならば悪い。 0.70
Deﬁne SB as the set of bad super-arms. SBを悪いスーパーアームの集合として定義する。 0.66
For a given underlying agent i ∈ [n], deﬁne: 与えられた基底エージェント i ∈ [n] に対して、次のように定義する。 0.57
min = optq − max{rq(S)|S ∈ SB, i ∈ S} ∆i max = optq − min{rq(S)|S ∈ SB, i ∈ S}. min = optq − max{rq(S)|S ∈ SB, i ∈ S} , i max = optq − min{rq(S)|S ∈ SB, i ∈ S} である。 0.94
∆i Using the same proof as in , we can show that, VT , the expected number of times we play a sub-optimal agent till round T , is upper bounded as: 四位 10]と同じ証明を使用して、VT、ラウンドTまでのサブオプティマティブエージェントを再生する期待回数は、次のように上限があることを示すことができます。 0.46
T(cid:88) VT ≤ n(lT ) + T(cid:88) VT ≤ n(lT ) + 0.85
2n t2 ≤ n(lT ) + (cid:18) π2 (cid:19) · n. 2n t2 ≤ n(lT ) + (cid:18) π2 (cid:19) · n。 0.82
t=τ 6n · ln T t= 6n · ln t 0.83
(f−1(∆min))2 + (f−1(イミン))2 + 0.91
3 T(cid:88) 3 T(cid:88) 0.85
t=1 2n t2 ≤ t=1 2n t2 ≤ 0.71
6 6 0.85

(f−1(∆min))2 . (f−1(イミン))2。 0.77
Hence, we can bound the regret それゆえ 後悔を縛ることができます 0.68
6 ln T where lT = as:Regu(T ) ≤ VT · ∆max ≤ 6 ln T ここで lT = as:Regu(T ) ≤ VT · >max ≤ 0.88
(cid:18) (cid:32) (cid:18) (cid:32) 0.78
= 6 · ln T ( ∆min R )2 = 6 · ln T(シュミンR)2。 0.83
+ 6 · ln T + 6 · ln t 0.84
(cid:33) (f−1(∆min))2 + π2 3 (cid:33) (f−1(イミン))2 + π2 3 0.84
n · ∆max. (cid:19) n · . . . (cid:19) 0.73
π2 3 n · ∆max π2 3 n · . . . 0.69
(cid:4) Substituting the results of Theorem 5 in Equation 3, (cid:4) Equation 3 における Theorem 5 の結果の代用 0.82
we prove that DPSS-UCB incurs a regret of O(ln T ). DPSS-UCB が O(ln T ) の後悔を引き起こすことを証明した。 0.62
5 Greedy Approach 5 Greedy アプローチ 0.80
In the previous sections, we propose a framework and dynamic programming based algorithm to solve our subset selection problem for both when the agents’ quality is known and not. 前節では、エージェントの品質が分かっていない場合にも、サブセット選択の問題を解決するためのフレームワークと動的プログラミングに基づくアルゴリズムを提案する。 0.82
Since DPSS explores all the possible combinations of the selection vector and the utility associated with it, the complexity of DPSS is of O(2n), which makes it diﬃcult to scale when n is large. DPSS は選択ベクトルとそれに関連するユーティリティのすべての可能な組み合わせを探索するので、DPSS の複雑さは O(2n) であり、n が大きくなるとスケールが困難になる。 0.84
To overcome this limitation, we propose a greedy based approach to our problem. この制限を克服するため,我々は欲求に基づくアプローチを提案する。 0.71
When the quality of agents are known, we propose GSS that runs in polynomial time, O(n log n), and provides an approximate solution to our ILP. エージェントの品質が分かっている場合、多項式時間O(n log n)で動作するGASを提案し、我々のILPに近似したソリューションを提供する。 0.70
Then, we use GSS as our SSA in the SS-UCB framework and propose GSS-UCB as an alternate algorithm to DPSS-UCB in the setting where the qualities of the agents are unknown. そこで、SS-UCBフレームワークではGSSをSSAとして使用し、エージェントの品質が不明な設定でDPSS-UCBに代わるアルゴリズムとしてGSS-UCBを提案する。 0.78
5.1 Greedy Subset Selection (GSS) 5.1 グリーディサブセット選択(GSS) 0.86
Greedy algorithms have been proven eﬀective to provide approximate solutions to ILP problems such as 0-1 knapsack. グリーディアルゴリズムは、0-1 ナップサックのような ilp 問題の近似解を提供するのに有効であることが証明されている。

0.61
They do so by solving linearly relaxed variants of an ILP, such as fractional knapsack, and removing any fractional unit from its solution. 彼らは、分数knapsackのようなILPの線形に緩和された変種を解き、その溶液から分数単位を除去する。 0.66
We propose a similar algorithm for our subset selection problem by allowing xi ∈ [0, 1]. 我々は、xi ∈ [0, 1] を許すことにより、部分集合選択問題に対して同様のアルゴリズムを提案する。 0.65
However, we cannot simply remove fractional units from our solution, as it may lead to QC violation. しかし、QC違反につながる可能性があるため、ソリューションから分数単位を削除することはできません。 0.69
Consider the following example: 以下の例を考えてみよう。 0.66
Given n = 2 agents with qualities, q = [0.6, 0.9], c = [10, 100] and α = 0.7. n = 2 つの性質を持つエージェント q = [0.6, 0.9], c = [10, 100], α = 0.7 が与えられる。 0.87
Allowing fractional units to be taken, the optimal solution would be to take x1 = 1, x2 = 0.5 units of the two agents. 取るべき分数単位が与えられると、最適解は x1 = 1, x2 = 0.5 個のエージェントを取ることである。 0.83
Removing fractional units would lead to selecting only the ﬁrst agent, which violates the QC. 分数単位を除去すると、QCに違反する最初のエージェントのみを選択する。 0.76
Towards this, we include an additional step (Line 22, Algorithm 3) in our algorithm that ensures that QC is not violated. これに向けて、我々はQCに違反しないようにアルゴリズムに追加のステップ(Line 22 Algorithm 3)を含める。 0.79
Formally, the algorithm proceeds as follows: 正式なアルゴリズムは次のとおりである。 0.73
1. Divide the agents into the four categories, namely, 1. エージェントを4つのカテゴリに分割します。 0.76
S1,S2,S3,S4, as described in Section 3.4. S1,S2,S3,S4は3.4節に記載されている。 0.60
2. Select all agents in S1. 2. S1のすべてのエージェントを選択します。 0.72
Let d = (cid:80) d = (cid:80) とする。 0.61
(qi − α) be the excess quality accumulated and as before, drop all agents in S4. (qi − α) は蓄積された過剰な品質であり、以前と同様に全てのエージェントを S4 にドロップする。 0.66
i∈S1 3. For agents in S2, sort them in the decreasing order of revenue gained per unit loss in quality ( ri ). i∈S1 3. S2のエージェントの場合、品質の単位損失(ri)ごとに得られた収益の減少順にそれらを並べ替えます。 0.68
Simα−qi ilarly, for agents in S3, sort them in the increasing order of revenue lost per unit gain in quality ( ri ). Simα−qi は、S3 のエージェントに対して、品質の単位利益 (ri ) 当たりの売上増加順に並べ替える。 0.62
α−qi 7 4. Select units (could be fractional) from agents from S2 until the total loss of quality is no more than d. Essentially, we use the agents in S2 to increase revenue while ensuring average quality is above the threshold. α-qi 7 4. 基本的に、私たちはS2のエージェントを使用して、平均品質がしきい値を超えることを保証しながら、収入を増やす。

0.73
5. For agents in S2 with remaining fractional units, we pair them up with an equivalent fractional unit of an agent in S3 that balances the loss in average quality. 5. 残りの分数単位を持つS2のエージェントの場合、平均品質の損失のバランスをとるS3のエージェントの同等の分数単位とそれらをペアリングします。 0.82
6. When the revenue gained per unit loss in quality from the ﬁrst non-exhausted agent in S2 is less than the revenue lost per unit gain of quality from the ﬁrst non-exhausted agent in S3, terminate the algorithm. 6. S2の最初の非排出エージェントから品質の単位損失当たりの収益が、S3の最初の非排出エージェントから品質の単位損失当たりの収益未満である場合、アルゴリズムを終了します。 0.85
An agent is exhausted if the unit produce is completely selected. ユニット生産品が完全に選択された場合、エージェントは枯渇する。 0.65
7. For any agent in S3 with a fractional unit, take the complete unit instead. 7. 分数単位の S3 内の任意のエージェントは、代わりに完全な単位を取る。 0.80
For all other agents, remove any fractional units selected. 他のすべてのエージェントは、選択された分数単位を削除する。 0.62
Algorithm 3 GSS アルゴリズム3 GSS 0.73
5: ∀i ∈ S1, xi = 1; d =(cid:80) 5: xi ∈ s1, xi = 1; d =(cid:80) 0.88
1: Inputs: N , α, R, costs c = [ci], qualities q = [qi] 2: Output: Quantities procured x = (x1, . 1: 入力: N , α, R, コスト c = [ci], 品質 q = [qi] 2: 出力: 調達される数量 x = (x1, .)。 0.83
. . , xn) 3: Initialization: ∀i ∈ N , ri = Rqi − ci 4: Segregate S1,S2,S3,S4 as described in Section 3.4 6: ∀i ∈ S4, xi = 0 7: L2 = sort(S2) on decreasing order of 8: L3 = sort(S3) on increasing order of 9: p = 0, q = 0 10: while d > 0 and p < |S2| do . . S1, S2, S3, S4: Segregate S1, S4, xi = 0 7: L2 = sort(S2) on decrease order of 8: L3 = sort(S3) on increasing order of 9: p = 0, q = 0 10: while d > 0 and p < |S2| do

0.84
(qi − α) ri α−qi ri α−qi (qi − α) ri α−qi ri α−qi 0.75
i∈S1 11: 12: 13: i∈S1 11: 12: 13: 0.66
i = L2[p]; if α − qi ≤ d then xi = 1, d = d − α − qi, p+ = 1 else xi = d i = L2[p]; α − qi ≤ d ならば xi = 1, d = d − α − qi, p+ = 1 その他 xi = d となる。 0.95
, d = 0 α−qi , d = 0。 α-qi 0.73
14: while p < |S2| and q < |S3| do 14: p < |S2| と q < |S3| do 0.79
17: 18: 19: 17: 18: 19: 0.85
15: 16: i = L2[p], j = L3[q] , b = rj a = ri α−qj α−qi if a ≤ b then break; w1 = min((1 − xi)(α − qi), (1 − xj)(qj − α)) xi+ = w1 , xj+ = w1 α−qi qj−α if xi == 0 then p + +; if xj == 0 then q + +; 21: 22: if 0 < xj < 1 then xj = 1 23: return (cid:98)x(cid:99) 15: 16: i = L2[p], j = L3[q] , b = rj a = ri α−qj α−qi if a ≤ b then break; w1 = min((1 − xi)(α − qi), (1 − xj)(qj − α)) xi+ = w1 , xj+ = w1 α−qi qj−α if xi == 0 ならば p + +; xj == 0 ならば q + +; 21: 22: if 0 < xj < 1 then xj = 1 23: return (cid:98)x(cid:99) 0.92
20: 5.2 Approximation Ratio 20: 5.2 近似比 0.75
While GSS is computationally more eﬃcient than DPSS, it is important to note that it may not always return the optimal subset of agents. GSSはDPSSよりも計算効率が高いが、エージェントの最適部分集合を常に返さないことに注意する必要がある。 0.74
We show for the following example, that GSS doesn’t have a constant approximation w.r.t. 次の例では、GSS が定数近似 w.r.t を持たないことを示しています。 0.64
the optimal solution: Consider n = 3 agents with qualities, q = [1.00, 0.98, 0.97] and c = [R − , 78R 100 ]. 最適解: 品質を持つ n = 3 個のエージェント q = [1.00, 0.98, 0.97] と c = [R − ..., 78R 100 ] を考える。 0.87
Hence, r = [, R 2 ], where R is some constant as discussed before such that ri = Rqi − ci. したがって、r = [ , R 2 ], ここで R は ri = Rqi − ci となるような前に述べたような定数である。 0.90
If α = 0.99, the value of ri α−qi for the third agent is higher than that of the second, but only a fractional unit can pair with the ﬁrst agent. α = 0.99 の場合、第3のエージェントに対する ri α-qi の値は第2のエージェントよりも高いが、第1のエージェントと結合できるのは分数単位のみである。 0.78
Hence, according to GSS, we only select the ﬁrst agent giving us a utility of , whereas the optimal utility is equal to  + R 5 したがって、GSS によれば、我々は最初のエージェントだけを選択すべきであり、一方最適効用は s + R 5 に等しい。 0.67
100 , 47R 5 , R 100,47R 5, R。 0.88

corresponding to choosing the ﬁrst and the third agent. 第1および第3のエージェントの選択に対応する。 0.75
. Since  can take Thus, the approximation ratio is an arbitrary small value, the approximation ratio between the utility achieved by GSS and DPSS can be arbitrary small. . これにより、近似比は任意の小さい値となるので、GASとDPSSで達成したユーティリティの近似比は任意の小さい値となる。 0.78
+ R 5  However, through experiments, we show that in practice, GSS gives close to optimal solutions at a huge computational beneﬁt that allows us to scale our framework for a large number of agents, such as in an E-commerce setting. ～+R5  しかし、実験を通じて、実際に、GSSは、Eコマースの設定など、多数のエージェントに対して、我々のフレームワークをスケールできる巨大な計算上の利点で、最適なソリューションをほぼ提供することを示す。 0.78
5.3 GSS-UCB 5.3 GSS-UCB 0.50
When we use GSS as the SSA in our SS-UCB framework, we refer to the algorithm as GSS-UCB. SS-UCB フレームワークで GSS を SSA として使用する場合、このアルゴリズムを GSS-UCB と呼ぶ。 0.86
While the regret analysis may not necessarily hold, as GSS does not have a constant approximation, we still show that in practice, it works as good as DPSS-UCB in both (i) achieving constraint satisfaction after τ rounds and (ii) the regret incurred thereafter. 後悔分析は必ずしも成り立たないが,GASには一定の近似がないため,実際にはDPSS-UCBと同等に機能し,τラウンド後の制約満足度とその後の後悔度の両方で有効であることを示す。 0.72
We show this via experiments, as discussed in Section 6. 第6節で論じたように,実験を通じてこれを示す。 0.67
6 Experimental Analysis 6.1 Subset Selection With Known Quali- 6 実験分析 6.1 Quali のサブセット選択 0.84
ties In this section, we compare the performance of GSS with DPSS in the setting where quality of the agents is known. 結び合い 本稿では,エージェントの質が分かっている環境でのgssの性能とdssの性能を比較した。 0.58
In Figure 1a, we compare the ratio of the utility achieved by GSS (zgss) to the utility achieved by DPSS (zdpss) while ensuring the QC is met. 図1aでは、GSS(zgss)が達成したユーティリティとDPSS(zdpss)が達成したユーティリティの比率を比較し、QCが満たされることを保証する。 0.71
In Figure 2, we present a box plot of the distribution of the ratios of these utilities over 1000 iterations for α = 0.7. 図2では、α = 0.7 に対して、これらのユーティリティの1000回のイテレーションに対する比率の分布のボックスプロットを示す。 0.76
To compare the performance of GSS for much larger values of n, we compare it against the utility achieved by an ILP solver (zilp), namely, the COIN-OR Branch and Cut Solver (CBC)  since the computational limitations of DPSS made it infeasible to run experiments for large values of n. The results for the same are presented in Figure 1b. gssの性能を n のはるかに大きな値と比較するために、これを ilp ソルバ (zilp) が達成したユーティリティ、すなわち、dpss の計算上の制限により n の大きな値に対する実験が不可能になったため、coin-or branch and cut solver (cbc)  と比較する。

0.71
Lastly, in Table 1, we compare the ratio of the time taken by GSS (tgss) with respect to DPSS (tdpss) and the ILP solver (tilp) for diﬀerent values of n with α being set to 0.7. 最後に、表1では、n の異なる値に対する DPSS (tdpss) および ILP ソルバー (tilp) に対する GSS (tgss) の時間比を比較し、α が 0.7 に設定されている。 0.78
6.1.1 Setup 6.1.1 セットアップ 0.49
For diﬀerent values of n, the number of agents and α, the quality threshold, we generate agents with qi and ci both ∼ U [0, 1]. n の異なる値、エージェントの数、α、品質のしきい値に対しては、qi と ci の両方で U[0, 1] のエージェントを生成します。 0.76
For Figure 1a and 1b, we average our results over 1000 iterations for each (n, α) pair, while in Figure 2, we plot the distribution of the ratios obtained in each of the 1000 iterations for diﬀerent values of n with α set to 0.7. 図 1a と 1b に対して、各 (n, α) 対について、平均1000回以上の結果が得られるのに対し、図 2 では、0.7 に設定された n の異なる値に対して、1000回ごとに得られる比率の分布をプロットする。 0.76
We use R = 1 for all our experiments. すべての実験に R = 1 を使用します。 0.87
indicates that GSS performs almost as good as DPSS in practice with an exponentially improving computational performance in terms of time complexity with respect to DPSS and an almost 50x improvement over the ILP solver as well. GSSは実際にDPSSとほぼ同じ性能を発揮し、DPSSに対する時間の複雑さと、ILPソルバに対する50倍近い改善の点で計算性能を指数関数的に改善していることを示している。 0.76
This establishes the eﬃcacy of GSS for practical use at scale. これは大規模で実用的使用のためのGSSの有効性を確立します。 0.50
n 2 5 8 10 12 14 16 18 20 n 2 5 8 10 12 14 16 18 20 0.85
tdpss : tgss tdpss : tgss 0.85
tilp : tgss tilp : tgss 0.85
5.5 15.7 32.6 54.3 106.3 284.4 897.1 3109.7 11360.6 5.5 15.7 32.6 54.3 106.3 284.4 897.1 3109.7 11360.6 0.42
70 64 63.7 58.6 67.6 65.3 60.2 63.1 68.1 70 64 63.7 58.6 67.6 65.3 60.2 63.1 68.1 0.49
n tilp : tgss n tilp : tgss 0.85
25 50 100 400 1000 5000 10000 50000 100000 25 50 100 400 1000 5000 10000 50000 100000 0.85
66.7 58.3 52.7 43.1 31.8 31.6 34.5 45 56.8 66.7 58.3 52.7 43.1 31.8 31.6 34.5 45 56.8 0.45
Table 1: Computational performance of GSS w.r.t. 表1: GSS w.r.t の計算性能 0.79
to DPSS and ILP へ DPSSとILP 0.72
6.2 Subset Selection With Unknown 6.2 未知のサブセット選択 0.83
Qualities In this section, we present experimental results of DPSSUCB and GSS-UCB towards the following: 特質 このセクションでは、DPSSUCB と GSS-UCB の実験結果を以下に示します。 0.69
1. Constraint Satisfaction: As discussed in section 4.3, DPSS-UCB satisﬁes the QC approximately with high probability after τ = 3 ln T rounds. 1. 制約満足度: 第4.3節で述べたように、DPSS-UCB は τ = 3 ln T ラウンドの後に QC を満たす。 0.78
Here, α+2 is the 22 2 target constraint of the agent when α is the required average quality threshold. ここで α + 2 は、α が要求される平均品質閾値であるとき、エージェントの 2 対 2 の目標制約である。 0.70
Towards this, we plot the average number of iterations where DPSS-UCB and GSS-UCB returns a subset that satisﬁes QC at each round in our experiment for diﬀerent values of 2. これに向けて, dpss-ucb と gss-ucb が各ラウンドの qc を満たす部分集合を 2 の異なる値で返却するイテレーションの平均数をプロットする。 0.65
2. Regret incurred for t > τ : We show that the regret incurred by our algorithm for t > τ , follows a curve upper bounded by O(ln T ). 2. t > τ : t > τ のアルゴリズムによって得られた後悔は、O(ln T ) で有界な曲線の上を辿ることを示す。 0.78
Towards this we plot the cumulative regret vs. round t, where τ < t ≤ T . これに向けて τ < t ≤ T であるような累積後悔対円 t をプロットする。 0.80
6.1.2 Results and Discussion 6.1.2 結果と議論 0.58
As can be seen from Figures 1a and 1b, the average ratio of both ( zgss ) lies approximately between zdpss [0.94,1.0], with a median of 1.0 for almost all values of n and only a few outliers and a few rare instances when the ratio drops below 0.2 as evident from Figure 2. 図1aと1bからわかるように、両方の平均比率(zgss )はzdpss [0.94,1.0]の間にあり、nのほぼすべての値に対する1.0の中央値と、数個の外れ値と、図2から明らかな0.2を下回った場合のまれなインスタンスのみである。 0.76
This ) and ( zgss zilp これ ) と (zgss zilp) 0.81
To carry out these experiments, we generated n = 10 agents with both qi, ci ∼ U [0, 1]. これらの実験を行うため、n = 10 個のエージェントを qi, ci > U [0, 1] で生成した。 0.80
We chose α = 0.7 as for a higher value of α the number of super-arms satisfying QC is very low and hardly much to learn whereas for a low value, the number of super-arms that satisfy QC is very high but practically of not much interest. 我々は、α のより高い値として α = 0.7 を選択し、QC を満たすスーパーアームの数は極めて低く、学習しにくいが、QC を満たすスーパーアームの数は非常に高いが、実際はあまり興味がない。 0.69
In Figure 6.2.1 Setup 図中 6.2.1 セットアップ 0.48
8 8 0.85

(a) w.r.t DPSS a) w.r.t DPSS 0.77
(b) w.r.t. (b) w.r.t. 0.71
ILP Figure 1: Performance of GSS on diﬀerent values of α ILP 図1: α の異なる値に対する GSS の性能 0.86
Figure 2: GSS vs DPSS ratio distribution 図2:GSS対DPSS比分布 0.72
Figure 3: Regret incurred for t > τ 図3: t > τ に対する後悔 0.73
Figure 4: Constraint satisfaction at each round 図4:各ラウンドでの制約満足度 0.83
4, we perform the experiment over a varied range of values of 2, whereas in Figure 3, we set 2 = 0.01. 4) の値の異なる範囲で実験を行い, 図3では, 2 = 0.01 とする。 0.67
We average our results for 1000 iterations of each experiment. 各実験の1000回のイテレーションで結果を平均します。 0.77
For example, in Figure 4, a value of 0.4 at some round t, would denote that in 40% of the iterations, the QC was satisﬁed at round t. For both the experiments, R = 1 and T = 100000. 例えば、図4では、ある円tにおける0.4の値は、繰り返しの40%において、QCは円tで満たされたことを意味する。

0.75
7 Conclusion and Future Work 7 結論と今後の課題 0.78
In this paper, we addressed the class of problems where a central planner had to select a subset of agents that maximized its utility while ensuring a quality constraint. 本稿では,中央計画立案者が品質制約を確保しつつ,その有効性を最大化するエージェントのサブセットを選択する必要がある問題に対処する。 0.80
We ﬁrst considered the setting where the agents’ quality is known and proposed DPSS that provided an exact solution to our problem. まず、エージェントの品質がわかっている設定を検討し、問題に正確な解決策を提供するDPSSを提案しました。 0.65
When the qualities were unknown, we modeled our problem as a CMAB problem with semibandit feedback. 品質が不明な場合、半バンドフィードバックを伴うcmab問題として問題をモデル化した。 0.59
We proposed SS-UCB as a framework to address this problem where both the constraint and the objective function depend on the unknown parameter, a setting not considered previously in the literature. そこで本研究では, 制約関数と目的関数の両方が未知のパラメータに依存しているという問題に対処するためのフレームワークとしてSS-UCBを提案した。 0.72
Using DPSS as our SSA in SS-UCB, we proposed DPSS-UCB that incurred a O(ln T ) regret and achieved constraint satisfaction with high probability after τ = O(ln T ) rounds. SS-UCB では DPSS を SSA として用い,O(ln T ) の後悔を招き,τ = O(ln T ) ラウンド後に高い確率で制約満足度を達成できるDPSS-UCB を提案した。 0.77
To address the computational limitations of DPSS, we proposed GSS for our problem that allowed us to scale our framework to a large number of agents. DPSSの計算上の限界に対処するため、我々はフレームワークを多数のエージェントにスケールできる問題に対してGSSを提案しました。 0.74
Via simulations, we showed the eﬃcacy of GSS. シミュレーションの結果, GSSの有効性が示された。 0.67
The SS-UCB framework proposed in this paper can be used to design and compare other approaches to this class of problems that ﬁnd its applications in many ﬁelds. 本論文で提案するSS-UCBフレームワークは、多くの分野で応用されているこの問題に対する他のアプローチの設計と比較に用いることができる。 0.81
It can also easily be extended to solve for other interesting variants of the problem such as (i) where the pool of agents to choose from is dynamic with new agents entering the setting, (ii) where an agent selected in a particular round is not available for the next few rounds (sleeping bandits) possibly due to lead time in procuring the units, a setting which is very common in operations research literature. i)選択するエージェントのプールが新しいエージェントで動的に設定に入る場合、(ii)特定のラウンドで選択されたエージェントが、ユニットの調達にリードタイムがあるため、次の数ラウンド(スリーピングバンド)で利用できない場合、運用研究文献で非常に一般的な設定など、問題の他の興味深い変種のために簡単に解決することができます。 0.73
Our work can also be extended to include strategic agents where the planner needs to design a mechanism to elicit the agents’ cost of production truthfully. 私たちの作業は、プランナーがエージェントの真面目な生産コストを引き出すメカニズムを設計する必要がある戦略的エージェントを含むように拡張することも可能です。 0.79
6.2.2 Discussion Higher the value of 2, higher is the target constraint and thus more conservative is our algorithm in selecting the subset of agents. 6.2.2 議論 2 の値が高く、より高い値が対象の制約であり、従ってより保守的なアルゴリズムはエージェントのサブセットを選択する。 0.60
Therefore, we achieve correctness quickly, which is evident from Figure 4. したがって、図4から明らかな正しさを迅速に達成します。 0.81
In all three cases, the algorithm achieves correctness in close to 100% of the iterations, after 3 ln T rounds (indicated by the vertical 22 2 dotted line), which justiﬁes our value of τ . いずれの場合も、このアルゴリズムは3 ln T ラウンド(垂直 2 × 2 点線で示される)の後に、100% に近い精度で正当性を達成し、τ の値を正当化する。 0.77
Similarly, the regret incurred by DPSS-UCB for t > τ follows a curve upper bounded by O(ln T ). 同様に、 t > τ に対する DPSS-UCB による後悔は、O(ln T ) で有界な曲線の上を辿る。 0.72
The regret incurred by GPSSUCB is slightly lower than DPSS-UCB which further establishes the eﬃcacy of our greedy approach. GPSSUCBが起こした後悔はDPSS-UCBよりもわずかに低いため,我々の欲求的アプローチの有効性がさらに確立される。 0.67
References  Kontogeorgos Achilleas and Semos Anastasios. 参考文献  Kontogeorgos AchilleasとSemos Anastasios。 0.72
Marketing aspects of quality assurance systems: The organic food sector case. 品質保証システムのマーケティング的側面:有機食品セクターの場合。 0.80
British Food Journal, 110(8):829–839, 2008. British Food Journal, 110(8):829-839, 2008 0.92
 Shipra Agrawal and Nikhil R Devanur.  Shipra AgrawalとNikhil R Devanur。 0.72
Bandits with concave rewards and convex knapsacks. コンケーブの報酬と凸ナプサックを持つバンド。 0.61
In Proceedings of the ﬁfteenth ACM conference on Economics and computation, pages 989–1006, 2014. 第15回 ACM Conference on Economics and Computing (英語) Proceedings of the 15th ACM Conference on Economics and Compute, pages 989–1006, 2014 0.58
9 9 0.85

 Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. 3] Peter Auer、Nicolo Cesa-Bianchi、Paul Fischer。 0.70
Finite-time analysis of the multiarmed bandit problem. マルチアームバンディット問題の有限時間解析。 0.62
Machine learning, pages 235–256, 2002. 機械学習、2002年235-256頁。 0.80
 Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. 4]Ashwinkumar Badanidiyuru,Robert Kleinberg,Aleksandrs Slivkins。 0.58
Bandits with knapsacks. ナップサックの包帯。 0.47
In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 207–216. 2013年、IEEE 54th Annual Symposium on Foundations of Computer Science, pages 207–216。 0.81
IEEE, 2013. 2013年、IEEE。 0.59
 Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. 5]Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. 0.77
Resourceful contextual bandits. 有意義な文脈の盗賊。 0.39
In Conference on Learning Theory, pages 1109–1134, 2014. Conference on Learning Theory, Page 1109–1134, 2014 0.78
 Arpita Biswas, Shweta Jain, Debmalya Mandal, and Y. Narahari. 6] Arpita Biswas、Shweta Jain、Debmalya Mandal、Y. Narahari。 0.65
A truthful budget feasible multi-armed bandit mechanism for crowdsourcing time critical tasks. タイムクリティカルなタスクをクラウドソーシングするための真の予算実現可能なマルチアームバンディットメカニズム。 0.55
In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’15, pages 1101–1109, Richland, SC, 2015. International Foundation for Autonomous Agents and Multiagent Systems. 2015年のIn Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’15, pages 1101–1109, Richland, SC, 2015 International Foundation for Autonomous Agents and Multiagent Systems。 0.91
 S´ebastien Bubeck and Nicolo Cesa-Bianchi. S ́ebastien Bubeck と Nicolo Cesa-Bianchi。 0.78
Regret analysis of stochastic and nonstochastic multi-armed bandit problems. 確率的および非確率的多重武装バンディット問題の回帰解析 0.64
Machine Learning, 5(1):1–122, 2012. 機械学習, 5(1):1–122, 2012 0.87
 Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. 8] Shouyuan Chen、Tian Lin、Irwin King、Michael R Lyu、Wei Chen。 0.65
Combinatorial pure exploration of multi-armed bandits. 多腕バンディットのコンビネーション・純粋な探索 0.53
In Advances in Neural Information Processing Systems 27, pages 379–387. In Advances in Neural Information Processing Systems 27 ページ 379–387。 0.82
2014.  Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. 2014. 9] Wei Chen、Wei Hu、Fu Li、Jian Li、Yu Liu、Pinyan Lu。 0.76
Combinatorial multi-armed bandit with general reward functions. 一般報酬機能を有する複合多腕バンディット 0.60
In Advances in Neural Information Processing Systems, pages 1659–1667, 2016. Advanceds in Neural Information Processing Systems, page 1659–1667, 2016 0.76
 Wei Chen, Yajun Wang, and Yang Yuan.  Wei Chen、Yajun Wang、Yang Yuan。 0.66
Combinatorial multi-armed bandit: General framework and applications. combinatorial multi-armed bandit: 汎用フレームワークとアプリケーション。 0.82
In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 151–159, Atlanta, Georgia, USA, 17–19 Jun 2013. Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, Volume 28 of Proceedings of Machine Learning Research, page 151–159, Atlanta, Georgia, USA, 17–19 Jun 2013 0.88
PMLR.  Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. PMLR。 11] Wei Chen、Yajun Wang、Yang Yuan、およびQinshi Wang。 0.76
Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. 複合多腕バンディットとその確率的トリガーアームへの拡張 0.69
The Journal of Machine Learning Research, 17(1):1746– 1778, 2016. journal of machine learning research, 17(1):1746–1778, 2016年。 0.85
 Richard Combes, リチャード Combes 0.61
Sadegh Shahi, Alexandre Proutiere, Talebi Mazraeh et al. Sadegh Shahi, Alexandre Proutiere, Talebi Mazraeh et al 0.74
Combinatorial bandits revisited. コンビナートバンドが再訪。 0.34
In Advances in Neural Information Processing Systems, pages 2116–2124, 2015. Advanceds in Neural Information Processing Systems, page 2116–2124, 2015 0.77
Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, and marc lelarge. Sadegh Talebi Mazraeh Shahi、Alexandre Proutiere、Marc lelarge。 0.63
Combinatorial bandits revisited. コンビナートバンドが再訪。 0.34
In Advances in Neural Information Processing Systems 28, pages 2116–2124. In Advances in Neural Information Processing Systems 28 page 2116–2124。 0.88
2015. 10  Eyal Even-Dar, Shie Mannor, and Yishay Mansour. 2015. 10  Eyal Even-Dar、Shie Mannor、Yishay Mansour。 0.83
Pac bounds for multi-armed bandit and markov decision processes. 多腕バンディットおよびマルコフ決定過程に対するパックバウンド。 0.60
In International Conference on Computational Learning Theory, pages 255–270. 計算学習理論に関する国際会議」255-270頁。 0.79
Springer, 2002. 2002年、スプリンガー。 0.63
 John J. Forrest, Stefan Vigerske, Haroldo Gambini Santos, Ted Ralphs, Lou Hafer, Bjarni Kristjansson, jpfasano, EdwinStraver, Miles Lubin, rlougee, jpgoncal1, h-i gassmann, and Matthew Saltzman. 15] John J. Forrest, Stefan Vigerske, Haroldo Gambini Santos, Ted Ralphs, Lou Hafer, Bjarni Kristjansson, jpfasano, EdwinStraver, Miles Lubin, rlougee, jpgoncal1, h-i gassmann, Matthew Saltzman。 0.86
coinor/cbc: Version 2.10.5, March 2020. coinor/cbc: Version 2.10.5, March 2020 0.73
 Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Yi Gai、Bhaskar Krishnamachari、Rahul Jain。 0.62
Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation. コグニティブ無線ネットワークにおけるマルチユーザチャネル割り当ての学習:コンビネート型多腕バンディット定式化 0.73
In IEEE Symposium on New Frontiers in Dynamic Spectrum, pages 1–9, 2010. IEEE Symposium on New Frontiers in Dynamic Spectrumで、2010年1-9ページ。 0.83
 Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Yi Gai、Bhaskar Krishnamachari、Rahul Jain。 0.61
Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. 未知変数による組合せネットワーク最適化:線形報酬と個別観測を伴う多腕バンディット。 0.75
IEEE/ACM Transactions on Networking, pages 1466–1478, 2012. IEEE/ACM Transactions on Networking, page 1466–1478, 2012 0.88
 David Haussler. 18] David Haussler (複数形 David Hausslers) 0.60
Probably approximately correct learning. おそらくほぼ正しい学習です。 0.81
University of California, Santa Cruz, Computer Research Laboratory, 1990. カリフォルニア大学サンタクルーズ校、コンピュータ研究所、1990年。 0.64
 Chien-Ju Ho, Shahin Jabbari, and Jennifer Wortman Vaughan. Chien-Ju Ho、Shahin Jabbari、Jennifer Wortman Vaughan。 0.77
In International Conference on Machine Learning, pages 534–542, 2013. 機械学習に関する国際会議で、2013年534-542ページ。 0.77
 Wassily Hoeﬀding. Wassily Hoeffding。 0.74
Probability inequalities for sums of bounded random variables. 有界確率変数の和に対する確率不等式。 0.71
Journal of the American Statistical Association, 58(301):13–30, 1963. Journal of the American Statistical Association, 58(301):13–30, 1963年。 0.90
 Shweta Jain, Satyanath Bhat, Ganesh Ghalme, Divya Padmanabhan, and Y. Narahari.  Shweta Jain、Satyanath Bhat、Ganesh Ghalme、Divya Padmanabhan、Y. Narahari。 0.77
Mechanisms with learning for stochastic multi-armed bandit problems. 確率的マルチアームバンディット問題に対する学習のメカニズム 0.74
Indian Journal of Pure and Applied Mathematics, 47(2):229–272, Jun 2016. Indian Journal of Pure and Applied Mathematics, 47(2):229–272, Jun 2016 0.90
 Shweta Jain, Sujit Gujar, Satyanath Bhat, Onno Zoeter, and Y Narahari. Shweta Jain、Sujit Gujar、Satyanath Bhat、Onno Zoeter、Y Narahari。 0.68
A quality assuring, cost optimal multi-armed bandit mechanism for expertsourcing. エキスパートソーシングのための品質保証・コスト最適多武装バンディット機構 0.63
Artiﬁcial Intelligence, 254:44–63, 2018. 人工知能、254:44-63、2018。 0.52
 David R Karger, Sewoong Oh, and Devavrat Shah. David R Karger、Sewoong Oh、Deavrat Shah。 0.64
Iterative learning for reliable crowdsourcing systems. 信頼できるクラウドソーシングシステムのための反復学習。 0.55
In Advances in neural information processing systems, pages 1953–1961, 2011. 神経情報処理システムの進歩、1953-1961ページ、2011。 0.72
 Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Branislav Kveton, Zheng Wen, Azin Ashkan, Csaba Szepesvari。 0.69
Tight regret bounds for stochastic combinatorial semi-bandits. 確率的組合せ半バンドに対する後悔の束縛。 0.51
In Artiﬁcial Intelligence and Statistics, pages 535–543, 2015. 人工知能と統計』535-543頁、2015年。 0.68
 Jason D Papastavrou, Srikanth Rajagopalan, and Anton J Kleywegt. Jason D Papastavrou、Srikanth Rajagopalan、Anton J Kleywegt。 0.63
The dynamic and stochastic knapsack problem with deadlines. 動的で確率的なknapsack問題と期限の問題。 0.60
Management Science, 42(12):1706–1718, 1996. 経営科学、42(12):1706-1718、1996。 0.71

 Robert P Rooderkerk and Harald J van Heerde.  Robert P RooderkerkとHarald J van Heerde。 0.78
Robust optimization of the 0–1 knapsack problem: Balancing risk and return in assortment optimization. 0-1 ナップサック問題のロバスト最適化: ソートメント最適化におけるリスクとリターンのバランス。 0.67
European Journal of Operational Research, 250(3):842–854, 2016. European Journal of Operational Research, 250(3):842–854, 2016 0.93
 Prabhakant Sinha and Andris A Zoltners. Prabhakant SinhaとAndris A Zoltners。 0.77
The multiple-choice knapsack problem. 多重選択knapsack問題。 0.59
Operations Research, 27(3):503–515, 1979. 運用調査, 27(3):503–515, 1979。 0.81
 Aleksandrs Slivkins.  Aleksandrs Slivkins。 0.79
Introduction to multi-armed Foundations and Trends® in Machine 機械における多武装ファウンデーションとトレンド®の紹介 0.65
bandits. Learning, 2019. 盗賊だ 2019年、学習。 0.68
 Mil´e Terziovski, Danny Samson, and Douglas Dow. Mil ́e Terziovski, Danny Samson, Douglas Dow。 0.57
The business value of quality management systems certiﬁcation. 品質管理システムの認証のビジネス価値。 0.71
evidence from australia and new zealand. オーストラリアとニュージーランドの証拠です 0.61
Journal of operations management, 15(1):1– 18, 1997. journal of operations management, 15(1):1–18, 1997を参照。 0.78
 William R Thompson. ウィリアム・R・トンプソン(William R Thompson) 0.64
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. 2つのサンプルの証拠の観点から、未知の確率が別の確率を超える可能性について。

0.78
Biometrika, 25(3/4):285– 294, 1933. Biometrika、25(3/4):285–294、1933。 0.78
 Long Tran-Thanh, Sebastian Stein, Alex Rogers, and Nicholas R Jennings. 31] Long Tran-Thanh、Sebastian Stein、Alex Rogers、Nicholas R Jennings。 0.72
Eﬃcient crowdsourcing of unknown experts using bounded multi-armed bandits. 有界多腕包帯を用いた未知の専門家の効率的なクラウドソーシング 0.45
Artiﬁcial Intelligence, 214:89–111, 2014. 人工知能、214:89-111 2014年。 0.53
 Long Tran-Thanh, Matteo Venanzi, Alex Rogers, and Nicholas R Jennings. 32] Long Tran-Thanh、Matteo Venanzi、Alex Rogers、Nicholas R Jennings。 0.70
Eﬃcient budget allocation with accuracy guarantees for crowdsourcing classiﬁcation tasks. クラウドソーシング分類タスクの精度を保証する効率的な予算割り当て。 0.71
In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pages 901–908. 2013年の自律エージェントとマルチエージェントシステムに関する国際会議Proceedingsにおいて、901-908ページ。 0.70
International Foundation for Autonomous Agents and Multiagent Systems, 2013. International Foundation for Autonomous Agents and Multiagent Systems, 2013 (英語) 0.92
 GJ Zaimai. GJザイマイ。 0.67
Optimality conditions and duality for constrained measurable subset selection problems with minmax objective functions. minmax 客観的関数による測定可能なサブセット選択問題の最適条件と双対性 0.88
Optimization, 20(4):377–395, 1989. 最適化, 20(4):377–395, 1989。 0.77
11 11 0.85
ページの最初に戻る