Cloud Workload Prediction (CWP) is a critical task in cloud computing, essential for resource scheduling, performance optimization, and cost management. However, existing time series prediction methods struggle with instability and inefficiency when applied directly to cloud workloads due to their high variability and frequent fluctuations. To address these challenges, we propose DEL4CW, a novel D eep E xpansion L earning framework specifically designed for CWP . DEL4CW introduces a unique self-decoupling mechanism to disentangle the complex dependencies present in highly variable cloud workloads, leading to more accurate predictions of job arrival rates. The core contribution of DEL4CW lies in its ability to decouple cloud workload signals into three key components—trend, periodicity, and residuals—by treating these as hidden variables. This enables the model to better manage both short-term fluctuations and long-term workload trends. DEL4CW employs a deep expansion learning framework structured as stacked blocks, where each block includes dedicated modules for trend, periodicity, and compensation. Specifically, the trend module utilizes multi-layer fully connected networks to capture evolving trends at multiple granularities, while the periodicity module leverages multi-head attention to identify diverse periodic patterns. The compensation module addresses unpredictable, localized fluctuations, improving the model’s robustness to noise. In addition to its predictive accuracy, DEL4CW provides interpretable insights through its hierarchical design, allowing for layer-by-layer aggregation of meaningful partial predictions. This interpretability stems from the doubly residual learning pipeline, which ensures that each prediction block contributes progressively refined predictions. Extensive experiments on real-world cloud workload traces demonstrate that DEL4CW significantly outperforms existing baselines, with error reductions reaching up to 27.74% in certain scenarios.

As recommender systems are essential to various web domains such as e-commerce and web content sharing, providing equitable item exposure regardless of popularity becomes an imperative requirement. However, traditional fairness-aware approaches typically aim to achieve a better tradeoff between recommendation accuracy and fairness, and focus on improving the exposure rate of the long-tail items on static settings, evaluating fairness on one-shot recommendation decisions using logged data. Such methods overlook the dynamic nature of user preferences in real-world interactive environments. In contrast, our work seeks a win-win solution that simultaneously enhances recommendation accuracy and fairness over the long term, rather than merely trading off one against the other. To achieve this goal, we empirically demonstrate and analyze the spatiotemporal heterogeneity of user popularity preference. Our findings reveal complementary characteristics that, when fully exploited, can guide personalized strategies for long-term fairness. Building on this insight, we propose HER4IF, a novel hierarchical reinforcement learning framework designed for interactive recommendation. HER4IF decomposes the recommendation process into two key tasks: dynamic fairness control and item recommendation. The high-level agent continuously learns adaptive fairness constraints from evolving user popularity preferences, while the low-level agent refines recommendation policies under these personalized constraints. Extensive experiments on three real-world datasets and the interactive recommendation platform KuaiSim demonstrate that HER4IF significantly outperforms state-of-the-art methods, achieving substantial improvements in both fairness and recommendation accuracy. Our code is available at: https://github.com/1163710212/HER4IF .

As cloud services become increasingly integral to modern IT infrastructure, ensuring hardware reliability is essential to sustain high-quality service. Memory failures pose a significant threat to overall system stability, making accurate failure prediction through the analysis of memory error logs (i.e., Correctable Errors) imperative. Existing memory failure prediction approaches have notable limitations: rule-based expert models suffer from limited generalizability and low recall rates, while automated feature extraction methods exhibit suboptimal performance. To address these limitations, we propose M2-MFP: a Multi-scale and Multi-Level Memory Failure Prediction framework designed to enhance the reliability and availability of cloud infrastructure. M2-MFP converts correctable errors (CEs) into multi-level binary matrix representations and introduces a Binary Spatial Feature Extractor (BSFE) to automatically extract high-order features at both DIMM-level and bit-level. Building upon the BSFE outputs, we develop a dual-path temporal modeling architecture: 1) a time-patch module that aggregates multi-level features within observation windows, and 2) a time-point module that employs interpretable rule-generation trees trained on bit-level patterns. Experiments on both benchmark datasets and real-world deployment show the superiority of M2-MFP as it outperforms existing state-of-the-art methods by significant margins. Code and data are available at this repository: https://github.com/hwcloud-RAS/M2-MFP.

