More Like this

1. Towards Return Parity in Markov Decision Processes

   Chi, J.; Shen, J.; Dai, X.; Zhang, W; Tian, Y.; Zhao, H. (March 2022, 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022))

   Algorithmic decisions made by machine learning models in high-stakes domains may have lasting impacts over time. However, naive applications of standard fairness criterion in static settings over temporal domains may lead to delayed and adverse effects. To understand the dynamics of performance disparity, we study a fairness problem in Markov decision processes (MDPs). Specifically, we propose return parity, a fairness notion that requires MDPs from different demographic groups that share the same state and action spaces to achieve approximately the same expected time-discounted rewards. We first provide a decomposition theorem for return disparity, which decomposes the return disparity of any two MDPs sharing the same state and action spaces into the distance between group-wise reward functions, the discrepancy of group policies, and the discrepancy between state visitation distributions induced by the group policies. Motivated by our decomposition theorem, we propose algorithms to mitigate return disparity via learning a shared group policy with state visitation distributional alignment using integral probability metrics. We conduct experiments to corroborate our results, showing that the proposed algorithm can successfully close the disparity gap while maintaining the performance of policies on two real-world recommender system benchmark datasets. 

   more » « less
2. Bayesian function registration with random truncation

   https://doi.org/10.1371/journal.pone.0287734  

   Lu, Yi; Herbei, Radu; Kurtek, Sebastian (July 2023, PLOS ONE)

   Yang, Junyuan (Ed.)

   In this work, we develop a new set of Bayesian models to perform registration of real-valued functions. A Gaussian process prior is assigned to the parameter space of time warping functions, and a Markov chain Monte Carlo (MCMC) algorithm is utilized to explore the posterior distribution. While the proposed model can be defined on the infinite-dimensional function space in theory, dimension reduction is needed in practice because one cannot store an infinite-dimensional function on the computer. Existing Bayesian models often rely on some pre-specified, fixed truncation rule to achieve dimension reduction, either by fixing the grid size or the number of basis functions used to represent a functional object. In comparison, the new models in this paper randomize the truncation rule. Benefits of the new models include the ability to make inference on the smoothness of the functional parameters, a data-informative feature of the truncation rule, and the flexibility to control the amount of shape-alteration in the registration process. For instance, using both simulated and real data, we show that when the observed functions exhibit more local features, the posterior distribution on the warping functions automatically concentrates on a larger number of basis functions. Supporting materials including code and data to perform registration and reproduce some of the results presented herein are available online. 

   more » « less
3. Distributed Bayesian Varying Coefficient Modeling Using a Gaussian Process Prior

   Guhaniyogi, R.; Li, C.; Savitsky, T.D.; Srivastava, S. (May 2022, Journal of machine learning research)

   McCulloch, R. (Ed.)

   Varying coefficient models (VCMs) are widely used for estimating nonlinear regression functions for functional data. Their Bayesian variants using Gaussian process priors on the functional coefficients, however, have received limited attention in massive data applications, mainly due to the prohibitively slow posterior computations using Markov chain Monte Carlo (MCMC) algorithms. We address this problem using a divide-and-conquer Bayesian approach. We first create a large number of data subsamples with much smaller sizes. Then, we formulate the VCM as a linear mixed-effects model and develop a data augmentation algorithm for obtaining MCMC draws on all the subsets in parallel. Finally, we aggregate the MCMC-based estimates of subset posteriors into a single Aggregated Monte Carlo (AMC) posterior, which is used as a computationally efficient alternative to the true posterior distribution. Theoretically, we derive minimax optimal posterior convergence rates for the AMC posteriors of both the varying coefficients and the mean regression function. We provide quantification on the orders of subset sample sizes and the number of subsets. The empirical results show that the combination schemes that satisfy our theoretical assumptions, including the AMC posterior, have better estimation performance than their main competitors across diverse simulations and in a real data analysis. 

   more » « less
4. Stochastic Communication and Motion Planning via Learned Abstract World Representations

   Dadvar, Mehdi; Majd, Keyvan; Fainekos, Georgios; Srivastava, Siddharth (September 2025, CoRL)

   The increasing deployment of robots alongside humans necessitates sophisticated communication and motion planning to ensure safety and task achievability in social navigation scenarios. Existing methods often rely heavily on historical data and extensive expert hand-coding, which limits their scalability and generalizability. This paper introduces a novel framework that models social navigation as a Markov Decision Process (MDP), utilizing Conditional Abstraction Trees (CATs) to learn dynamic abstract world representations and policies that focus on critical aspects of interaction. In the offline phase, the framework operates within a simulator, while in the online phase, it deploys the learned representations and policies in real-world scenarios for ongoing refinement and adaptation. Integral to our approach is a Dynamic Bayesian Network (DBN) based human sensor and belief model that accounts for humans’ imperfect perception to enhance the prediction of human motion. We evaluated our method through extensive simulations and user studies involving physical experiments, demonstrating its effectiveness in managing critical interactions and ensuring safety and task completion across various scenarios. 

   more » « less
5. Near-Optimal Offline Reinforcement Learning via Double Variance Reduction

   Yin, Ming; Bai, Yu; Wang, Yu-Xiang (December 2021, Advances in neural information processing systems)

   We consider the problem of offline reinforcement learning (RL) -- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open even in basic settings such as \emph{tabular} Markov Decision Processes (MDPs). In this paper, we propose Off-Policy Double Variance Reduction (OPDVR), a new variance reduction based algorithm for offline RL. Our main result shows that OPDVR provably identifies an ϵ-optimal policy with O˜(H2/dmϵ2) episodes of offline data in the finite-horizon stationary transition setting, where H is the horizon length and dm is the minimal marginal state-action distribution induced by the behavior policy. This improves over the best known upper bound by a factor of H. Moreover, we establish an information-theoretic lower bound of Ω(H2/dmϵ2) which certifies that OPDVR is optimal up to logarithmic factors. Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards. 

   more » « less