Change search
Link to record
Permanent link

Direct link
BETA
Proutiere, Alexandre
Publications (10 of 13) Show all publications
Combes, R., Ok, J., Proutiere, A., Yun, D. & Yi, Y. (2019). Optimal Rate Sampling in 802.11 Systems: Theory, Design, and Implementation. IEEE Transactions on Mobile Computing, 18(5), 1145-1158
Open this publication in new window or tab >>Optimal Rate Sampling in 802.11 Systems: Theory, Design, and Implementation
Show others...
2019 (English)In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 18, no 5, p. 1145-1158Article in journal (Refereed) Published
Abstract [en]

Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems. It allows transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radio channel conditions, to learn and track the (mode, rate) pair providing the highest throughput. The design of RA mechanisms has been mainly driven by heuristics. In contrast, we rigorously formulate RA as an online stochastic optimization problem. We solve this problem and present G-ORS (Graphical Optimal Rate Sampling), a family of provably optimal (mode, rate) pair adaptation algorithms. Our main result is that G-ORS outperforms state-of-the-art algorithms such as MiRA and Minstrel HT as demonstrated by experiments on a 802.11n network test-bed. The design of G-ORS is supported by a theoretical analysis, where we study its performance in stationary radio environments where the successful packet transmission probabilities at the various (mode, rate) pairs do not vary over time, and in non-stationary environments where these probabilities evolve. We show that under G-ORS, the throughput loss due to the need to explore sub-optimal (mode, rate) pairs does not depend on the number of available pairs. This is a crucial advantage as evolving 802.11 standards offer an increasingly large number of (mode, rate) pairs. We illustrate the superiority of G-ORS over state-of-the-art algorithms, using both trace-driven simulations and test-bed experiments.

Place, publisher, year, edition, pages
IEEE COMPUTER SOC, 2019
Keywords
Rate adaptation, multi-armed bandits, 802.11, test-bed
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-252394 (URN)10.1109/TMC.2018.2854758 (DOI)000467071000012 ()2-s2.0-85049850809 (Scopus ID)
Note

QC 20190718

Available from: 2019-07-18 Created: 2019-07-18 Last updated: 2019-07-18Bibliographically approved
Talak, R., Manjunath, D. & Proutiere, A. (2019). Strategic arrivals to queues offering priority service. Queueing systems, 92(1-2), 103-130
Open this publication in new window or tab >>Strategic arrivals to queues offering priority service
2019 (English)In: Queueing systems, ISSN 0257-0130, E-ISSN 1572-9443, Vol. 92, no 1-2, p. 103-130Article in journal (Refereed) Published
Abstract [en]

We consider strategic arrivals to a FCFS service system that starts service at a fixed time and has to serve a fixed number of customers, for example, an airplane boarding system. Arriving early induces a higher waiting cost (waiting before service begins) while arriving late induces a cost because earlier arrivals take the better seats. We first consider arrivals of heterogenous customers that choose arrival times to minimize the weighted sum of waiting cost and cost due to expected number of predecessors. We characterize the unique Nash equilibria for this system. Next, we consider a system offering L levels of priority service with a FCFS queue for each priority level. Higher priorities are charged higher admission prices. Customers make two choicestime of arrival and priority of service. We show that the Nash equilibrium corresponds to the customer types being divided into L intervals and customers belonging to each interval choosing the same priority level. We further analyze the net revenue to the server and consider revenue maximizing strategiesnumber of priority levels and pricing. Numerical results show that with only a small number of queues (two or three) the server can obtain nearly the maximum revenue.

Place, publisher, year, edition, pages
Springer, 2019
Keywords
Games in queues, Strategic arrivals, Priority queues, Pricing, Service differentiation
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:kth:diva-251695 (URN)10.1007/s11134-019-09604-3 (DOI)000466925200005 ()2-s2.0-85065221593 (Scopus ID)
Note

QC 20190520

Available from: 2019-05-20 Created: 2019-05-20 Last updated: 2019-05-29Bibliographically approved
Li, B., Wu, J., Qi, H., Proutiere, A. & Shi, G. (2018). Boolean Gossip Networks. IEEE/ACM Transactions on Networking, 26(1), 118-130
Open this publication in new window or tab >>Boolean Gossip Networks
Show others...
2018 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. 26, no 1, p. 118-130Article in journal (Refereed) Published
Abstract [en]

