Uniform-reward reinforcement learning from human feedback (RLHF), which trains a single reward model to represent the preferences of all annotators, fails to capture the diversity of opinions across sub-populations, inadvertently favoring dominant groups. The state-of-the-art, MaxMin-RLHF, addresses this by learning group-specific reward models, and by optimizing for the group receiving the minimum reward, thereby promoting fairness. However, we identify that a key limitation of MaxMin-RLHF is its poor performance when the minimum-reward group is a minority. To mitigate this drawback, we introduce a novel framework, termed *SharedRep-RLHF*. At its core, SharedRep-RLHF learns and leverages *shared preference traits* in annotations among various groups, in contrast to learning separate reward models across groups. We first show that MaxMin-RLHF is provably suboptimal in learning shared traits, and then quantify the sample complexity of SharedRep RLHF. Experiments across diverse natural language tasks showcase the effectiveness of ShareRep-RLHF compared to MaxMin-RLHF with a gain of up to 20% in win rate.

This paper introduces a general framework for risk-sensitive bandits that integrates the notions of risk-sensitive objectives by adopting a rich class of {\em distortion riskmetrics}. The introduced framework subsumes the various existing risk-sensitive models. An important and hitherto unknown observation is that for a wide range of riskmetrics, the optimal bandit policy involves selecting a \emph{mixture} of arms. This is in sharp contrast to the convention in the multi-arm bandit algorithms that there is generally a \emph{solitary} arm that maximizes the utility, whether purely reward-centric or risk-sensitive. This creates a major departure from the principles for designing bandit algorithms since there are uncountable mixture possibilities. The contributions of the paper are as follows: (i) it formalizes a general framework for risk-sensitive bandits, (ii) identifies standard risk-sensitive bandit models for which solitary arm selections is not optimal, (iii) and designs regret-efficient algorithms whose sampling strategies can accurately track optimal arm mixtures (when mixture is optimal) or the solitary arms (when solitary is optimal). The algorithms are shown to achieve a regret that scales according to $O((\log T/T )^{\nu})$, where $T$ is the horizon, and $\nu>0$ is a riskmetric-specific constant.

This paper investigates two hitherto unaddressed aspects of best arm identification (BAI) in stochastic multi-armed bandits in the fixed-confidence setting. The first aspect is related to the optimality and efficiency tradeoff. Specifically, the two key metrics for assessing bandit algorithms are their computational efficiency and performance optimality (e.g., in sample complexity). In the stochastic BAI literature, there have been advances in designing algorithms to achieve optimal performance at the expense of being computationally expensive (e.g., optimization-based methods). Similarly, there have been also advances in designing algorithms with high computational efficiency that have provable gaps to the optimal performance (e.g., the$\beta $-optimal approaches in top-two methods). This paper introduces a framework for BAI that achieves optimal performance with a computationally efficient set of decision rules. The central process that facilitates this is a routine for sequentially estimating the optimal allocations up to sufficient fidelity. Specifically, these estimates are accurate enough for identifying the best arm (hence, achieving optimality) but not overly accurate to an unnecessary extent that creates excessive computational complexity (hence, maintaining efficiency). The second aspect pertains to the class of parametric stochastic bandits. The existing literature has only focused on the exponential family of distributions. This paper addresses any arbitrary family of distributions parameterized by their mean values (under mild regularity conditions). The optimality is established analytically, and numerical evaluations are provided to assess the analytical guarantees and compare the performance with those of the existing ones.

This paper investigates a hitherto unaddressed as-pect of best arm identification (BAI) in stochastic multi-armed bandits in the fixed -confidence setting. Two essential metrics for assessing bandit algorithms are computational efficiency and performance optimality (e.g., in sample complexity). In stochastic BAI literature, there have been advances in designing algorithms to achieve optimal performance, but they are generally computationally expensive to implement (e.g., optimization-based methods). There also exist approaches that have high computationally efficiency but do not achieve the optimal performance (e.g., UCB-based methods) or achieve it up to a gap (e.g., the$\beta-$optimal approaches in top-two methods). This paper introduces a framework and an algorithm for BAI that achieves optimal performance with a computationally efficient set of decision rules. The central process that facilitates this is a routine for sequentially estimating the optimal allocations up to sufficient fidelity. Specifically, these estimates are accurate enough for identifying the best arm (hence, achieving optimality) but not excessively accurate to an unnecessary extent (hence, maintaining efficiency). Numerical evaluations are provided to (i) establish the optimality and efficiency of the algorithm, (ii) showcase the implicit estimation property of the proposed allocation rules, and (ii) demonstrate the superior performance of the proposed algorithms compared to the existing ones.