Reposting plays an essential role in boosting visibility on online social networks (OSNs). In this paper, we study the problem of designing “reposting service” in an OSN to incentivize “transactions” between requesters (users who seek to enhance visibility) and suppliers (users who are willing to repost if certain incentives are given), and maximize the welfare increase accumulated through a given time horizon. We formulate a mathematical model for reposting which captures various factors like click-through rates (CTRs), requesters’ valuations and suppliers’ costs. We formulate the problem of maximizing the welfare increase via judiciously assigning suppliers to requesters from two aspects: (a) “user-centric” and (b) “platform-centric”. The user-centric aspect deals with situations where requesters and suppliers collaborate and share valuations and costs. To address the challenge of unknown CTRs, we propose an online learning protocol and achieve a sub-linear regret. The platform-centric aspect corresponds to the scenario where users keep their valuations or costs private. To address the challenges of unknown CTRs, valuations and costs, we design an “explore-then-commit” online protocol. We prove the truthfulness of the proposed online protocol, and we also prove that this protocol has a sub-linear regret. Lastly, we conduct extensive experiments on six public datasets to evaluate the effectiveness and scalability of the proposed protocols.

It is a longstanding problem that Q-learning suffers from the overestimation bias. This issue originates from the fact that Q-learning uses the expectation of maximum Q-value to approximate the maximum expected Q-value. A number of algorithms, such as Double Q-learning, were proposed to address this problem by reducing the estimation of maximum Q-value, but this may lead to an underestimation bias. Note that this underestimation bias may have a larger performance penalty than the overestimation bias. Different from previous algorithms, this article studies this issue from a fresh perspective, i.e., meta-learning view, which leads to our Meta-Debias Q-learning. The main idea is to extract the maximum expected Q-value with meta-learning over multiple tasks to remove the estimation bias of maximum Q-value and help the agent choose the optimal action more accurately. However, there are two challenges: (1) How to automatically select suitable training tasks? (2) How to positively transfer the meta-knowledge from selected tasks to remove the estimation bias of maximum Q-value? To address the two challenges mentioned above, we quantify the similarity between the training tasks and the test task. This similarity enables us to select appropriate “partial” training tasks and helps the agent extract the maximum expected Q-value to remove the estimation bias. Extensive experiment results show that our Meta-Debias Q-learning outperforms SOTA baselines drastically in three evaluation indicators, i.e., maximum Q-value, policy, and reward. More specifically, our Meta-Debias Q-learning only underestimates \(1.2*10^{-3}\) than the maximum expected Q-value in the multi-armed bandit environment and only differs \(5.04\%-5\%=0.04\%\) than the optimal policy in the two states MDP environment. In addition, we compare the uniform weight and our similarity weight. Experiment results reveal fundamental insights into why our proposed algorithm outperforms in the maximum Q-value, policy, and reward.

Online rating system serves as an indispensable building block for many web applications. Previous studies showed that due to assimilate-contrast effects, historical ratings could significantly distort users' ratings, leading to low accuracy of product quality estimation and recommendation. To understand assimilate-contrast effects, an “accurate” model is still missing as previous models do not capture important factors like rating recency, selection bias, etc. Furthermore, an analytical framework to characterize product estimation accuracy under assimilate-contrast effects is also missing. This paper aims to fill in this gap. We propose a probabilistic model to quantify the aforementioned important factors on assimilate-contrast effects. We apply stochastic approximation theory to show that when the rating bias satisfies mild contraction conditions, the aggregate rating converges under aggregate opinion heterogeneity. We also apply non-stationary Markov chain theory to show that when the strength of assimilate-contrast satisfies mild stable conditions, the aggregate rating converges under rating recency. We also derive an equation to characterize the converged aggregate ratings. These conditions reveal important insights on how the aforementioned factors influence the convergence and guide the online rating system operator to design appropriate rating aggregation rules and rating displaying strategies. We apply it to rating prediction tasks and product recommendation tasks. Experiment results on four public datasets show that our model can improve the rating prediction and recommendation accuracy over previous models significantly, under various metrics like RMSE, NDCG, etc. We also demonstrate the flexibility of our model by showing that it can be applied to enhance other rating behavior models.