This paper proposes and investigates a Boolean gossip model as a simplified but non-trivial probabilistic Boolean network. With positive node interactions, in view of standard theories from Markov chains, we prove that the node states asymptotically converge to an agreement at a binary random variable, whose distribution is characterized for large-scale networks by mean-field approximation. Using combinatorial analysis, we also successfully count the number of communication classes of the positive Boolean network explicitly in terms of the topology of the underlying interaction graph, where remarkably minor variation in local structures can drastically change the number of network communication classes. With general Boolean interaction rules, emergence of absorbing network Boolean dynamics is shown to be determined by the network structure with necessary and sufficient conditions established regarding when the Boolean gossip process defines absorbing Markov chains. Particularly, it is shown that for the majority of the Boolean interaction rules, except for nine out of the total 2(16) - 1 possible nonempty sets of binary Boolean functions, whether the induced chain is absorbing has nothing to do with the topology of the underlying interaction graph, as long as connectivity is assumed. These results illustrate the possibilities of relating dynamical properties of Boolean networks to graphical properties of the underlying interactions.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2018
Keywords
Boolean networks, gossiping process, Markov chains, communication classes
National Category
Probability Theory and Statistics Computer Sciences
Identifiers
urn:nbn:se:kth:diva-224042 (URN)10.1109/TNET.2017.2763964 (DOI)000425324000009 ()2-s2.0-85032838465 (Scopus ID)
Note

QC 20180320

Available from: 2018-03-20 Created: 2018-03-20 Last updated: 2018-03-20Bibliographically approved
Ok, J., Proutiere, A. & Tranos, D. (2018). Exploration in Structured Reinforcement Learning. In: Bengio, S Wallach, H Larochelle, H Grauman, K CesaBianchi, N Garnett, R (Ed.), Advances In Neural Information Processing Systems 31 (NIPS 2018): . Paper presented at 32nd Conference on Neural Information Processing Systems (NIPS), DEC 02-08, 2018, Montreal, CANADA. Neural Information Processing Systems (NIPS), 31
Open this publication in new window or tab >>Exploration in Structured Reinforcement Learning
2018 (English)In: Advances In Neural Information Processing Systems 31 (NIPS 2018) / [ed] Bengio, S Wallach, H Larochelle, H Grauman, K CesaBianchi, N Garnett, R, Neural Information Processing Systems (NIPS) , 2018, Vol. 31Conference paper, Published paper (Refereed)
Abstract [en]

We address reinforcement learning problems with finite state and action spaces where the underlying MDP has some known structure that could be potentially exploited to minimize the exploration rates of suboptimal (state, action) pairs. For any arbitrary structure, we derive problem-specific regret lower bounds satisfied by any learning algorithm. These lower bounds are made explicit for unstructured MDPs and for those whose transition probabilities and average reward functions are Lipschitz continuous w.r.t. the state and action. For Lipschitz MDPs, the bounds are shown not to scale with the sizes S and A of the state and action spaces, i.e., they are smaller than c log T where T is the time horizon and the constant c only depends on the Lipschitz structure, the span of the bias function, and the minimal action sub-optimality gap. This contrasts with unstructured MDPs where the regret lower bound typically scales as SA log T. We devise DEL (Directed Exploration Learning), an algorithm that matches our regret lower bounds. We further simplify the algorithm for Lipschitz MDPs, and show that the simplified version is still able to efficiently exploit the structure.

Place, publisher, year, edition, pages
Neural Information Processing Systems (NIPS), 2018
Series
Advances in Neural Information Processing Systems, ISSN 1049-5258 ; 31
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-249916 (URN)000461852003043 ()2-s2.0-85064810437 (Scopus ID)
Conference
32nd Conference on Neural Information Processing Systems (NIPS), DEC 02-08, 2018, Montreal, CANADA
Note

QC 20190425. QC 20191023