This paper investigates the robustness of causal bandits (CBs) in the face of temporal model fluctuations. This setting deviates from the existing literature's widely-adopted assumption of constant causal models. The focus is on causal systems with linear structural equation models (SEMs). The SEMs and the time-varying pre- and post-interventional statistical models are all unknown and subject to variations over time. The goal is to design a sequence of interventions that incur the smallest cumulative regret compared to an oracle aware of the entire causal model and its fluctuations. A robust CB algorithm is proposed, and its cumulative regret is analyzed by establishing both upper and lower bounds on the regret. It is shown that in a graph with maximum in-degree$d$, length of the largest causal path$L$, and an aggregate model deviation$C$, the regret is upper bounded by$\tilde{\mathrm{O}}(d^{L-\frac{1}{2}}(\sqrt{T}+C))$and lower bounded by$\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T}\,\ d^{2}C\})$. The proposed algorithm achieves nearly optimal$\tilde{\mathcal{O}}(\sqrt{T})$regret when$C$is$o(\sqrt{T})$, maintaining sub-linear regret for a broad range of C.

We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite-state space. The state transitions in each arm are captured by an ergodic transition probability matrix (TPM) that is a member of a single-parameter exponential family of TPMs. The real-valued parameters of the arm TPMs are unknown and belong to a given space. Given a function f defined on the common state space of the arms, the goal is to identify the best arm—the arm with the largest average value of f evaluated under the arm’s stationary distribution—with the fewest number of samples, subject to an upper bound on the decision’s error probability (i.e., the fixed-confidence regime). A lower bound on the growth rate of the expected stopping time is established in the asymptote of a vanishing error probability. Furthermore, a policy for best arm identification is proposed, and its expected stopping time is proved to have an asymptotic growth rate that matches the lower bound. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds. It is shown that under every policy, the state-action visitation proportions satisfy a specific approximate flow conservation constraint and that these proportions match the optimal proportions dictated by the lower bound under any asymptotically optimal policy. The prior studies on best arm identification in restless bandits focus on independent observations from the arms, rested Markov arms, and restless Markov arms with known arm TPMs. In contrast, this work is the first to study best arm identification in restless bandits with unknown arm TPMs.

This paper investigates the problem of best arm identification (BAI) in stochastic multi-armed bandits in the fixed confidence setting. A novel formulation based on sequential hypothesis testing is provided, and an algorithm for BAI is proposed that, in spirit, follows the structure of the canonical sequential probability ratio test (SPRT). The algorithm has three features: (1) its sample complexity is asymptotically optimal, (2) it is guaranteed to be δ-PAC, and (3) it addresses the computational challenge of the state-of-the-art approaches. Specifically, the existing approaches rely on Thompson sampling for dynamically identifying the best arm and a challenger. This paper shows that identifying the challenger can be computationally expensive and demonstrates that the SPRT-based approach addresses that computational weakness.

The paper considers the problem of estimating a covariate parameter shared by multiple statistical models. Under the objective of estimating the parameter with target reliability with the fewest number of samples from these models, a fundamental question is how to glean samples from the statistical models. This question is especially important when the models are not equally descriptive or informative about the parameter, each being the most informative only for a specific regime of the parameter. This paper provides 1) an active sampling framework that specifies how the samples should be collected from different models over time in a data-adaptive fashion; 2) a stopping criterion specifying when the collected data is informative enough to form a reliable estimate for the covariate parameter; and 3) a terminal estimation rule. These rules, collectively, are shown to admit certain optimality guarantees. Numerical evaluations are provided to compare the performance with relevant existing approaches.