While personalization increases the utility of item recommendation, it also suffers from the issue of popularity bias. However, previous methods emphasize adopting supervised learning models to relieve popularity bias in the static recommendation, ignoring the dynamic transfer of user preference and amplification effects of the feedback loop in the recommender system (RS). In this paper, we focus on studying this issue in the interactive recommendation. We argue that diversification and novelty are both equally crucial for improving user satisfaction of IRS in the aforementioned setting. To achieve this goal, we propose a D iversity- N ovelty- a ware I nteractive R ecommendation framework (DNaIR) that augments offline reinforcement learning (RL) to increase the exposure rate of long-tail items with high quality. Its main idea is first to aggregate the item similarity, popularity, and quality into the reward model to help the planning of RL policy. It then designs a diversity-aware stochastic action generator to achieve an efficient and lightweight DNaIR algorithm. Extensive experiments are conducted on the three real-world datasets and an authentic RL environment (Virtual-Taobao). The experiments show that our model can better and full use of the long-tail items to improve recommendation satisfaction, especially those low popularity items with high-quality ones, thus achieving state-of-the-art performance.

Template mining is one of the foundational tasks to support log analysis, which supports the diagnosis and troubleshooting of large scale Web applications. This paper develops a human-in-the-loop template mining framework to support interactive log analysis, which is highly desirable in real-world diagnosis or troubleshooting of Web applications but yet previous template mining algorithms fail to support it. We formulate three types of light-weight user feedback and based on them we design three atomic human-in-the-loop template mining algorithms. We derive mild conditions under which the outputs of our proposed algorithms are provably correct. We also derive upper bounds on the computational complexity and query complexity of each algorithm. We demonstrate the versatility of our proposed algorithms by combining them to improve the template mining accuracy of five representative algorithms over sixteen widely used benchmark datasets.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by theslow convergencerate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient “unbiased sampling” schemes, and we also design two variant algorithms which can reduce sampling cost and speed up the convergence. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms; and to achieve the same estimation accuracy, our approach reduces the query cost significantly. Last, we use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Random walk sampling is often used to conduct statistical estimation over graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. Our bias reduction algorithm only utilizes a small number of valid sub-samples, which can reduce more bias of the estimator but may increase the variance of the estimator significantly. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. We provide theoretical guarantees and computational complexity analysis of our proposed bias reduction algorithms. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. Extensive experiments on four public datasets confirm the effectiveness and computational efficiency of our proposed algorithmic framework under the mean square metric and beyond.

Contextual bandit serves as an invaluable tool to balance theexploration vs. exploitationtradeoff in various applications such as online recommendation. In many applications,heterogeneous information networks(HINs) provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this article, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users’ preference over items, the target of our online learning, are closely related to users’ preference over meta-paths. However, it is unknown which meta-path a user prefers more. Thus, both preferences are needed to be learned in an online fashion with exploration vs. exploitation tradeoff balanced. We propose the HIN-assisted upper confidence bound (HUCB) algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendations by leveraging the relationship captured in this meta-path. A bandit master is then employed to learn users’ preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration vs. exploitation tradeoff. We theoretically prove that the HUCB algorithm can achieve similar performance compared with the optimal algorithm where each user is served according to his true preference over meta-paths (assuming the optimal algorithm knows the preference). Moreover, we prove that the HUCB algorithm benefits from leveraging HIN in achieving a smaller regret upper bound than the baseline algorithm without leveraging HIN. Experimental results on a synthetic dataset, as well as real datasets from LastFM and Yelp demonstrate the fast learning speed of the HUCB algorithm.

In the past few years, many companies are considering “social recommendation” for their businesses, e.g., firms are offering rewards to customers who recommend the firms’ products/services in online social networks (OSNs). However, the pros and cons of such social recommendation scheme are still unclear. Thus, it is difficult for firms to design rewarding schemes, and for OSN platforms to design regulating policies. By analyzing real data from Weixin and Yelp, we first identify key factors that affect the spreading of products/services in OSNs. These findings enable us to develop an accurate (i.e., with a high validation accuracy) mathematical model on social recommendations. Our model captures how users decide whether to recommend an item, which is a key factor but often ignored by previous social recommendation models such as the “Independent Cascade model”. We also design algorithms to infer model parameters. Using our model, we uncover conditions when social recommendation improves a firm’s profit and users’ utilities, as well as when it cannot improve the profit or hurts users’ utilities. These conditions help the design of both rewarding schemes and regulating policies. Moreover, we extend our model to a dynamic setting, so that a firm can improve its profit by dynamically optimizing its rewarding schemes.