Available from: 2019-04-25 Created: 2019-04-25 Last updated: 2019-10-23Bibliographically approved
Combes, R., Magureanu, S. & Proutiere, A. (2018). Generic Asymptotically Optimal Algorithms for Multi-Armed Bandits. In: 2018 56TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON): . Paper presented at 56th Annual Allerton Conference on Communication, Control, and Computing llerton), OCT 02-05, 2018, Monticello, IL (pp. 235-241). IEEE
Open this publication in new window or tab >>Generic Asymptotically Optimal Algorithms for Multi-Armed Bandits
2018 (English)In: 2018 56TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), IEEE , 2018, p. 235-241Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE, 2018
Series
Annual Allerton Conference on Communication Control and Computing, ISSN 2474-0195
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-248119 (URN)000461021200021 ()978-1-5386-6596-1 (ISBN)
Conference
56th Annual Allerton Conference on Communication, Control, and Computing llerton), OCT 02-05, 2018, Monticello, IL
Note

QC 20190412

Available from: 2019-04-12 Created: 2019-04-12 Last updated: 2019-09-25Bibliographically approved
Yun, D., Ahn, S., Proutiere, A., Shin, J. & Yi, Y. (2018). Multi-armed bandit with additional observations. In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems: . Paper presented at 2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018, Beckman CenterIrvine, United States, 18 June 2018 through 22 June 2018 (pp. 53-55). Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Multi-armed bandit with additional observations
Show others...
2018 (English)In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2018, p. 53-55Conference paper, Published paper (Refereed)
Abstract [en]

We study multi-armed bandit (MAB) problems with additional observations, where in each round, the decision maker selects an arm to play and can also observe rewards of additional arms (within a given budget) by paying certain costs. We propose algorithms that are asymptotic-optimal and order-optimal in their regrets under the settings of stochastic and adversarial rewards, respectively.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2018
Keywords
Additional Observations, INF, KL-UCB, Multi-armed Bandit
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-234118 (URN)10.1145/3219617.3219639 (DOI)2-s2.0-85052012891 (Scopus ID)9781450358460 (ISBN)
Conference
2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018, Beckman CenterIrvine, United States, 18 June 2018 through 22 June 2018
Note

QC 20180905

Available from: 2018-09-05 Created: 2018-09-05 Last updated: 2018-09-05Bibliographically approved
Magureanu, S., Isaksson, M., Proutiere, A. & Zhang, B. (2018). Online learning of optimally diverse rankings. In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems: . Paper presented at 2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018, Beckman Center, Irvine, United States, 18 June 2018 through 22 June 2018 (pp. 47-49). Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Online learning of optimally diverse rankings
2018 (English)In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2018, p. 47-49Conference paper, Published paper (Refereed)
Abstract [en]

Search engines answer users’ queries by listing relevant items (e.g. documents, songs, products, web pages, ...). These engines rely on algorithms that learn to rank items so as to present an ordered list maximizing the probability that it contains relevant item. The main challenge in the design of learning-to-rank algorithms stems from the fact that queries often have different meanings for different users. In absence of any contextual information about the query, one often has to adhere to the diversity principle, i.e., to return a list covering the various possible topics or meanings of the query. To formalize this learning-to-rank problem, we propose a natural model where (i) items are categorized into topics, (ii) users find items relevant only if they match the topic of their query, and (iii) the engine is not aware of the topic of an arriving query, nor of the frequency at which queries related to various topics arrive, nor of the topic-dependent click-through-rates of the items. For this problem, we devise LDR (Learning Diverse Rankings), an algorithm that efficiently learns the optimal list based on users’ feedback only. We show that after T queries, the regret of LDR scales as O((N - L) log(T)) where N is the number of all items. This scaling cannot be improved, i.e., LDR is order optimal.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2018
Keywords
Diversity, Learning to rank, Multi-armed bandits, Online learning
National Category
Other Computer and Information Science
Identifiers
urn:nbn:se:kth:diva-234117 (URN)10.1145/3219617.3219637 (DOI)2-s2.0-85052016103 (Scopus ID)9781450358460 (ISBN)
Conference
2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018, Beckman Center, Irvine, United States, 18 June 2018 through 22 June 2018
Note

QC 20180903

Available from: 2018-09-03 Created: 2018-09-03 Last updated: 2018-09-03Bibliographically approved
Talebi Mazraeh Shahi, M. S., Zou, Z., Combes, R., Proutiere, A. & Johansson, M. (2018). Stochastic Online Shortest Path Routing: The Value of Feedback. IEEE Transactions on Automatic Control, 63(4), 915-930
Open this publication in new window or tab >>Stochastic Online Shortest Path Routing: The Value of Feedback
Show others...
2018 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 63, no 4, p. 915-930Article in journal (Refereed) Published
Abstract [en]