Consider a sequence of$n$random variables$\mathrm{X}\ {\buildrel \triangle\over=} (X_{1},\cdots, X_{n})$forming a random field (RF). X is assumed to be generated according to one of the two possible classes of probability measures$\mathcal{P}\ {\buildrel \triangle\over=}\ \{\mathbb{P}_{i}: i\in\{1,\cdots, m\}\}$and$\mathcal{Q}\ {\buildrel \triangle\over=}\ \{\mathbb{Q}_{i}: i\in\{1, \cdots, m\}\}$. Up to$s$realizations of each random variable$X_{i}$are available for sampling. This paper addresses the following two questions. 1) Given a target classification reliability, what is the minimum number of samples, on average, required to classify X? 2) What is an optimal sequence of sampling the random variables such that a classification decision can be formed with the fewest number of samples? This paper addresses these questions in the asymptote of large$n$.

Over the last decade, online forums have become primary news sources for readers around the globe, and social media platforms are the space where these news forums find most of their audience and engagement. Our particular focus in this paper is to study conflict dynamics over online news articles in Reddit, one of the most popular online discussion platforms. We choose to study how conflicts develop around news inside a discussion community, the \em r/news subreddit. Mining the characteristics of these engagements often provide useful insights into the behavioral dynamics of large-scale human interactions. Such insights are useful for many reasons -- for news houses to improvise their publishing strategies and potential audience, for data analytics to get a better introspection over media engagement as well as for social media platforms to avoid unnecessary and perilous conflicts. In this work, we present a novel quantification of conflict in online discussion. Unlike previous studies on conflict dynamics, which model conflict as a binary phenomenon, our measure is continuous-valued, which we validate with manually annotated ratings. We address a two-way prediction task. Firstly, we predict the probable degree of conflict a news article will face from its audience. We employ multiple machine learning frameworks for this task using various features extracted from news articles.Secondly, given a pair of users and their interaction history, we predict if their future engagement will result in a conflict. We fuse textual and network-based features together using a support vector machine which achieves an AUC of 0.89. Moreover, we implement a graph convolutional model which exploits engagement histories of users to predict whether a pair of users who never met each other before will have a conflicting interaction, with an AUC of 0.69. We perform our studies on a massive discussion dataset crawled from the Reddit news community, containing over $41k$ news articles and $5.5$ million comments. Apart from the prediction tasks, our studies offer interesting insights on the conflict dynamics -- how users form clusters based on conflicting engagements, how different is the temporal nature of conflict over different online news forums, how is contribution of different language based features to induce conflict, etc. In short, our study paves the way towards new methods of exploration and modeling of conflict dynamics inside online discussion communities.

Traditional forms of education are increasingly being replaced by online forms of learning. With many degrees being awarded without the requirement of co-location, it becomes necessary to build tools to enhance online learning interfaces. Online educational videos are often long and do not have enough metadata. Viewers trying to learn about a particular topic have to go through the entire video to find suitable content. We present a novel architecture to curate content tables for educational videos. We harvest text and acoustic properties of the videos to form a hierarchical content table (similar to a table of contents available in a textbook). We allow users to browse the video smartly by skipping to a particular portion rather than going through the entire video. We consider other text-based approaches as our baselines. We find that our approach beats the macro F1-score and micro F1-score of baseline by 39.45% and 35.76% respectively. We present our demo as an independent web page where the user can paste the URL of the video to obtain a generated hierarchical table of contents and navigate to the required content. In the spirit of reproducibility, we make our code public at https://goo.gl/Qzku9d and provide a screen cast to be viewed at https://goo.gl/4HSV1v.

In this paper we have developed an algorithm for many-objective optimization problems, which will work more quickly than existing ones, while offering competitive performance. The algorithm periodically reorders the objectives based on their conflict status and selects a subset of conflicting objectives for further processing. We have taken differential evolution multiobjective optimization (DEMO) as the underlying metaheuristic evolutionary algorithm, and implemented the technique of selecting a subset of conflicting objectives using a correlation-based ordering of objectives. The resultant method is called α-DEMO, where α is a parameter determining the number of conflicting objectives to be selected. We have also proposed a new form of elitism so as to restrict the number of higher ranked solutions that are selected in the next population. The α-DEMO with the revised elitism is referred to as α-DEMO-revised. Extensive results of the five DTLZ functions show that the number of objective computations required in the proposed algorithm is much less compared to the existing algorithms, while the convergence measures are competitive or often better. Statistical significance testing is also performed. A real-life application on structural optimization of factory shed truss is demonstrated.