In online social networks (OSNs), users may want to enhance their social visibility, as it can make their contents, i.e., opinions, videos, pictures, etc., attract attention from more users. Motivated by this, we propose a mechanism, where the OSN operator provides a "social visibility boosting service" to incentivize "transactions" between requesters (users who seek to enhance their social visibility via adding new "neighbors") and suppliers (users who are willing to be added as a new "neighbor" of any requester when certain "rewards" is provided). We design a posted pricing scheme for the OSN provider to charge the requesters who use such boosting service, and reward the suppliers who contribute to such boosting service. The OSN operator keeps a fraction of the payment from requesters and distributes the remaining part to participating suppliers "fairly" via a scheme based on the Shapley value. The objective of the OSN provider is to select the price and supplier set to maximize the revenue under the budget constraint of requesters. We first show that the revenue maximization problem is not simpler than an NP-hard problem. We then decompose it into two subroutines, prove the hardness of each sub-routine, and eventually design computationally efficient approximation algorithms to solve the revenue maximization problem. We conduct extensive experiments to evaluate our proposed algorithms.

Graphs are commonly used in various applications such as online social networks (OSNs), E-commerce systems and social recommender systems. Random walk sampling is often used to conduct statistical estimation over such graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. A new feature of this bias reduction algorithm is that it allows the variance to increase whenever the bias can be further reduced. The increased variance may lead to a large mean square error of the estimator. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. Our algorithmic framework enables one to attain different trade-offs between the sample complexity (i.e., number of parallel random walks) and the mean square error of the statistical estimation. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. To demonstrate the versatility of the framework, we apply it to optimize the Metropolis random walk and simple random walk sampling. Extensive experiments confirm the effectiveness and efficiency of our proposed algorithmic framework.

Contextual bandit serves as an invaluable tool to balance the exploration vs. exploitation trade-off in various applications like online recommendation. In many applications, heterogeneous information network (HIN) can be derived to provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this paper, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users' preference over items, the target of our online learning, are closely related to users' preference over meta-paths, however it is unknown which meta-path a user prefers more. We propose the HUCB algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendation by leveraging the relationship captured in this meta-path. The bandit master is then employed to learn users' preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration-exploitation trade-off. Experimental results on real datasets from LastFM and Yelp demonstrate the efficacy of the HUCB algorithm.

Online social network (OSN) is an ideal venue to enhance one's visibility. This paper considers how a user (called requester) in an OSN selects a small number of available users and invites them as new friends/followers so as to maximize his "social visibility". More importantly, the requester has to do this under the anonymity setting, which means he is not allowed to know the neighborhood information of these available users in the OSN. In this paper, we first develop a mathematical model to quantify the social visibility and formulate the problem of visibility maximization with anonymity guarantee, abbreviated as "VisMAX-A". Then we design an algorithmic framework named as "AdaExp", which adaptively expands the requester's visibility in multiple rounds. In each round of the expansion, AdaExp uses a query oracle with anonymity guarantee to select only one available user. By using probabilistic data structures like the k-minimum values (KMV) sketch, we design an efficient query oracle with anonymity guarantees. We also conduct experiments on real-world social networks and validate the effectiveness of our algorithms.

Utilizing offline logged data to improve sequential or online decision making is drawing more and more attention. VirUCB is one of the latest notable algorithmic framework in this research line, and it has both sound theoretical guarantee and nice empirical performance. However, regarding VirUCB, it is still unclear: (1) how imbalanced offline logged data influences the decision making accuracy; (2) how to schedule offline logged data across the decision making horizon so as to reduce offline logged data consumption. We show that with imbalanced offline logged data, VirUCB can have a learning speed slower than the baseline algorithm without offline logged data. This finding inspires us to design RobVirUCB algorithm, which is robust against such imbalanced data, i.e., still maintains a fast learning speed. RobVirUCB adaptively selects “useful” offline logged data to speed up learning and it has theoretical guarantees on regret. Finally, we design EffVirUCB algorithm, which reduces offline logged data consumption of RobVirUCB. EffVirUCB schedules the offline logged data to the decision round that the decision maker may select suboptimal arms and it has theoretical guarantees on regret. Extensive experiments on both synthetic data and real-world data validate the superior performance of RobVirUCB and EffVirUCB.

