Asymptotic optimality of myopic ranking and selection procedures
Ranking and selection (R&S) is a popular model for studying discrete-event dynamic systems. It aims to select the best design (the design with the largest mean performance) from a finite set, where the mean of each design is unknown and has to be learned by samples. Great research efforts have b...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/170583 |
| _version_ | 1811686002985533440 |
|---|---|
| author | Li, Yanwen Gao, Siyan Shi, Tony Z. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Li, Yanwen Gao, Siyan Shi, Tony Z. |
| author_sort | Li, Yanwen |
| collection | NTU |
| description | Ranking and selection (R&S) is a popular model for studying discrete-event dynamic systems. It aims to select the best design (the design with the largest mean performance) from a finite set, where the mean of each design is unknown and has to be learned by samples. Great research efforts have been devoted to this problem in the literature for developing procedures with superior empirical performance and showing their optimality. In these efforts, myopic procedures were popular. They select the best design using a “naive” mechanism of iteratively and myopically improving an approximation of the objective measure. Although they are based on simple heuristics and lack theoretical support, they turned out highly effective, and often achieved competitive empirical performance compared to procedures that were proposed later and shown to be asymptotically optimal. In this paper, we theoretically analyze these myopic procedures and prove that they also satisfy the optimality conditions of R&S, just like some other popular R&S methods. It explains the good performance of myopic procedures in various numerical tests, and provides good insight into the structure and theoretical development of efficient R&S procedures. |
| first_indexed | 2024-10-01T04:53:30Z |
| format | Journal Article |
| id | ntu-10356/170583 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:53:30Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1705832023-09-19T23:38:20Z Asymptotic optimality of myopic ranking and selection procedures Li, Yanwen Gao, Siyan Shi, Tony Z. School of Physical and Mathematical Sciences Science::Mathematics Ranking and Selection Myopic Procedure Ranking and selection (R&S) is a popular model for studying discrete-event dynamic systems. It aims to select the best design (the design with the largest mean performance) from a finite set, where the mean of each design is unknown and has to be learned by samples. Great research efforts have been devoted to this problem in the literature for developing procedures with superior empirical performance and showing their optimality. In these efforts, myopic procedures were popular. They select the best design using a “naive” mechanism of iteratively and myopically improving an approximation of the objective measure. Although they are based on simple heuristics and lack theoretical support, they turned out highly effective, and often achieved competitive empirical performance compared to procedures that were proposed later and shown to be asymptotically optimal. In this paper, we theoretically analyze these myopic procedures and prove that they also satisfy the optimality conditions of R&S, just like some other popular R&S methods. It explains the good performance of myopic procedures in various numerical tests, and provides good insight into the structure and theoretical development of efficient R&S procedures. This research was supported in part by City University of Hong Kong (Grants 7005269 and 7005568 ). 2023-09-19T23:38:20Z 2023-09-19T23:38:20Z 2023 Journal Article Li, Y., Gao, S. & Shi, T. Z. (2023). Asymptotic optimality of myopic ranking and selection procedures. Automatica, 151, 110896-. https://dx.doi.org/10.1016/j.automatica.2023.110896 0005-1098 https://hdl.handle.net/10356/170583 10.1016/j.automatica.2023.110896 2-s2.0-85147961923 151 110896 en Automatica © 2023 Elsevier Ltd. All rights reserved. |
| spellingShingle | Science::Mathematics Ranking and Selection Myopic Procedure Li, Yanwen Gao, Siyan Shi, Tony Z. Asymptotic optimality of myopic ranking and selection procedures |
| title | Asymptotic optimality of myopic ranking and selection procedures |
| title_full | Asymptotic optimality of myopic ranking and selection procedures |
| title_fullStr | Asymptotic optimality of myopic ranking and selection procedures |
| title_full_unstemmed | Asymptotic optimality of myopic ranking and selection procedures |
| title_short | Asymptotic optimality of myopic ranking and selection procedures |
| title_sort | asymptotic optimality of myopic ranking and selection procedures |
| topic | Science::Mathematics Ranking and Selection Myopic Procedure |
| url | https://hdl.handle.net/10356/170583 |
| work_keys_str_mv | AT liyanwen asymptoticoptimalityofmyopicrankingandselectionprocedures AT gaosiyan asymptoticoptimalityofmyopicrankingandselectionprocedures AT shitonyz asymptoticoptimalityofmyopicrankingandselectionprocedures |