Better rates for any adversarial deterministic MDP

Ofer Dekel; Elad Hazan

Better rates for any adversarial deterministic MDP

Research output: Contribution to conference › Paper › peer-review

Abstract

We consider regret minimization in adversarial deterministic Markov Decision Processes (ADMDPs) with bandit feedback. We devise a new algorithm that pushes the state-of-the-art forward in two ways: First, it attains a regret of O(T^2/3) with respect to the best fixed policy in hindsight, whereas the previous best regret bound was O(T^3/4). Second, the algorithm and its analysis are compatible with any feasible ADMDP graph topology, while all previous approaches required additional restrictions on the graph topology.

Original language	English (US)
Pages	1712-1720
Number of pages	9
State	Published - 2013
Externally published	Yes
Event	30th International Conference on Machine Learning, ICML 2013 - Atlanta, GA, United States Duration: Jun 16 2013 → Jun 21 2013

Other

Other	30th International Conference on Machine Learning, ICML 2013
Country/Territory	United States
City	Atlanta, GA
Period	6/16/13 → 6/21/13

All Science Journal Classification (ASJC) codes

Human-Computer Interaction
Sociology and Political Science

Cite this

@conference{84f2c22e40074fe8bf9ab1988d46e711,

title = "Better rates for any adversarial deterministic MDP",

abstract = "We consider regret minimization in adversarial deterministic Markov Decision Processes (ADMDPs) with bandit feedback. We devise a new algorithm that pushes the state-of-the-art forward in two ways: First, it attains a regret of O(T2/3) with respect to the best fixed policy in hindsight, whereas the previous best regret bound was O(T3/4). Second, the algorithm and its analysis are compatible with any feasible ADMDP graph topology, while all previous approaches required additional restrictions on the graph topology.",

author = "Ofer Dekel and Elad Hazan",

year = "2013",

language = "English (US)",

pages = "1712--1720",

note = "30th International Conference on Machine Learning, ICML 2013 ; Conference date: 16-06-2013 Through 21-06-2013",

}

TY - CONF

T1 - Better rates for any adversarial deterministic MDP

AU - Dekel, Ofer

AU - Hazan, Elad

PY - 2013

Y1 - 2013

N2 - We consider regret minimization in adversarial deterministic Markov Decision Processes (ADMDPs) with bandit feedback. We devise a new algorithm that pushes the state-of-the-art forward in two ways: First, it attains a regret of O(T2/3) with respect to the best fixed policy in hindsight, whereas the previous best regret bound was O(T3/4). Second, the algorithm and its analysis are compatible with any feasible ADMDP graph topology, while all previous approaches required additional restrictions on the graph topology.

AB - We consider regret minimization in adversarial deterministic Markov Decision Processes (ADMDPs) with bandit feedback. We devise a new algorithm that pushes the state-of-the-art forward in two ways: First, it attains a regret of O(T2/3) with respect to the best fixed policy in hindsight, whereas the previous best regret bound was O(T3/4). Second, the algorithm and its analysis are compatible with any feasible ADMDP graph topology, while all previous approaches required additional restrictions on the graph topology.

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

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

M3 - Paper

AN - SCOPUS:84897554269

SP - 1712

EP - 1720

T2 - 30th International Conference on Machine Learning, ICML 2013

Y2 - 16 June 2013 through 21 June 2013

ER -

Better rates for any adversarial deterministic MDP

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this