Online rating system serves as an indispensable building block for many web applications such as Amazon, TripAdvior and Yelp. It enables production quality estimation via aggregate ratings (a.k.a. wisdom of the crowd) as well as product recommendation via inferring user preference from ratings, etc. Previous studies showed that due to assimilate-contrast effects, historical ratings can significantly distort user's ratings, leading to low accuracy of product quality estimation and recommendation. To understand assimilate-contrast effects, an "accurate'' model is still missing as previous models do not capture important factors like rating recency, selection bias, etc. Furthermore, an analytical framework to characterize product estimation accuracy under assimilate-contrast effects is also missing. This paper aims to fill in this gap. We propose a mathematical model to quantify the aforementioned important factors on assimilate-contrast effects. Our model attains a good balance between model complexity and model accuracy, such that it is neat enough for us to develop an analytical framework to study assimilate-contrast effects. Based on our model, we derive sufficient conditions, under which the product estimation and collective opinion converges to the "ground-truth''. These conditions reveal important insights on how the aforementioned factors influence the convergence and guide the online rating system operator to design appropriate rating aggregation rules and rating displaying strategies. To demonstrate the versatility of our model, we apply to rating prediction tasks and product recommendation tasks. Experiment results on four public datasets show that our model can improve the rating prediction and and recommendation accuracy over previous models significantly.

A fundamental question for companies with large amount of logged data is: How to use such logged data together with incoming streaming data to make good decisions? Many companies currently make decisions via online A/B tests, but wrong decisions during testing hurt users’ experiences and cause irreversible damage. A typical alternative is offline causal inference, which analyzes logged data alone to make decisions. However, these decisions are not adaptive to the new incoming data, and so a wrong decision will continuously hurt users’ experiences. To overcome the aforementioned limitations, we propose a framework to unify offline causal inference algorithms (e.g., weighting, matching) and online learning algorithms (e.g., UCB, LinUCB). We propose novel algorithms and derive bounds on the decision accuracy via the notion of “regret”. We derive the first upper regret bound for forest-based online bandit algorithms. Experiments on two real datasets show that our algorithms outperform other algorithms that use only logged data or online feedbacks, or algorithms that do not use the data properly.

Finding the set of most influential users in online social networks (OSNs) to trigger the largest influence cascade is meaningful, e.g., companies may leverage the “word-of-mouth” effect to trigger a large cascade of purchases by offering free samples/discounts to those most influential users. This task is usually modeled as an influence maximization problem, and it has been widely studied in the past decade. However, considering that users in OSNs may participate in various online activities, e.g., joining discussion groups and commenting on same pages or products, influence diffusion through online activities becomes even more significant. In this article, we study the impact of online activities by formulating social-activity networks which contain both users and online activities, and thus induce two types of weighted edges, i.e., edges between users and edges between users and activities. To address the computation challenge, we define an influence centrality via random walks, and use the Monte Carlo framework to efficiently estimate the centrality. Furthermore, we develop a greedy-based algorithm with novel optimizations to find the most influential users for node recommendation. Experiments on real-world datasets show that our approach is very computationally efficient under different influence models, and also achieves larger influence spread by considering online activities.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google Play Store, and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “ message-based persuasion ” lead to “ biased ” product ratings in a cascading manner (we call this the persuasion cascade ). This article investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on both synthetic data and real-world data from Amazon and TripAdvisor. Experiment results show that our inference algorithm has a high accuracy. Furthermore, persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

Online rating systems are often used in numerous web or mobile applications, e.g., Amazon and TripAdvisor, to assess the ground-truth quality of products. Due to herding effects, the aggregation of historical ratings (or historical collective opinion) can significantly influence subsequent ratings, leading to misleading and erroneous assessments. We study how to manage product ratings via rating aggregation rules and shortlisted representative reviews, for the purpose of correcting the assessment error. We first develop a mathematical model to characterize important factors of herding effects in product ratings. We then identify sufficient conditions (via the stochastic approximation theory), under which the historical collective opinion converges to the ground-truth collective opinion of the whole user population. These conditions identify a class of rating aggregation rules and review selection mechanisms that can reveal the ground-truth product quality. We also quantify the speed of convergence (via the martingale theory), which reflects the efficiency of rating aggregation rules and review selection mechanisms. We prove that the herding effects slow down the speed of convergence while an accurate review selection mechanism can speed it up.

