Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedback
Authors: Quan Zhou
Jakub Marecek
Robert Noel Shorten
Venue: Accepted by TMLR ()

Abstract: There is an increasing need to enforce multiple, often competing, measures of fairness within automated decision systems. The appropriate weighting of these fairness objectives is typically unknown a priori, may change over time and, in our setting, must be learned adaptively through sequential interactions. In this work, we address this challenge in a bandit setting, where decisions are made with graph-structured feedback.

Jakub Mareček Published in Transactions on Machine Learning Research (02/2026)
Online Learning with Multiple Fairness Regularizers via Graph-Structuree Feedback
Quan Zhou'
guan.shou@museedu.
Deportment of Mathematics, National University of Singapore
jokub @marecek.ca
Department of Computer Science, Czech Technical Universiby
Robert Shorten
r. ..shorten@mmeriian uk
Dyson School of Design Engineering, Imperial College London
Reviewed on OpenReview: bttps///pppnneiieeeett///ouuuord
Abstract
There an increasing need lo enforce multiple, often competing, measures of fairness within automated decision systems. The appropriate weighting of these fairness objectives is typi- cally unknown a priori, may change over time and, in our setting, must be learned adaptively through sequential interactions. In this work, we address this challenge in a bandit setting, where decisions are made with graph-structured feedback.
1 Introduction
Artificial intelligence (AI) has become deeply integrated into modern society, powering applications across business, healthcare, finance, and public policy. Its rapid adoption stems from its ability to automate complex decision-making processes scales previously unimaginable. However, as AT systems increasingly influence outcomes that directly affect individuals and communitics, ensuring fairness becomes a critical concern. This work focuses specifically on fairness in bandit-based sequential decision-making senttssnnniingsseeinnng where decisions must be made repeatedly with only partial, stochastic feedback. Fairness in such sequential AI systems is not only matter of ethical responsibility but also a practical necessity for building trust, meeting regulatory standards, and supporting long-term social and organizational goals.
One of the main challenges in achieving fairness is that can be defined in numerous, often conflicting, ways. Mcasures of fairness can focus on individuals, subgroups, or combinations of protectod attributes such as race and gender. Optimizing for one notion of fairness frequently comes the expense of another, and fairness objectives can also conflict with traditional performance metries. As result, trade-offs are inherent in the design of fair Al systems. These trade-offs must be incorporated into decision-making Yet, the structure of fairness-fairness and pairness-peffommant term, societal preferences and definitions of fairness are not static but evolve with changing norms, values, and data distributions. This dynamic nature introduces further complexity to fairness in AI.
trade-offs is often difficult to characterize analytically. In the long
Consider, for example, political advertising on the Internet. In some jurisdictions, the current and proposed regulations of political advertising suggest that the aggregate space-time available each political party should be equalised in the spirit of "equal opportunity" [ It is not clear, however, whether the opportunity should be construed in terms of budgets, average price per ad, views, "reach" of the ad, and whether it should correspond to the share of the popular vote in past elections (e.g., in a previous election with some means of data imputation), the current estimates of voting preferences (cf. rulings in the US allowing for
"ork done while PhD student Imperial College London. In the USA, see the equal opportanity section (315) of the Communications Act of 1934, amended many times.

---

Published in Transactions on Machine Learning Research (02/2026)
the participation of only the two leading parties), or be uniform across all registered parties (ef. the "equal time" rule in broadcast media). For example, on Facebook, the advertisers need to declare their affiliation with the political party they support Considering multiple political parties, as per the declaration, and their budgets, one may need to consider multiple fairness measures (o.g., differences in average price per ad, differences in spend proportional to the vole share, differences in the reach, elc, and their 4, 1, le norms). Furthermore, most platforms have a very clear mcasure of ad revenue, which they wish to balance with some "fairness regularizers" Lu et al. (2020). To complicate matters further still, the perceptions of the ideal trade-off among the ad revenue and the fairness regularizers clearly change over time.
In this work, we propose to address the challenge of conflicting fairness notions by explicitly modeling and exploring the space of trade-offs. Fairness measures are often interdependent: some may conflict, while others may partially align, and decisions made at each time step can improve one fairness criterion while negatively impacting another. To capture these relationships, we represent fairness regularizers and available actions as nodes a graph, with odges encoding their interactions, which can be either time-invariant or Lime-varying lo account for evolving social norms. Building on graph-struclured bandits (Mannor & Shamir, 2011), we integrate this representation into sequential decision makiiig framework, enabling sampling- based exploration of the feasible fairness landscape. This approach provides a practical way for decision-makery to navigate trade-offs intelligently, balancing multiple fairness objectives.
Contributions: (1) We formulate the problem of learning under time-varying, multiple fairness constraints as an online resource allocation problem with graph-structured partial feedback. (2) We develop a bandit algorithm for this setting by extending the graph-structured bandits framework: we model fairness regular- izers additional nodes in the feedback graph, which classically only encodes relationships among actions. This enables sequential decisions that balance reward and non-stationary fairness goals.
Our work is inspired by Awasthi et al. (2020), which utilizes an incompatibility graph among multiple fairness regularizers (criteria) and assumes full feedback from all regularizers. Our work differs from prior approaches that formulate fairness-aware sequential decision-making as a Markov Decision Process (MDP). Whereas MDP-based methods typically assume full state observability and known transition dynamics, we restrict attention to the bandit setting, where the learner observes only stochastic rewards from actions, and correlations among actions are embedded in the graph-structured feodback. This makes our framework more suitable for applications where system dynamics are unknown, non-slationary, or loo costly to model explicitly.
2 Related Work
There are many measures of fairness for any protected attributes (e.g., gender, race, ethnicity, income) defining the subgroups. Without attempting encompass all of the related literature, let us present some of the most relevant work.
2.1 Measures of Fairness
There are many definitions of fairness, especially within the context of classification. The statistical definition of fairness requires that a classifie''s statistics-ste such as the raw positive classification rate (also sometimes referred to statistical parity), false positive rate, and false negative rate (also sometimes referred to equalized odds) be equalized across subgroups so that the algorithm's 's errors are proportionately distributed. An initial, naive approach to fairness is to enforce "fairness through unawareness" by excluding protected attributes from the decision model. The shortcoming of this notion is that there may exist unobserved features related to protected attributes, and these features can be used to predict the protected attributes. Therefore, a predictor that ignores protected attributes can still produce outcomes correlated with them. Demographic parity, proposed by Calder et al. (2009). requires that members of each segment of a protected class (e.g., gender) receive the positive outcome at equal rates. However, this criterion may lead to unfairness when the distributions of fcatures differ between advantaged and disadvantaged subgroups, even in the
2In the USA, this may become legal requirement, the Honest Ads Act. Cr. https://ww..coggesss.ggg 1.Sth-congressseeatte-lllll
2

---

Published in Transactions on Machine Learning Research (02/2026)
absence of bias. The notions of equalized odds introduced by Hardt et al. (2016) and counterfactual fairness proposed by Kusner et al. (2077) both require the predictor to be unrelated to protected attributes. Tn other words, these approaches can be viewed as refined versions of unawareness that aim to remove the effects of unobserved fcatures correlated with protected attributes. They focus on ensuring accurate prediction in the presence of unbalanced distributions, without introducing discrimination. The underlying belief is that a predictor is unlikely to be discriminatory if it only reflects real outcomes.
Group fairness provides only average guarantee for individuals within protected group Awasthi et al.) (020)) and is insufficient its own. Even when group fairness criteria are satisfied, outcomes may still be unfair from the perspective of individual members. Individual fairness requires imposing constraints on specific pairs of individuals, rather than on quantities averaged over groups. In other words, it requires that similar individuals should be treated similarly Dwork et al. (2011). This notion relies on the existence of similarity metric that captures ground truth, which typically requires both general and task-specific agrocment on its definition.
2.2 The Conflict Between Group and Individual Fairness
In the United States, affirmative action policies are often controversial because favoring one group inevitably involves disadvantaging another Dur et al. (2020). In the case Regents of the University of California v. Bakke (1978), race was allowed to be one of several factors in college admission decisions. However, California Proposition 209 later prohibited state governmental institutions from considering race, sex, or ethnicity in public employment, public contracting, and public education. In 2019, California Senate Constitutional Amendment No. 5 (SCA-5) sought to eliminate Proposition 209's ban on the use of race, sex, and other characteristics. Asian American communtiies opposed this amendment Wang 2020).. These debates reflect the collision of different perceptions of fairness, which stem from distinct views regarding which factors of individuals' performance they should be held accountable for Schillberg- Hörisch al. (2020).
2.3 Reasoning about Trade-offs
Recently, there have been several attempts to formulate frameworks for reasoning about multiple fairness measures. The "fairness resolution model" proposed by Awasthi et al. (2020) is guided by unfairness com- plaints received by the system and offers a more practical way to maintain both group and individual fairness. This work provides a finilesttate, discrete-time Markov decision process framework that supports multiple fairness regularizers while accounting for their potential incompatibilities. Independently, Ospina et al. (2021) proposed a framework that employs an online algorithm for time-varying networked system optimiza- tion, aiming to trade off human preferences. In particular, the human preference function (i.e., the fairness regularizer function) is learned concurrently with the execution of the algorithm using shape-constrained Gaussian processes. Other works have focused on designing systems that balance multiple, potentially con- flicting fairness measures (Kim et al.) 2020 Lohia et al. 2019). and specifically identifying Pareto front of fairness cairnes--peffrmannde performance trade-ofls Kozdoba et al. 2002
Prior research has emphasized that naively enforcing fixed fairness constraints can sometimes have unintended negative consequences, such as harming minority groups through delayed or compounding effects (Liu et al. 2018c D'Amour et al.) 2020). To address this, researchers have explored approaches that allow AT models to adapt to evolving fairness notions and shifting environments. In particular, sequential docision-making frameworks have incorporated mechanisms for feedback and long-term outcome monitoring, enabling policies
to adjust dynamically as fairness concepts and societal expectations change (Bechavod & Roth 2023
Wen
ct al. 2021 Zhang & Liu 2021 Jabbari et al. 2017).
A Alternatively, one can consider approaches from multi-objective optimization (MOO). A key recent reference is ZZang et al. (202I), who study dynamic MOO but do not provide performance guarantees for their algorithms. This line of work builds on a long history of rescarch on convexification techniques in MOO
(e.g.. Sun al. 2001). Related developments have also appeared in various applied domains, such as mathematical finance Li & Ng (2000).
3

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm
Reference
Regret (allowing for minor variations)
ELP
Mannor & Shamir
2011
ExpBan
Mannor & Shamir
2011
(ogx(G) ((VaT log d)
Exp3-Set
Alon et al.
(2013
UCB-N
Caron et
(2012)
Expected regret parametrised by clique covers
Exp3-Dome
Alon et al.
(2013)
Exp3-IX
Kocák et al.
(2014)
Stochastic feedback graph
UCB-LP
Buocapatnam et a.
2014
Stochastic feedback graph
Exp3.G
Alon et al.
(2015
Tight bounds for some cases
Exp3-WIX
Kocák et al.
(0016)
O(va
CHK
Cohen ct al.
2016
Tight bounds for some cases matching Alon et al. 2005
BARE
Carpentier
Valko
(2016)
Exp3-DOM
Alon et al.
2017
log((T)) (ogg())/ogKKTT) Eie mas(g")
log(() log( mas(g") w.p.
ELP.P
Alon et al. 2017
TS
Tossou ct al.
(2017)
TS
Liu et al. (20186)
Optimal bayesian regret bounds Switching costs
OMD
Arora et (2019
TS+UCB
Lykouris et al. (2000)
IDS
Liu ct al.
[2018a
UCB-NE
Hu et al.
2020
Non-directed graphs Pseudo-regret bounds
UCB-DSG
Cortes et
al.
20200
et al. (2020)
Cascades in the stochastic f.g. O((5" log((V1))2//772/5)
OSMDE
Chen
2021
Lu et al. 2021
Adversarial corruptions
Table 1: An overview of the algorithms for the model with graph-structured feedback. mas(g') is the size of the maximal acyelic graph in G is the coloring number, 8* is the weak domination number, a is the independence number, a* is the effective independence number.
2.4 Graph-Structured Bandits
Graph-structured bandits (Alon 2013 Mannor & Shamir 2011) generalize the classical multi-armed bandit setting {Lai & Robbins 1985) by incorporating known dependency structure among the actions (arms), typically represented edges encode relationships such as similarity, correlation, or shared feedback. Executing an action not only yields a reward for that action but may also provide partial feedback about its neighbors, enabling more efficient exploration. This structure allows algorithms to leverage side information and propagate observed rewards across the graph, reducing uncertainly and improving regret bounds compared to standard bandit approaches. This approach provides middle ground between the classical bandit setting and the expert setting. In the standard bandit setting, only the reward of the chosen vertex is revealed; the best-known algorithm Audibert et al. (2009) achieves optimal regret of order V[A/T. In contrast, in the expert setting, the rewards of all vertices are revcaled, and the optimal regret of order /log( A|)T can be achieved using the Hedge algorithm Freund & Schapire (1997) or the Follow the Perturbed Leader algorithm Kalai & Vempala 2005)).
graph. In this formulation, each vertex corresponds to an action, and
Graph-structured bandits naturally apply to scenarios where dependencies among actions exist, including recommendation systems, networked decision-making, and, as we explore in this paper, reasoning about multiple fairness measures in sequential decision problems. In this work, we first formulate the problem of handling multiple fairness measures graph-structured bandits problem. Once this framework is established, we present algorithms suitable for this setting. In the context of graph-structured feedback, numerous algorithms have been developed, summarized in Table

---

Published in Transactions on Machine Learning Research (02/2026)
3 Our Framework for Reasoning with Multiple Fairness Regularizers
As the need for additional notions of model fairness grows and the trade-offs among them become increas- ingly important, it is necessary to develop comprehensive framework for reasoning about multiple fairness regularizers-partien
in cases where not all regularizers can be fully satisfied simultaneously.
We consider discrete time, with denoting the number of time steps (rounds). We assume the existence of possibly time-varying, (un)directed compatibility graph g (A, E*). The vertex set inchudes action vertices E A and fairness regularizer vertices f E F. The (possibly time-varying) relationships among them are encoded in the edge set E", where v + v' denotes an edge from vertex to vertex v' at time t, with v E A AUR F. Specifically, there are two types of relationships:
4 f: A directed edge from an action vertex to a regularizer vertex f indicates that executing action a will affect regularizer f. This relation is captured by the subset action vertices that can influence f in round t.
i d': A directed edge from an action vertex a to another action vertex a' indicates that executing action a will reveal the reward of executing action a'. This relation is captured by the subset of action vertices whose rewards will be disclosed when executed in round t.
In fact, if we remove the set of regulariser vertices F, the graph reduces to the standard graph-structured bandit setting. The introduction of the extra vertex set F allows us to explicitly account for the states of the fairness regularisers and their associated rewards.
Suppose there exists state space Each regulariscr vertex f E F is characterized by state s E S. The state of regulariser vertex evolves whenever any action vertex a such that 4 f are executed at time t, as formalized in equation !
('((s(tt-),a)) if if f sl11--1)
s(10)
(1)
otherwise,
where p' is the state evolution function.
The reward r² at round & consists of the direct income from executing action and penalties imposed by the fairness regularisers. Formally,
rd (a) = Income (a)
E f(sto.)) JEF
(2)
where Income'(o) denotes the direct reward from exccuting action a, and f(s²) represents the penalty associated with regulariser f in round t, which is function of the states st.
Within this general framework, we consider the case of limited graph-structured feedback. While the func- tions pl and Income" are unknown, the compatibility graph g' is provided at the beginning of each round and may time-invariant or lime-varying (For the case where the graph is time-varying and not disclosed, Alon et al. (2017).) each round, we choose an action and observe the rewards associated with action vertices a' such that I a' according to G This limited feedback is then used to guide decisions in subsequent rounds.
we refer to Algorithm
Nolice that in the limited-feed setting, Awasthi el al. 2020 roduced a compatibility graph consisting only of regulariser vertices in the context fairness. Their approach considers a sequence of fairness rewards, which are functions of the regulariser vertices' states and are received cach time step. These rewards reflect users' perceptions of fairness regarding the outcomes. However, we can also incorporate the actual fairness outcomes feedback, since there may be discrepancy between users" perceptions and reality.
5

---

Published in Transactions on Machine Learning Research (02/2026)
Suppose Algorithm Alg is used to select a' in each round. The overall reward of the algorithm is defined R(Alg) := raa))) We consider two types of regrets:
Dynamic regret: the difference between the cumulative reward of algorithm and that of the best sequence of actions chosen in hindsight, thus OPT - R(Alg), where
OPT
Σ LE[T]
max r' (a).
(3)
aEV
Weak regret: the difference wetneen the cumulative reward of algorithm and that of the best single action chosen in hindsight, applied at all time steps, thus OPTw - R(Alg), where
OPT max aEV
r (a).
(4)
EE
In Table
we provide summary of the common notation used in the paper.
Symbol
Description
t, T
Round index, total number of rounds
k
(Political) party index Set of action vertices
F
Set of fairness regularizer vertices Edge set of the feedback graph Time-varying compalibility graph at round t Size of the maximal acyclic graph in g Directed edge from a E to f E F in g' Directed edge from a A to a' E An g Action chosen at round
E
G (A, E²)
mg)
& f
S d' a'
s(fi))
State of fairness regularizer f after round t Penalty (negative reward) of fairness regularizer f at round Income (reward) vector round t Target shares for each party (fairness goal) Cumulative reward of algorithm Alg over T rounds
((((F))
Income
Share
R(Alg)
OPTw
Optimal cumulative reward of the best sequence of actions in hindsight. Optimal cumulative reward the best single hindsight
OPT
"
Learning rate
8
Confidence parameter Set (1, n.
[n]
Table 2: Summary of common notation used in the paper.
4
Motivating Examples
Let us revisit the example of political advertising on the Internet, which we introduced earlier. Consider two major political parties e.g., the Conservative and Liberal parties along with several third-party candidates (k = 1,2,3) in jurisdiction where political advertisements social networking sites regulated.
(aa) provides general example of the compatibility graph, featuring three action vertices, three regulariser vertices, and nine subgroup regulariser vertices. According to the edge definitions, executing action vertex at could potentially affect. fi, fi, $3, and the rewards associated with a² and a² would be disclosed a executed.
Figure
This setup models scenario in which the regularisers of political advertising represent dollar spent, reach, and number of shares, respectively, each of which is required to satisfy "equal opportunity" constraint.

---

Published in Transactions on Machine Learning Research (02/2026)
The subgroup regulariser vertices fk. fh. ff impose constraints on the same metrics (dollar spent, reach, number of shares) for party k, ensuring they remain within specific ranges. While there could be many more actions in practice, in this example we consider a1, 42, 03 as selling one unit of advertising space-time to the Conservative party, the Liberal party, and the third-party candidates, respectively.
As another example, consider the same three political parties. There are three action vertices (A {ai, 02, (2,03)) and three regulariser vertices (F' = {fi, fa)), each corresponding to one party. The ac- tion ag represents selling one unit of advertising space-time to party k. The state g(fe.t) represents the cumulative number of space-time units sold to party k up to round t, and assume the initial states of the regulariser vertices are [0, 0, 0j.
Suppose the regularisers suggest that the allocation s(fe.0) k,1,2,3 should be proportional to the share of the popular vote. One could then set the regularisers f1, f2. fa to require the two major parties and all third-party candidates to receive an equalized allocation of political ads on a social media platform, i.c., s(fu.t) /T = 1/3 for 2, In each round, each regulariser fa returns penally based on how far the allocation for party k deviates from its target share: fa(((fe.))= = s(44. -3 Let Income be the income vector at time t. The income from executing action 0ę in round is denoted Income' (ax), i.., the k-th component of Income'.
Let us consider T 2, and the income vector for the two rounds to be:
Income [1 0 0] Income [o 0]
Here, we would like to learn the trade-off between the regularizers and the income of the platform. Corre- spondingly, the state transmission function P is set to be glfe.f) = s(f..t1) + if a is executed in time otherwise the state stays the same.
OPTD: In the example above, the best sequence of actions would choose different actions of each round. Perhaps it could conduct an in the first round and 0g in the second round. Let (Ftt) be the 3-dimensional vector (slfiit,, slfeat), g(fast)), then with the corresponding states being
((.11) = [1 0 0],
8 (F22 =
[1 1 10..
The resulting reward is
(1
(1-
OPT =
+ 2
+2 x
3
3
2
3
3
OPTw: If, on the other hand, we were to pick only a single action vertex to be taken in both rounds t. The corresponding actions and states would be:
(F.1) = 1 0
(F2) = 2 0
0
The resulting reward is
1 OPTw 2 (11- +2 + x 5
-2-2x(1-1++xx))
Limited Feedback: When P and Income' are unknown and only the rewards yd revealed, our feedback at time is therefore limited to: the reward for the chosen action a", plus the rewards for any action where at 4 in the compatibility graph g'.
Figure [[c] provides an example of time-invariant graph, which must be disclosed before the first round. According to the edge definitions, if (a2 4 az) and we select action 0g in round t, the reward r'(2)) that we actually achieve will be revealed immediately. Simultaneously, we also observe the reward r(ag) that we could have obtained had we selected action vertex dg.
The compatibility graph ge can also be timo-varying, in which case is disclosed at the beginning of each round t. This can model situations such as temporary malfunctions or availability constraints for certain actions.
7

---

Published in Transactions on Machine Learning Research (02/2026)
f
f3
03
Q3
Q1
83
f
f3
f3
f3
fi
f2
f3
(a)
(b)
(c)
Figure 1: Examples of the compatibility graph with 3 action vertices (green), i.e., a1, 02, dg and 3 regularizer verlices (dark grey), i.e., /2, Sa. Additionally, (a) has extra subgroup regularizer vertices (light grey), i.e., fk. fky f for each subgroup & E [1.
5 A Model with Graph-Structen
Bandit Feedback
Starting with Mannor & Shamir (0011), this line of work introduced a graphical feedback system to model the side information available in online learning.
the graph (corresponding to the action vertices and odges among them in our framework), a directed edge from vertex a to vertex a' implics that by choosing a, the rewards associated with both a and a' are revealed immeedaateyy. Note that an undirected edge bet ween vertices and a' can be interpreted as two directed edges, 4 a' and a' 4 a.
5.1 Time-variant Craph-Structuree Bandit Feedback
There several algorithms available in the literature for graph-structured feedback. Mannor & Shamir (2011) introduced the ExpBan and ELP algorithms, where ELP allows for time-varying graphs, detailed in Algorithm [ When the graph is disclosed only after the action is taken, the Exp3-SET algorithm suffices, with complete analysis provided in Alon et al. (2015), which dorives regret bounds for both obscrvable and unobservable graphs. In the context of multiple lairness regularisers, we model the compatibility graph as a directed, informed, and noosstoci variant, following Alon
(2017).
In this sctting, the reward function rf in round t be arbitrary bounded function of the history of actions. The compatibility graph may be lime-varying but is disclosed at the beginning of each round. Immediately after choosing action at, the reward associated with a' is revealed, as well as the rewards associated with other actions if a' 4a.
Let A(A) denote the probability simplex over the set of action vertices A. Let (f6)) be the probability of observing the reward of action vertex a' in round i, and p(..) the probability of selecting a² in that round. In Algorithm ff is determined as a trade-off between the weight ((.t) and the exploration factor (()) modulated by an egalitarianism factor 7². Here, wiitt) represents the weight of each action vertex, which increases (docreases) when the associated payoff is favorable (unfavorable), while g() in equation Fepreesent the desire select. an action verlex uniformly from each clique of action vertices in G'. Using this setup, the importance sampling estimator pli.t) and the weight (f.f) for each can be updated described in
7
Theorem (Informal version). Algorithm achieves weak regret bounded by
Ö (og((A)/5)
Σ mas(G)) (G*)) LE[T
where Ö hides only numerical constants and factors logarithmic |A| and 1/n, and mas(gg)) denotes the size of marinam acyelic subgraph of the action feedback graph (A, F.).
8

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm Expooentially-Weigheed Algorithm with Linear Programining
Action vertices A, regularizer vertices F and rounds T, compatibility graph g' cach round (or g if time-invariant), confidence parameter E (0, 1), learning rate v E (0, (0,1/(3/A))] Output: Actions and states.
Input:
Initialization: w(o11) 1, for E A.
1: fo 1...,, do
2: Solve the linear program
max min CEA(A) aEA
Σ gla?
(5)
a'sarta
3: Set pla.f) = (1 -²) wla,)) /wa (Ww++ +-* c(a), where W
-EoEd EnEawlas) wlas),
(1+
In(5|Al/0)
7 EA Σ 400 E(a')) B B= 2
In A
Update g(a.t) =I
a' 0o pla'
Draw one action vertex a' according to distribution p(a.0)
Observe pairs pla,t) for all actions such that a' 4 a, where p(a,t) is given equation
2
7:
For any a E A, set estimated reward p(a.t) and update wla+t11, follows
pla.t) platt) 1fa' 4 a)
(6)
gla.2)
(aa,411) = (a.))) exp (n plax))))
(7)
end for
As summarized Alon et al. (011 the regret bounds graph-structured bandits interpolate between the bandit and full-information settings. The size of the maximum acyelic subgraph mas(g)) is the largest possible subgraph of directed graph that contains directed cycles. It quantifies the information plexity of the feedback structure: larger mas(G()) implies denser, more informative feedback pattern. When (A, E²) is complete graph for all t - meaning the decision-maln -aaer observes the losses of all actions, as in the full-information setting we have mas(g = 1. In this case, this bound recovers the standard Ö(VT) regret (up to logarithmic factors). Conversely, when G is empty graph for all t meaning the decision-maker only observes the loss of the chosen action, in the bandit setting - then mas(g |A], and we recover the standard Ö(v[A[T) bandit regret. Between these extremes, the regret bound scales with the graph structure of the action vertices, as captured by the term Everyy mas(g)). The formal version of the theorem and proof is included in the Supplementary Material, but essentially follows from the work of
Alon et al. 2017
Mannor & Shamir 2011
6 Numerical Illustrations
Let us revisit and extend the motivating example in Section 4 by considering five political parties, indexed by k = L,....,, We define five action vertices A {a1...... 05); where a corresponds to selling one unit of advertising space-time to party k's candidates. The state variable g(fe.t) represents the cumulative number of space-time units sold to party l up to round t.
We also introduce five regularizers F = (f...... fo). each requiring that party k's candidates receive a prescribed share of the total advertising space-time- The target shares are sampled from Dirichlet process with concentration parameter a 1 and mean equal to the uniform distribution. Let. Sharey denote the target share for party k. The corresponding regularizer
example, match the most recent election results.
9

---

Published in Transactions on Machine Learning Research (02/2026)
penalizes deviations from this target:
fa (sl = 13S5k.0/ Sharex
for each f. [7], where the penalty is negative reward. The state transmission function is defined gla,t) = g(a.t1) + 1 if action is chosen at round i, and g(a.t) g(a,t1) otherwise. The initial states for all parties are zero.
The platform's revenue at time is Income' (a"), given by the a'-th component of the income vector Income'. We evaluate our method using revenue data from the 5 advertisers (parties) over 100,000 impressions forming 5 100,000 income -rawn from the dataset of Balseiro al. (2020). For each row of this matrix, we first normalize its entries to the range [0, and then add 1, ensuring that the net reward at time tic.., income minus penalty-is nonnegative.
For Algorithm we set the learning rate = 1/15 and the confidence parameter 5 = 0.025. The time horizon T is varied over [30, 80] in increments of 5. For each T', we run 30 repeated trials, each selecting T rows of revenue data uniformly at random from the income matrix. We compare three experimental cases:
Baseline (empty graph). No edges between action vertices, corresponding to classic bandit setting where only the reward of the chosen action is observed.
Time-invariant graph. A single randomly generated compatibility graph is used for all rounds in each trial.
Time-narying graph. A new compatibility graph is randomly sampled in each round.
Note that when we generate a random graph, we refer specifically to the action feedback graph among action vertices, since the edges between actions and regularizers are fixed by the definition of the vertices and regularizers themselves. (By construction, selecting any action changes the states of all regularizers; therefore, the compatibility graph must contain directed edges from each action vertex to every regularizer vertex.) To generate the action feedback graph, we iterate over all possible directed edges between action vertices. For each candidate edge, we sample uniform random number u ~ 1) and include the edge in the graph u > 0.2; otherwise, it is excluded.
Figure 2 compares the dynamic regret (blue) and weak regret (green) across the three experimental cases, with one subplot per case. Figure 3 plots the corresponding objective values (OPTp, OPTw, computed via CVXPY (Diamond & Boyd 2016)) and the cumulative reward R(Alg) achieved by Algorithm for each case. Results are averaged over 30 trials, with shaded regions indicating + one standard deviation; subplots in the same row share common y-axis.
From the figures above, the baseline performs worse because it does not utilize the graph structure. The time-varying graph performs slightly better than the time-invariant graph, potentially due to the varying topology providing more informative leedback over time. The optimal values of OPT, and OPTw were computed using CVXPY; each corresponds an integer programming problem. The dynamic benchmark OPTp is harder to solve because it involves larger set of integer variables: while OPTw requires only 5 variables (one per action), OPT, requires 5 x T variables (one per action per round). Consequently, the computed values for OPTp exhibit greater variance in the figure.
The implementation and experimental scripts are publicly available at https::/ www.ttuu.coom0000 com/Quan--e Quuunnuuunnuu///////
graph- -ww.eeaaaa-aiiionnnniiiiiaa -aaa-oonine--eerninng
7 Conclusions
In this paper, we have addressed the challenge of bandit-based sequential decision- decision-making under non- stationary fairness constraints, setting that arises in many real-world resource allocation systems where decisions must be made with limited feedback. Our contributions are twofold. First, we formulated this prob- lem online bandit. problem with graph-structured partial feedback, explicitly modeling the interplay
10

---

Published in Transactions on Machine Learning Research (02/2026)
Baseline (empty graph)
Time-invariant graph
Time-varying graph
120
Dynamic Regret
100
Zero
Weak Regret
Regret
-20
Time Window [T]
Time Window [T]
Time Window [T]
Figure 2: Dynamic (blue) and weak (green) regret Algorithm under the three experimental configurations. Porformance evaluated over 30 independent trials, cach with randomly sampled batch of income vectors. The curves represent mean regret across trials, with shaded error bands corresponding to + one standard deviation.
Baseline (empty graph)
Time-invariant graph
Time-varying graph
80
Objective Values (Rewards)
50
OPTp
20
OPTw
R(Alg)
10
30
40
30
60
70
80
40
80
30
40
50
70
Time Window [T]
Time Window [T]
Time Window
Figure 3: Rewards achieved by Algorithm I in the three experimental cases, alongside the com- puted optimal values OPTp (blue) and OPTw (green) via the CVXPY package (Diamond & Boyd 2016). Results are averaged over 30 trials, each using a randomly selected batch of revenue vectors. Curves show means, with shaded bands indicating + one standard deviation.
between actions within the bandit framework. Second, our approach, fairness regularizers are represented as additional vertices in the feedback graph, which traditionally only encoded relationships among actions. This formulation enables the bandit decision-maker learn from structured feedback while dynamically balancigg reward objectives with multiple fairness goals that may evolve over time.
11

---

Published in Transactions on Machine Learning Research (02/2026)
Acknowledgments
This work has received funding from the European Union's Horizon Europe research and innovation pro- gramme under grant agreement No. 101070568. This work was also supported by Innovate UK under the Horizon Europe Guarantee; UKRI Reference Number: 10040569 (Human-Compate with Guarantees (AutoFair)). J.M. also acknowledges the support of National Recovery Plan funded project MPO 602733/4//2130//2100 CEDMO 2.0 NPO. R.S. was in part supported by the IOTA Foundation.
Artificial Intelligence
References
Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. Advances in Neural Information Processing Systems, 26:1610-1618, 2013.
Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory, pp. 23 35, PMLR, 2015.
Noga Alon, Nicolo Cesa-Bianchi Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Non- stochastic multi-armed bandits with graphrstructured leedback. SIAM Journal on Compuling, 46(6): 1785-1826, 2017.
Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch-BBuc, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: wwp.e.apppppp.. .ddf
Yven-Yves Audibert, Sébastien Bubeck, et al. Minimax policies for adversarial and stochastic bandits. COLT, volume 7, pp. 1 1-122, 2009.
Pranjal Awasthi, Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Beyond individual and group fairness. arxiv preprint arXix:2008. 09490, 2020.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference Machine Learning, pp. 613-628. PMLR, 2020.
Yahav Bechavod and Aaron Roth. Individually fair learning with one-sided feedback. In International Conference on Machine Learning, pp. 1954-1977. PMLR, 2023.
Swapna Buceapatnam, Atilla Eryilmaz, and Ness B Shroff. Stochastic bandits with side observations networks. Tn The 2014 ACM international conference on Measurement and modeling of compuler systems, pp. 289-300, 2014.
Bobby Calder, Edward C Malthouse, and Ute Schaedel. An experimental study of the relationship between online engagement and advertising effectiveness. Journal of interactive marketing, 23(4):321 331, 2009.
Stephane Caron, Branislav Kveton, Mare Lelarge, and S Bhagat. Leveraging side observations in stochastic bandits. In UAI, 2012.
Alexandra Carpentier and Michal Valko. Revealing graph bandits for maximizing local influence. In Artificial Intelligence and Statistics, pp. 10-18. PMLR, 2016.
Houshuang Chen, Zengfeng Huang, Shuai Li, and Chihao Zhang. Understanding bandits with graph feedback. arXiv preprint Xiv:::2105.1 14260, 2021.
Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feedback graphs without the graphs. In International Conference on Machine Learning, pp. 811-819. PMLR, 2016.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mchryar Mohri, and Ningshan Zhang. Online learning with dependent stochastic foodback graphs. In International Conference on Machine Learning, pp. 2154-2163. PMLR, 2020.
12

---

Published in Transactions on Machine Learning Research (02/2026)
Alexander D' A'mour, Hansa Srinivasan, James Atwood, Pallavi Baljekar, David Scalley, and Yoni Halpern. Fairness is not static: deeper understanding of long term fairness via simulation studies. In Proceedings of the 2020 Conference on Faimess, Accountability, and Transparency, pp. 525 534, 2020.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimiza- tion. Journal of Machine Learning Research, 2016. URL https:// hwwttaaffrd.eeu/bboo///pppeepeee pttbbooppppaprr/pp/ /
cvxpy_paper pdf To appear.
Umut Dur, Parag A Pathak, and Tayfun Sönmez. Explicit vs. statistical targeting in affirmative action:
Theory and evidence from chicago's exam schools. Journal of Economic Theory, 187:104996, 2020.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S Zemel. Fairness through awareness. corr abs/ 19ss110433913 (2011). arXiv preprint arXit:1104.3913, 2011.
Yoar Freund and Robert E Schapire. cheissin generalization of ou-line learning and an application boosting. Journal of computer and system sciences, 55(1):1199 139, 1997.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. arXiv preprint 1610.0610.02/11 2016.
Bingshan Hu, Nishant A Mehla, and Jianping Pan. Problem-dependdnt regret bounds for online learning with feedback graphs. In Uncertainty in Artificial Intelligence, pp. 852-861. PMLR, 2020.
Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in rein- forcement learning. In International conference on machine learning, pp. 1617-1626. PMLR, 2017.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71 (33):29113377 2005.
Joon Sik Kim, Jiahao Chen, and Ameet Talwalkar. Fact: A diagnostic for group fairness trade-offs. In International Conference on Machine Learning, pp. 5264-5274. PMLR, 2020.
Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficientt learning by implicit exploration bandit problems with side observations. In Proceedings of the 27th International Conference on Newral Information Processing Systems- Volume 1, pp. 613 621, 2014.
Tomášs Kocák, Gergely Neu, and Michal Valko. Online learning with noisy side observations. In Artificial Intelligence and Statistics, pp. 1186-1194 PMLR, 2016.
Mark Kozdoba, Binyamin Perets, and Shic Mannor. Efficiont fairnss--performance pareto front computation. arXiv preprinl 2i0: 17643, 2024.
Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Xrxiv preprint arXiv:1 700.00000666 2017.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22 22, 1985.
Duan Li and Wan-Lung Ng. Optimal dynamic portfolio selection: Multiperiod mean-variance formulation. URL https:
Mathematical Finance, 10(3):387-400 2000. doi: 000000
camlinelibrary wiley.... com http://...//..111144449999.0.000
Shuai Li, Wei Chen, Zheng Wen, and Kwong-Sak Leung. Stochastic online learning with probabilistic graph feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04))4675 4682, Apr. 2020. doi: 10.1609/ aaai. v3404..99.. URL https://ojs..aalt hrggi////oj..aaai.oo///ii.... wttp://AAt/aatiil//ieeee////
Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018a.
Fang Liu, Zizhan Zheng, and Ness Shroff. Analysis of thompson sampling for graphical bandits without the graphs. Xix preprint arxiv: 1845.800.0880 1805088990 2018b.
13

---

Published in Transactions on Machine Learning Research (02/2026)
Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. In International Conference on Machine Learning, pp. 1150-3156 PMT.R, 2018c.
Pranay K Lohia, Karthikeyan Natesan Ramamurthy, Manish Bhide, Diptikalyan Saha, Kush R Varshney, and Ruchir Puri. Bias mitigation post-processing for individual and group fairness. In Loassp 2019-2019 lece international conference acoustics, speech and signal processing (icassp), pp- 2847-2851. IEEE, 2019.
Haihao Lu, Santiago Balseiro, and Vahab Mirrokni. Dual mirror descent for online allocation problems.
arXiv preprint Xr::20002. 10421, 2020.
Shiyin Lu, Guanghui Wang, and Lijun Zhang. Stochastic graphical bandits with adversarial corruptions. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8749-8757, 2021.
Thodoris Lykouris, Éva Tardos, and Drishti Wali, Feedback graph regret bounds for thompson sampling and ucb. In Algorithmic Learning Theory, pp. 592 614. PMLR, 2020.
Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. Advances in Newral Information Processing Systems, 44:6,46692, 2011.
Ana M Ospina, Andrea Simonetto, and Emiliano Dall'Anese. Time-varying optimization of networked systems with human preferences. arXiv preprint XrXi::2003.144 2021.
Hannah Schildberg-Hörissee Chi Trieu, and Jana Willrodt. Perceived fairness and consequences of affirmative action policies. 2020.
Xiao-Ling Sun, KIM McKinnon, and Duan Li. A convexification method for class of global optimization problems with applications to reliability optimization. Journal of Global Optimization, 21 2001.
Aristide CY Tossou, Christos Dimitrakakis, and Devdatt Dubhashi. Thompson sampling for stochastic bandits with graph feedback. In Thirty-Fire First AAAI Conference Artificial Intelligence, 2017.
Norman C Wang. Diversity, inclusion, and equity: evolution of race and ethnicily considerations for the cardiology workforce in the united states of america from 1969 to 2019. Journal of the American Heart Association, 9(7)xc015959, 2020.
Internaiional Conference on Artificial Intelligence and Statistics, pp. 1144 1152. PMLR, 2021. Min Wen, Osbert Bastani, and Ufuk Topcu. Algorithms for fairness in sequential decision making. In
Qingyang Zhang, Shouyong Jiang, Shengxiang Yang, and Hui Song. Solving dynamic multi-objactive prob- lems with new prediction-hased optimization algorithm. Plos one, 1608))e0254839, 2021.
Xueru Zhang and Mingyan Liu. Fairness in learning-based sequential decision algorithms: A survey. In Handbook of Reinforcement Learning and Control, pp. 525 555. Springer, 2021.
A Proof of Theorem
Proof. We want to show that with learning rate S A/( sufficiently small such that B S 1/4, with probability at least - 6, we have that the weak regret of Algorithm D is upper bounded by equation g where Ô hides only numerical constants and factors logarithmic in |A] and 1/n.
log(5) (og(5)Al/m)
5 llg
mas(g') +15
ma) xE[T]
log |A|
1E|T]
2 log (5) Al/8)
+O 1101+V/T
max mas) LE(T)
1
14

---

Published in Transactions on Machine Learning Research (02/2026)
To prove this, refer to Theorem 9 in Alon et al. A Algorithm
2017
10 9
use the definition of W Wa,lla)) pla.)) in
equation 11 uses inequality exp(x) &
W
w(act11)
w(a,t)
exp(1pla.1))
(9)
W
W
W
.ЕΛ
pla1)
7lc(a.))
exp(1fllat)
(10)
1 - gl
aEA
(a.))
-(((a0))
( (I+pplan) + (19pba.tt))
(11)
1 nt
aεA
< 1
(plit)/platt + (p(aat)))) (p(o:t)22)
(12)
aEA
equation 13 uses equation 12 and inequality 51 1x
WT+1
W
Σ In
S
WI
We
EE(T]
(13)
ΣΣ
ΣΣ ? RE|T 1- (pla:))faut)++ tpplal0
For fixed single action vertex a, we have
WT+1
w(aTT1)))
ln
In
W1
W
(a.1))
exp(11 Everry plan))
(14)
In
17
plant) - In |A|.
|A]
:E(T]
From Azuma's inequality, Chernoff bound and Freedman's 's inequality, we have the upper bound of regret
with probability at least 1 1- 8 in equation 15 Then, equation 16 obtained by combining (4) By
substituting condition 3 = (()) >" Ô (1mas (G*) E [n, 1/2], we get the upper bound in equation where
δ ignores factors depending logarithmically on |A| and 1/5.
Σ (a.1) (a',0) 1E/21
p(a,t) Σ Σ pla.t)
ln(k/5) +
In((AA/6)
(15)
3
2
[E[T]
BE(T] AAA
+ 2 2l((1 Σ mas 3
Σ mas(g") +
max maas(g)) (E(T]
IETT]
LE|2
<
n
(pla.1)) + +t (((t)))paattt
+ n
In AA
(16)
1
EEIT AEA
1n(k/5)
T Tin([A|] (|/))
+
2m((1/) Σ
mas (Gs) + 3 Σ
mas(g*) + +0
mm (maxxmas(G')
B
2
(E(]T
EE[T]
15


Reviews:
[{"review_id": "xzcqeShm6X", "reviewer": "Reviewer_y5ii", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors offer a broad overview of the problems of fairness in machine-learning systems in general and a good high-level overview of graph-structured bandits. They show how the existing framework of graph-structured bandits can be used for some decision-making that considers fairness issues.", "claims_and_evidence_yn": "No", "claims_explanation": "I have trouble identifying the expected contribution from the authors in the field, apart from a modelling framework. Based on the beginning of the submission (what is closest to TMLR's \"claims\", in my opinion), I would have expected a much deeper analysis (details below).\n\nMore specifically, what is \"time-varying convexification\"? The term is not really explained in the manuscript, which seems like an overreaching claim for the current contents.", "audience_yn": "Yes", "audience_explanation": "The paper is about a specific field of machine learning (bandit algorithms) and uses the lens of fairness, which ought to see more light. It explains how existing algorithms could be used for learning, decision-making in the bandit setting (with a hidden state), and fairness optimisation.", "requested_changes": "Major comments:\n- Your introduction is very generic and broad and clearly underlines the need to include fairness. However, the proposed article focuses on fairness in the specific case some stakeholder wants to make decisions with fairness in mind with the strong constraint that the decisions can be made by bandits. This is a very strong assumption and limitation of your work, while it is not as clearly indicated in the title or in the article itself (for instance, you frequently refer to \"sequential decision-making\", and bandits are a very limited way to perform sequential decision-making). In my opinion, this limitation should be at least hinted at in the title, in the abstract, and in the first two sections. \n- What is the main contribution of the article? Based on the abstract and first few sections alone, I would have expected a new algorithm that works in the described setting or more detailed experiments of existing algorithms in the setting you study or a more comprehensive numerical or theoretical study of existing algorithms. Instead, you offer a small theoretical study of a single algorithm that was the first one introduced in your literature survey (I couldn't find earlier attempts) with a very brief numerical experiment of the same algorithm. Your theoretical study focuses on your weak regret, a metric whose limitations you very well highlight in your manuscript. \n\nMinor comments (in order of appearance in the submitted PDF file):\n- Section 2.1: \"fairness under unawarenes\" is not explained, while it would be beneficial to the manuscript to have a brief explanation (one sentence could be enough). \n- Section 2.4: I find it surprising that you do not cite prior work on graph-structured bandits in the second paragraph, like your Mannor & Shamir (2011). \n- Table 1: having \"Algorithm 1\", from Cohen et al. (2016), induces some unneeded confusion with your Algorithm 1 (ELP). I would suggest calling this \"Cohen algorithm\" or \"Cohen-Hazan-Koren algorithm\" (or CHK in the interest of space) to reduce the potential to mistake the reference's algorithm with your own.\n- Section 3: \"The notation a t −→ a′ indicates an edge connecting action a to a′\", what is the role of t in this notation? \n- Section 3, formula 4: wouldn't it be clearer to write $\\sum_t \\max_{a\\in V} r^t\\left(a\\right)$ ?\n- Theorem 1: this is the first use of the notation mas(G) outside of a caption (Table 1, many pages before). Please consider summarising your notations in a dedicated space, at least for the notations used more generally in the submission (e.g., χ does not really need to be defined outside the caption of Table 1). It would be easier to follow, rather than to look for definitions that are scattered throughout the manuscript. \n- Section 5: in the sentence starting with \"The revenue of the platform, is assumed\", is this the only use of $\\dot s$? I didn't see a definition of it.", "broader_impact_concerns": "Section not present and not needed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XlR0gb7T2B", "reviewer": "Reviewer_twZu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a framework for tackling multiple possibly conflicting fairness objectives in a sequential decision-making problem. The authors formulate actions and fairness regularizers as nodes in a graph-structured model, and maintain the balance between fairness and performance under limited bandit feedback and time-varying network topology. The authors adapt and extend existing graph-structured bandit algorithms (notably Alon et al., 2017) and provides theoretical regret guarantees as well as illustrative numerical experiments on a political advertising scenario.", "claims_and_evidence_yn": "No", "claims_explanation": "Although the paper is understandable, the structure/organization of the presentation could be improved. Specifically, in the abstract, the authors mentioned the learning of time-varying convexifications of multiple fairness measures, but there are no clear mathematical formulations or discussion regarding that. There are also some technical parts which need further clarification (please see the major comments).", "audience_yn": "Yes", "audience_explanation": "The need of maintaining good trade-offs among multiple potentially conflicting fairness measures does exists in many practical applications. Therefore, it is beneficial to see how this need can be formulated from different perspectives.", "requested_changes": "Major comments:\n\n  1. It seems that the proposed algorithm heavily reuses existing algorithms in the literature (e.g., Exp3-SET or the one proposed by Alon et al., 2017). The reviewer wonders whether there are any new insights on the algorithmic side, or if the method essentially follows the same structure with a new interpretation in the context of fairness.\n\n2. The result in Theorem 1 does not fully characterize how fairness-related quantities (e.g., correlations among fairness regularizers) affect the regret bounds or learning dynamics. The regret guarantee appears to be a direct application of existing graph-bandit theory, without providing any fairness-specific insights.\n\n3. The empirical evaluation is limited to a small-scale synthetic example. The number of trials is too small to yield any statistically significant conclusions, and from the simulation results, the reviewer cannot verify how the performance depends on the parameters appearing in the regret bound (e.g., the network structure).\n\n4. In the abstract, the authors highlight the learning of time-varying convexifications (i.e., the relative weights) of multiple fairness measures. However, this idea is not clearly or rigorously formalized in the paper. Further clarification is needed.", "broader_impact_concerns": "None", "additional_comments": "Minor comment: \n\nIn Equation (3), is the state dependent on the specific regularizer or not ($s^t$ or $s^{(f,t)}$)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "YsU17N41k0", "reviewer": "Reviewer_SGyL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a sequential decision-making framework for exploring tradeoffs between multiple fairness measures. The proposed approach extends the graph-structured bandit problem by adding extra graph nodes that represent fairness measures. Within this context, the authors focus on the case of limited graph-structured feedback, where the fairness measure state updates corresponding to each selected action are encoded by edges connecting that action node and the corresponding fairness measure nodes.", "claims_and_evidence_yn": "No", "claims_explanation": "I find it difficult to evaluate this work because it is not very clear about what claims it is trying to make. However, there are enough deficiencies in various areas to raise questions about the value of the proposed approach.\n\nThe abstract justifies the basic idea of considering multiple fairness notions and provides high-level details of the proposed approach. The conclusion is a single sentence that reiterates a high-level description of the proposed framework. Neither of these sections provide information or claims about the novelty of the proposed method compared to prior works.\n\nThe introduction provides elaboration on the intended use case of the approach, but there is no explicit list of primary contributions. \n\nThe proposed approach is evaluated on a resource allocation dataset, but the paper does not compare its results to any baseline approach. There is also no discussion of the results, making their relevance unclear and making it hard to tell how they support the paper's claims.\n\nThe appendix provides a proof of an upper bound on regret for the proposed approach, which is appreciated. However, the proof goes nearly unmentioned throughout the rest of the work, and the authors never attempt to leverage the derived upper bound to justify any advantage of the proposed approach over prior works. \n\nOverall, I do not think the work does a good job of clearly articulating the claims it is trying to make, and I do not believe that the evidence provided by the work is sufficient in its current state to support the claims it should be making.", "audience_yn": "Yes", "audience_explanation": "The idea of explicitly encoding the connections between fairness measures and actions in a graph-structured framework seems quite interesting. I suspect it could serve as a useful basis for developing future algorithms related to fairness tradeoffs.", "requested_changes": "Necessary changes:\n\n+ Update and expand the abstract and introduction to include a clearer set of claims regarding the unique value provided by your framework compared to prior works.\n\n+ Add a \"main contributions\" list to the end of the introduction section.\n\n+ Provide a discussion of the results shown in Figures 2 and 3. How do these results support your paper's claims?\n\nOptional changes that would improve the work: \n\n+ Update Figures 2 and 3 with some comparison to a baseline approach. If no baseline exists or if it doesn't make sense here to compare to a baseline, add a paragraph for the reader that explains why.\n\n+ Replace the \"Case I\" and \"Case II\" chart titles with \"Time-Invariant Graph\" and \"Time-Varying Graph\". You have enough space to make those graphs wider to fit a clearer title. \n\n+ If it makes sense, you should use the derived regret upper bound from the proof of Theorem 1 to help justify claims about the proposed framework.\n\n+ Update and expand the conclusions section accordingly with the rest of the changes you make.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)