Constrained no-regret learning

Ye Du and Ehud Lehrer

Journal of Mathematical Economics, 2020, vol. 88, issue C, 16-24

Abstract: We investigate a dynamic decision making problem with constraints. The decision maker is free to take any action as long as the empirical frequency of the actions played does not violate pre-specified constraints. In a case of violation the decision maker is penalized. We introduce the constrained no-regret learning model. In this model the set of alternative strategies, with which a dynamic decision policy is compared, is the set of stationary mixed actions that satisfy all the constraints. We show that there exists a strategy that satisfies the following properties: (i) it guarantees that after an unavoidable deterministic grace period, there are absolutely no violations; (ii) for an arbitrarily small constant ϵ>0, it achieves a convergence rate of T−1−ϵ2, which improves the O(T−13) convergence rate of Mannor et al. (2009).

Keywords: No-regret strategy; Approachability; Constrained no-regret; On-line learning algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2) Track citations by RSS feed

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304406820300197
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:mateco:v:88:y:2020:i:c:p:16-24

DOI: 10.1016/j.jmateco.2020.02.002

Access Statistics for this article

Journal of Mathematical Economics is currently edited by Atsushi (A.) Kajii

More articles in Journal of Mathematical Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().