Contextual bandit algorithms provide principled online learning solutions to balance the exploitation-exploration trade-off in various applications such as recommender systems. However, the learning speed of the traditional contextual bandit algorithms is often slow due to the need for extensive exploration. This poses a critical issue in applications like recommender systems, since users may need to provide feedbacks on a lot of uninterested items. To accelerate the learning speed, we generalize contextual bandit to conversational contextual bandit. Conversational contextual bandit leverages not only behavioral feedbacks on arms (e.g., articles in news recommendation), but also occasional conversational feedbacks on key-terms from the user. Here, a key-term can relate to a subset of arms, for example, a category of articles in news recommendation. We then design the Conversational UCB algorithm (ConUCB) to address two challenges in conversational contextual bandit: (1) which key-terms to select to conduct conversation, (2) how to leverage conversational feedbacks to accelerate the speed of bandit learning. We theoretically prove that ConUCB can achieve a smaller regret upper bound than the traditional contextual bandit algorithm LinUCB, which implies a faster learning speed. Experiments on synthetic data, as well as real datasets from Yelp and Toutiao, demonstrate the efficacy of the ConUCB algorithm.

“Unbiasedness,” which is an important property to ensure that users’ ratings indeed reflect their true evaluations of products, is vital both in shaping consumer purchase decisions and providing reliable recommendations in online rating systems. Recent experimental studies showed that distortions from historical ratings would ruin the unbiasedness of subsequent ratings. How to “discover” historical distortions in each single rating (or at the micro-level), and perform the “debiasing operations” are our main objective. Using 42M real customer ratings, we first show that users either “assimilate” or “contrast” to historical ratings under different scenarios, which can be further explained by a well-known psychological argument: the “Assimilate-Contrast” theory. This motivates us to propose the Historical Influence Aware Latent Factor Model (HIALF), the “first” model for real rating systems to capture and mitigate historical distortions in each single rating. HIALF allows us to study the influence patterns of historical ratings from a modelling perspective, which perfectly matches the assimilation and contrast effects observed in experiments. Moreover, HIALF achieves significant improvements in predicting subsequent ratings and characterizing relationships in ratings. It also contributes to better recommendations, wiser consumer purchase decisions, and deeper understanding of historical distortions in both honest rating and misbehaving rating settings.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow convergence rate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient "unbiased sampling" schemes. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms. Furthermore, to achieve the same estimation accuracy, our approach reduces the query cost (a measure of sampling budget) significantly. Lastly, we also use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Firms are now considering to offer rewards to customers who recommend the firms' products/services in online social networks (OSN). However, the pros and cons of such social recommendation scheme are still unclear. Thus, it is difficult for firms to design rewarding schemes. Via empirical analysis of data, we first identify key factors that affect the spreading of a firm's product in OSNs. These findings enable us to develop an accurate (i.e., with a high validation accuracy) mathematical model on social recommendations. In particular, our model captures how users decide whether to recommend an item, which is a key factor but often ignored by previous social recommendation models such as the "Independent Cascade model". We also design algorithms to infer model parameters. Using these parameters in our model, we uncover conditions when social recommendation can (or cannot) improves a firm's profit. These conditions help a firm to design rewarding schemes. Finally, we extend our model to an online setting and design reinforcement learning algorithms for a firm to dynamically optimize its rewarding schemes.

Reputation systems have become an indispensable component of modern E-commerce systems, as they help buyers make informed decisions in choosing trustworthy sellers. To attract buyers and increase the transaction volume, sellers need to earn reasonably high reputation scores. This process usually takes a substantial amount of time. To accelerate this process, sellers can provide price discounts to attract users, but the underlying difficulty is that sellers have no prior knowledge on buyers’ preferences over price discounts. In this article, we develop an online algorithm to infer the optimal discount rate from data. We first formulate an optimization framework to select the optimal discount rate given buyers’ discount preferences, which is a tradeoff between the short-term profit and the ramp-up time (for reputation). We then derive the closed-form optimal discount rate, which gives us key insights in applying a stochastic bandits framework to infer the optimal discount rate from the transaction data with regret upper bounds. We show that the computational complexity of evaluating the performance metrics is infeasibly high, and therefore, we develop efficient randomized algorithms with guaranteed performance to approximate them. Finally, we conduct experiments on a dataset crawled from eBay. Experimental results show that our framework can trade 60% of the short-term profit for reducing the ramp-up time by 40%. This reduction in the ramp-up time can increase the long-term profit of a seller by at least 20%.

