Annealing-pareto multi-objective multi-armed bandit algorithm

S.Q. Yahyaa; M.M. Drugan; B. Manderick

doi:10.1109/ADPRL.2014.7010619

Annealing-pareto multi-objective multi-armed bandit algorithm

S.Q. Yahyaa, M.M. Drugan, B. Manderick

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

15 Citations (Scopus)

Abstract

In the stochastic multi-objective multi-armed bandit (or MOMAB), arms generate a vector of stochastic rewards, one per objective, instead of a single scalar reward. As a result, there is not only one optimal arm, but there is a set of optimal arms (Pareto front) of reward vectors using the Pareto dominance relation and there is a trade-off between finding the optimal arm set (exploration) and selecting fairly or evenly the optimal arms (exploitation). To trade-off between exploration and exploitation, either Pareto knowledge gradient (or Pareto-KG for short), or Pareto upper confidence bound (or Pareto-UCB1 for short) can be used. They combine the KG-policy and UCB1-policy respectively with the Pareto dominance relation. In this paper, we propose Pareto Thompson sampling that uses Pareto dominance relation to find the Pareto front. We also propose annealing-Pareto algorithm that trades-off between the exploration and exploitation by using a decaying parameter _t in combination with Pareto dominance relation. The annealing-Pareto algorithm uses the decaying parameter to explore the Pareto optimal arms and uses Pareto dominance relation to exploit the Pareto front. We experimentally compare Pareto-KG, Pareto-UCB1, Pareto Thompson sampling and the annealing-Pareto algorithms on multi-objective Bernoulli distribution problems and we conclude that the annealing-Pareto is the best performing algorithm.

Original language	English
Title of host publication	IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Pages	1-3
ISBN (Print)	9781479945535
DOIs	https://doi.org/10.1109/ADPRL.2014.7010619
Publication status	Published - 14 Jan 2015
Externally published	Yes
Event	2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL 2014) - Orlando, United States Duration: 9 Dec 2014 → 12 Dec 2014

Conference

Conference	2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL 2014)
Abbreviated title	ADPRL 2014
Country/Territory	United States
City	Orlando
Period	9/12/14 → 12/12/14

Access to Document

10.1109/ADPRL.2014.7010619

Cite this

Yahyaa, S. Q., Drugan, M. M., & Manderick, B. (2015). Annealing-pareto multi-objective multi-armed bandit algorithm. In IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida (pp. 1-3). Article 7010619 Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ADPRL.2014.7010619

Yahyaa, S.Q. ; Drugan, M.M. ; Manderick, B. / Annealing-pareto multi-objective multi-armed bandit algorithm. IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida. Piscataway : Institute of Electrical and Electronics Engineers, 2015. pp. 1-3

@inproceedings{dfd84edb20d54d49ab9fdb8246edb629,

title = "Annealing-pareto multi-objective multi-armed bandit algorithm",

abstract = "In the stochastic multi-objective multi-armed bandit (or MOMAB), arms generate a vector of stochastic rewards, one per objective, instead of a single scalar reward. As a result, there is not only one optimal arm, but there is a set of optimal arms (Pareto front) of reward vectors using the Pareto dominance relation and there is a trade-off between finding the optimal arm set (exploration) and selecting fairly or evenly the optimal arms (exploitation). To trade-off between exploration and exploitation, either Pareto knowledge gradient (or Pareto-KG for short), or Pareto upper confidence bound (or Pareto-UCB1 for short) can be used. They combine the KG-policy and UCB1-policy respectively with the Pareto dominance relation. In this paper, we propose Pareto Thompson sampling that uses Pareto dominance relation to find the Pareto front. We also propose annealing-Pareto algorithm that trades-off between the exploration and exploitation by using a decaying parameter t in combination with Pareto dominance relation. The annealing-Pareto algorithm uses the decaying parameter to explore the Pareto optimal arms and uses Pareto dominance relation to exploit the Pareto front. We experimentally compare Pareto-KG, Pareto-UCB1, Pareto Thompson sampling and the annealing-Pareto algorithms on multi-objective Bernoulli distribution problems and we conclude that the annealing-Pareto is the best performing algorithm.",

author = "S.Q. Yahyaa and M.M. Drugan and B. Manderick",

year = "2015",

month = jan,

day = "14",

doi = "10.1109/ADPRL.2014.7010619",

language = "English",

isbn = "9781479945535",

pages = "1--3",

booktitle = "IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL 2014), ADPRL 2014 ; Conference date: 09-12-2014 Through 12-12-2014",

}

