Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well

Özgür Şimşek, Simón Algorta, Amit Kothiyal

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

We examined the sequence of decision problems that are encountered in the game of Tetris and found that most of the problems are easy in the following sense: One can choose well among the available actions without knowing an evaluation function that scores well in the game. This is a consequence of three conditions that are prevalent in the game: simple dominance, cumulative dominance, and noncompensation. These conditions can be exploited to develop faster and more effective learning algorithms. In addition, they allow certain types of domain knowledge to be incorporated with ease into a learning algorithm. Among the sequential decision problems we encounter, it is unlikely that Tetris is unique or rare in having these properties.
LanguageEnglish
Title of host publicationProceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016
EditorsMaria-Florina Balcan, Kilian Q. Weinberger
Pages1757-1765
Number of pages9
StatusPublished - 2016

Publication series

NameJMLR Workshop and Conference Proceedings
PublisherJMLR.org
Volume48

Fingerprint

Learning algorithms
Function evaluation

Keywords

  • sequential decision making; reinforcement learning; statistical structure of decision environments

Cite this

Şimşek, Ö., Algorta, S., & Kothiyal, A. (2016). Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well. In M-F. Balcan, & K. Q. Weinberger (Eds.), Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016 (pp. 1757-1765). (JMLR Workshop and Conference Proceedings; Vol. 48).

Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well. / Şimşek, Özgür; Algorta, Simón; Kothiyal, Amit.

Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016. ed. / Maria-Florina Balcan; Kilian Q. Weinberger. 2016. p. 1757-1765 (JMLR Workshop and Conference Proceedings; Vol. 48).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Şimşek, Ö, Algorta, S & Kothiyal, A 2016, Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well. in M-F Balcan & KQ Weinberger (eds), Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016. JMLR Workshop and Conference Proceedings, vol. 48, pp. 1757-1765.
Şimşek Ö, Algorta S, Kothiyal A. Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well. In Balcan M-F, Weinberger KQ, editors, Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016. 2016. p. 1757-1765. (JMLR Workshop and Conference Proceedings).
Şimşek, Özgür ; Algorta, Simón ; Kothiyal, Amit. / Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well. Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016. editor / Maria-Florina Balcan ; Kilian Q. Weinberger. 2016. pp. 1757-1765 (JMLR Workshop and Conference Proceedings).
@inbook{162790aaba984ff7b8469cb232785175,
title = "Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well",
abstract = "We examined the sequence of decision problems that are encountered in the game of Tetris and found that most of the problems are easy in the following sense: One can choose well among the available actions without knowing an evaluation function that scores well in the game. This is a consequence of three conditions that are prevalent in the game: simple dominance, cumulative dominance, and noncompensation. These conditions can be exploited to develop faster and more effective learning algorithms. In addition, they allow certain types of domain knowledge to be incorporated with ease into a learning algorithm. Among the sequential decision problems we encounter, it is unlikely that Tetris is unique or rare in having these properties.",
keywords = "sequential decision making; reinforcement learning; statistical structure of decision environments",
author = "{\"O}zg{\"u}r Şimşek and Sim{\'o}n Algorta and Amit Kothiyal",
year = "2016",
language = "English",
series = "JMLR Workshop and Conference Proceedings",
publisher = "JMLR.org",
pages = "1757--1765",
editor = "Maria-Florina Balcan and Weinberger, {Kilian Q. }",
booktitle = "Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016",

}

TY - CHAP

T1 - Why most decisions are easy in Tetris—And perhaps in other sequential decision problems, as well

AU - Şimşek,Özgür

AU - Algorta,Simón

AU - Kothiyal,Amit

PY - 2016

Y1 - 2016

N2 - We examined the sequence of decision problems that are encountered in the game of Tetris and found that most of the problems are easy in the following sense: One can choose well among the available actions without knowing an evaluation function that scores well in the game. This is a consequence of three conditions that are prevalent in the game: simple dominance, cumulative dominance, and noncompensation. These conditions can be exploited to develop faster and more effective learning algorithms. In addition, they allow certain types of domain knowledge to be incorporated with ease into a learning algorithm. Among the sequential decision problems we encounter, it is unlikely that Tetris is unique or rare in having these properties.

AB - We examined the sequence of decision problems that are encountered in the game of Tetris and found that most of the problems are easy in the following sense: One can choose well among the available actions without knowing an evaluation function that scores well in the game. This is a consequence of three conditions that are prevalent in the game: simple dominance, cumulative dominance, and noncompensation. These conditions can be exploited to develop faster and more effective learning algorithms. In addition, they allow certain types of domain knowledge to be incorporated with ease into a learning algorithm. Among the sequential decision problems we encounter, it is unlikely that Tetris is unique or rare in having these properties.

KW - sequential decision making; reinforcement learning; statistical structure of decision environments

UR - http://proceedings.mlr.press/v48/simsek16.html

M3 - Chapter

T3 - JMLR Workshop and Conference Proceedings

SP - 1757

EP - 1765

BT - Proceedings of the 33nd International Conference on Machine Learning (ICML 2016), New York City, NY, USA, June 19-24, 2016

ER -

Access to Document