Product bundling is widely adopted for information goods and online services because it can increase profit for companies. For example, cable companies often bundle Internet access and video streaming services together. However, it is challenging to obtain an optimal bundling strategy, not only because it is computationally expensive, but also that customers’ private information (e.g., valuations for products) is needed for the decision, and we need to infer it from accessible datasets. As customers’ purchasing data are getting richer due to the popularity of online shopping, doors are open for us to infer this information. This paper aims to address: (1) How to infer customers’ valuations from the purchasing data? (2) How to determine the optimal product bundle to maximize the profit? We first formulate a profit maximization framework to select the optimal bundle set. We show that finding the optimal bundle set is NPhard. We then identify key factors that impact the profitability of product bundling. These findings give us insights to develop a computationally efficient algorithm to approximate the optimal product bundle with a provable performance guarantee. To obtain the input of the bundling algorithm, we infer the distribution of customers’ valuations from their purchasing data, based on which we run our bundling algorithm and conduct experiments on an Amazon co-purchasing dataset. We extensively evaluate the accuracy of our inference and the bundling algorithm. Our results reveal conditions under which bundling is highly profitable and provide insights to guide the deployment of product bundling.

Online reputation systems serve as core building blocks in various Internet services such as E-commerce (e.g. eBay) and crowdsourcing (e.g., oDesk). The flaws of real-world online reputation systems were reported extensively. Users who are frustrated about the system will eventually abandon such service. However, no formal studies have explored such flaws. This paper presents the first attempt, which develops a novel data analytical framework to uncover online reputation system deficiencies from data. We develop a novel measure to quantify the efficiency of online reputation systems, i.e., ramp up time of a new service provider. We first show that inherent preferences or personal biases in assigning feedbacks (or ratings) cause the computational infeasibility in evaluating online reputation systems from data. We develop a computationally efficient randomized algorithm with theoretical performance guarantees to address this computational challenge. We apply our methodology to real-life datasets (from eBay and Google Helpouts), we discover that the ramp up time in eBay and Google Helpouts are around 791 and 1,327 days respectively. Around 78.7% sellers have ramped up in eBay and only 1.5% workers have ramped up in Google Helpouts. This small fraction and the long ramp up time (1,327 days) explain why Google Helpouts was eventually shut down in April 2015.

Many Web services like Amazon, Epinions, and TripAdvisor provide historical product ratings so that users can evaluate the quality of products. Product ratings are important because they affect how well a product will be adopted by the market. The challenge is that we only have partial information on these ratings: each user assigns ratings to only a small subset of products. Under this partial information setting, we explore a number of fundamental questions. What is the minimum number of ratings a product needs so that one can make a reliable evaluation of its quality? How may users’ misbehavior, such as cheating in product rating, affect the evaluation result? To answer these questions, we present a probabilistic model to capture various important factors (e.g., rating aggregation rules, rating behavior) that may influence the product quality assessment under the partial information setting. We derive the minimum number of ratings needed to produce a reliable indicator on the quality of a product. We extend our model to accommodate users’ misbehavior in product rating. We derive the maximum fraction of misbehaving users that a rating aggregation rule can tolerate and the minimum number of ratings needed to compensate. We carry out experiments using both synthetic and real-world data (from Amazon and TripAdvisor). We not only validate our model but also show that the “average rating rule” produces more reliable and robust product quality assessments than the “majority rating rule” and the “median rating rule” in aggregating product ratings. Last, we perform experiments on two movie rating datasets (from Flixster and Netflix) to demonstrate how to apply our framework to improve the applications of recommender systems.

Given the globalized economy, how to process the heterogeneous web data so to extract customers' purchase behavior is crucial to manufacturers who want to enter or sustain in a competitive market. To maximize the sales, manufacturers not only need to decide what products to produce so to meet diverse customers' requirements, but at the same time, compete with competitors' products. In this paper, we present a general framework for the following product selection problems: (1) k-BSP problem, which is for a manufacturer to enter a competitive market, and (2) k-BBP problem, which is for a manufacturer to sustain in a competitive market. We propose several product adoption models to describe the complex purchase behavior of customers, and formally show that these problems are NP-hard in general. To tackle these problems, we propose computationally efficient greedy-based approximation algorithms. Based on the submodularity analysis, we prove that our algorithms can guarantee a (1--1/e)-approximation ratio as compared to the optimal solutions. We perform large scale data analysis to show the efficiency and accuracy of our framework. In our experiments, we observe 1,300 to 250,000 times speedup as compared to the exhaustive algorithms, and our solutions can achieve on average 96% of solution quality as compared to the optimal solutions. Finally, we apply our algorithms on web dataset to show the impact of customers' different purchase behavior on the results of product selection.