Yahyaa, SQ, Drugan, MM & Manderick, B 2015, Annealing-pareto multi-objective multi-armed bandit algorithm. in IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida., 7010619, Institute of Electrical and Electronics Engineers, Piscataway, pp. 1-3, 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL 2014), Orlando, Florida, United States, 9/12/14. https://doi.org/10.1109/ADPRL.2014.7010619

Annealing-pareto multi-objective multi-armed bandit algorithm. / Yahyaa, S.Q.; Drugan, M.M.; Manderick, B.
IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida. Piscataway: Institute of Electrical and Electronics Engineers, 2015. p. 1-3 7010619.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Annealing-pareto multi-objective multi-armed bandit algorithm

AU - Yahyaa, S.Q.

AU - Drugan, M.M.

AU - Manderick, B.

PY - 2015/1/14

Y1 - 2015/1/14

N2 - In the stochastic multi-objective multi-armed bandit (or MOMAB), arms generate a vector of stochastic rewards, one per objective, instead of a single scalar reward. As a result, there is not only one optimal arm, but there is a set of optimal arms (Pareto front) of reward vectors using the Pareto dominance relation and there is a trade-off between finding the optimal arm set (exploration) and selecting fairly or evenly the optimal arms (exploitation). To trade-off between exploration and exploitation, either Pareto knowledge gradient (or Pareto-KG for short), or Pareto upper confidence bound (or Pareto-UCB1 for short) can be used. They combine the KG-policy and UCB1-policy respectively with the Pareto dominance relation. In this paper, we propose Pareto Thompson sampling that uses Pareto dominance relation to find the Pareto front. We also propose annealing-Pareto algorithm that trades-off between the exploration and exploitation by using a decaying parameter t in combination with Pareto dominance relation. The annealing-Pareto algorithm uses the decaying parameter to explore the Pareto optimal arms and uses Pareto dominance relation to exploit the Pareto front. We experimentally compare Pareto-KG, Pareto-UCB1, Pareto Thompson sampling and the annealing-Pareto algorithms on multi-objective Bernoulli distribution problems and we conclude that the annealing-Pareto is the best performing algorithm.

AB - In the stochastic multi-objective multi-armed bandit (or MOMAB), arms generate a vector of stochastic rewards, one per objective, instead of a single scalar reward. As a result, there is not only one optimal arm, but there is a set of optimal arms (Pareto front) of reward vectors using the Pareto dominance relation and there is a trade-off between finding the optimal arm set (exploration) and selecting fairly or evenly the optimal arms (exploitation). To trade-off between exploration and exploitation, either Pareto knowledge gradient (or Pareto-KG for short), or Pareto upper confidence bound (or Pareto-UCB1 for short) can be used. They combine the KG-policy and UCB1-policy respectively with the Pareto dominance relation. In this paper, we propose Pareto Thompson sampling that uses Pareto dominance relation to find the Pareto front. We also propose annealing-Pareto algorithm that trades-off between the exploration and exploitation by using a decaying parameter t in combination with Pareto dominance relation. The annealing-Pareto algorithm uses the decaying parameter to explore the Pareto optimal arms and uses Pareto dominance relation to exploit the Pareto front. We experimentally compare Pareto-KG, Pareto-UCB1, Pareto Thompson sampling and the annealing-Pareto algorithms on multi-objective Bernoulli distribution problems and we conclude that the annealing-Pareto is the best performing algorithm.

UR - http://www.scopus.com/inward/record.url?scp=84925067907&partnerID=8YFLogxK

U2 - 10.1109/ADPRL.2014.7010619

DO - 10.1109/ADPRL.2014.7010619

M3 - Conference contribution

SN - 9781479945535

SP - 1

EP - 3

BT - IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

T2 - 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL 2014)

Y2 - 9 December 2014 through 12 December 2014

ER -

Yahyaa SQ, Drugan MM, Manderick B. Annealing-pareto multi-objective multi-armed bandit algorithm. In IEEE SSCI 2014 - 2014 IEEE Symposium Series on Computational Intelligence - ADPRL 2014: 2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, 9-12 December 2014, Orlando, Florida. Piscataway: Institute of Electrical and Electronics Engineers. 2015. p. 1-3. 7010619 doi: 10.1109/ADPRL.2014.7010619

Annealing-pareto multi-objective multi-armed bandit algorithm

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this