This paper studies online shortest path routing over multihop networks. Link costs or delays are time varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. Three algorithms, with a tradeoff between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms. We also assess numerically the performance of the proposed algorithms and compare it to that of existing algorithms.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Keywords
Online combinatorial optimization, shortest path routing, stochastic multiarmed bandits (MAB)
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-228142 (URN)10.1109/TAC.2017.2747409 (DOI)000429056000001 ()2-s2.0-85028716123 (Scopus ID)
Note

QC 20180518

Available from: 2018-05-18 Created: 2018-05-18 Last updated: 2018-05-23Bibliographically approved
Müller, M. I., Valenzuela, P. E., Proutiere, A. & Rojas, C. R. (2017). A stochastic multi-armed bandit approach to nonparametric H∞-norm estimation. In: 56th IEEE Conference on Decision and Control: . Paper presented at 56th IEEE Conference on Decision and Control (pp. 4632-4637). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>A stochastic multi-armed bandit approach to nonparametric H-norm estimation
2017 (English)In: 56th IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 4632-4637Conference paper, Published paper (Refereed)
Abstract [en]

We study the problem of estimating the largest gain of an unknown linear and time-invariant filter, which is also known as the H norm of the system. By using ideas from the stochastic multi-armed bandit framework, we present a new algorithm that sequentially designs an input signal in order to estimate this quantity by means of input-output data. The algorithm is shown empirically to beat an asymptotically optimal method, known as Thompson Sampling, in the sense of its cumulative regret function. Finally, for a general class of algorithms, a lower bound on the performance of finding the H-infinity norm is derived.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2017
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-223861 (URN)10.1109/CDC.2017.8264343 (DOI)000424696904075 ()2-s2.0-85046136421 (Scopus ID)978-1-5090-2873-3 (ISBN)
Conference
56th IEEE Conference on Decision and Control
Funder
Swedish Research Council, 2015-04393; 2016-06079
Note

QC 20180306

Available from: 2018-03-06 Created: 2018-03-06 Last updated: 2019-08-27Bibliographically approved
Petrosyan, V. & Proutiere, A. (2017). Viral initialization for spectral clustering. In: ESANN 2017 - Proceedings, 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning: . Paper presented at 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN 2017, 26 April 2017 through 28 April 2017, Bruge, Belgium (pp. 275-280). i6doc.com publication, Article ID ES2017-49.
Open this publication in new window or tab >>Viral initialization for spectral clustering
2017 (English)In: ESANN 2017 - Proceedings, 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, i6doc.com publication , 2017, p. 275-280, article id ES2017-49Conference paper, Published paper (Refereed)
Abstract [en]

Spectral Clustering is one of the most widely used cluster- ing algorithms. To find k clusters, it runs the K-means algorithm on the top k eigenvectors of a Laplacian matrix constructed from the data. As a consequence, it inherits the initialization issues of K-means. In this paper, we propose Viral Initialization (VI), a novel initialization procedure im- plemented in the Spectral Clustering algorithm before K-means is applied. VI is designed so that the resulting clusterings exhibit low normalized cut (Ncuts) values. This design principle is aligned with the recent observation that "good" clusterings have low Ncuts values. We show, through exten- sive numerical experiments, that the Spectral Clustering algorithm with VI consistently outperforms other state-of-the-art clustering techniques.

Place, publisher, year, edition, pages
i6doc.com publication, 2017
Keywords
Machine learning, Matrix algebra, Neural networks, Clustering techniques, Design Principles, Initialization procedures, Normalized cuts, Numerical experiments, Spectral clustering, Spectral clustering algorithms, State of the art, K-means clustering
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-262459 (URN)2-s2.0-85069455171 (Scopus ID)9782875870391 (ISBN)
Conference
25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN 2017, 26 April 2017 through 28 April 2017, Bruge, Belgium
Note

QC 20191017

Available from: 2019-10-17 Created: 2019-10-17 Last updated: 2019-10-17Bibliographically approved
Organisations

Search in DiVA

Show all publications