• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Achieving Fairness in the Stochastic Multi-Armed Bandit Problem

    View/Open
    Thesis full text (757.8Kb)
    Author
    Patil, Vishakha
    Metadata
    Show full item record
    Abstract
    The classical Stochastic Multi-armed Bandit (MAB) problem provides an abstraction for many real-world decision making problems such as sponsored-search auctions, crowd-sourcing, wireless communication, etc. In this work, we study FAIR-MAB, a variant of the MAB problem, where, in addition to the goal of maximizing the sum of expected rewards, the algorithm also has to ensure that each arm is pulled for at least a given fraction of the total number of rounds which imposes an additional fairness constraint on the algorithm. The non-trivial aspect of FAIR-MAB arises when the time horizon T is unknown to the algorithm. The literature on fairness in the MAB setting centers around procedural fairness where the fairness guarantee is in terms of the decision-making process followed by the algorithm rather than in terms of the outcome of the decisions made by the algorithm. In contrast to this, we consider an outcome-based fairness notion which can be validated based on the decision of the algorithm. Our primary contribution is characterizing a class of algorithms for the FAIR-MAB problem by two parameters: the unfairness tolerance and the learning algorithm used as a black-box. We define an appropriate notion of fairness and show that our algorithm guarantees fairness independent of the choice of the learning algorithm. We define the notion of fairness-aware regret which naturally extends the conventional notion of regret, and show that the fairness-aware regret of our algorithm matches in order, the regret of the black-box learning algorithm in the absence of fairness constraints. Finally, we show via detailed simulations that our algorithm outperforms the best known algorithm for the FAIR-MAB problem in terms of the fairness guarantee that it provides, while performing comparably in terms of the fairness-aware regret. We also evaluate the cost of fairness in the MAB setting in terms of the conventional notion of regret
    URI
    https://etd.iisc.ac.in/handle/2005/5129
    Collections
    • Computer Science and Automation (CSA) [394]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV