• ### Complete Submodularity Characterization in the Comparative Independent Cascade Model(1702.05218)

Nov. 14, 2018 cs.SI, cs.DS
We study the propagation of comparative ideas or items in social networks. A full characterization for submodularity in the comparative independent cascade (Com-IC) model of two-idea cascade is given, for competing ideas and complementary ideas respectively, with or without reconsideration. We further introduce One-Shot model where agents show less patience toward ideas, and show that in One-Shot model, only the strongest idea spreads with submodularity.
• ### Weighted estimates for the multilinear maximal function on the upper half-spaces(1705.04939)

Aug. 24, 2018 math.AP
For a general dyadic grid, we give a Calder\'{o}n-Zygmund type decomposition, which is the principle fact about the multilinear maximal function $\mathfrak{M}$ on the upper half-spaces. Using the decomposition, we study the boundedness of $\mathfrak{M}.$ We obtain a natural extension to the multilinear setting of Muckenhoupt's weak-type characterization. We also partially obtain characterizations of Muckenhoupt's strong-type inequalities with one weight. Assuming the reverse H\"{o}lder's condition, we get a multilinear analogue of Sawyer's two weight theorem. Moreover, we also get Hyt\"{o}nen-P\'{e}rez type weighted estimates.
• ### Combinatorial Multi-Armed Bandit with General Reward Functions(1610.06603)

July 20, 2018 cs.DS, cs.LG, stat.ML
In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the $\max()$ function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve $O(\log{T})$ distribution-dependent regret and $\tilde{O}(\sqrt{T})$ distribution-independent regret, where $T$ is the time horizon. We apply our results to the $K$-MAX problem and expected utility maximization problems. In particular, for $K$-MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first $\tilde{O}(\sqrt T)$ bound on the $(1-\epsilon)$-approximation regret of its online problem, for any $\epsilon>0$.
• ### Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity(1805.04436)

May 11, 2018 cs.GT, cs.DS
We introduce two new "degree of complementarity" measures, which we refer to, respectively, as supermodular width and superadditive width. Both are formulated based on natural witnesses of complementarity. We show that both measures are robust by proving that they, respectively, characterize the gap of monotone set functions from being submodular and subadditive. Thus, they define two new hierarchies over monotone set functions, which we will refer to as Supermodular Width (SMW) hierarchy and Superadditive Width (SAW) hierarchy, with level 0 of the hierarchies resting exactly on submodular and subadditive functions, respectively. We present a comprehensive comparative analysis of the SMW hierarchy and the Supermodular Degree (SD) hierarchy, defined by Feige and Izsak. We prove that the SMW hierarchy is strictly more expressive than the SD hierarchy. We show that previous results regarding approximation guarantees for welfare and constrained maximization as well as regarding the Price of Anarchy (PoA) of simple auctions can be extended without any loss from the SD hierarchy to the SMW hierarchy. We also establish almost matching information-theoretical lower bounds. The combination of these approximation and hardness results illustrate that the SMW hierarchy provides an accurate characterization of "near submodularity" needed for maximization approximation. While SD and SMW hierarchies support nontrivial bounds on the PoA of simple auctions, we show that our SAW hierarchy seems to capture more intrinsic properties needed to realize the efficiency of simple auctions. So far, the SAW hierarchy provides the best dependency for the PoA of Single-bid Auction, and is nearly as competitive as the Maximum over Positive Hypergraphs (MPH) hierarchy for Simultaneous Item First Price Auction (SIA). We provide almost tight lower bounds for the PoA of both auctions with respect to the SAW hierarchy.
• ### A Transfer Learning Approach for Microstructure Reconstruction and Structure-property Predictions(1805.02784)

Stochastic microstructure reconstruction has become an indispensable part of computational materials science, but ongoing developments are specific to particular material systems. In this paper, we address this generality problem by presenting a transfer learning-based approach for microstructure reconstruction and structure-property predictions that is applicable to a wide range of material systems. The proposed approach incorporates an encoder-decoder process and feature-matching optimization using a deep convolutional network. For microstructure reconstruction, model pruning is implemented in order to study the correlation between the microstructural features and hierarchical layers within the deep convolutional network. Knowledge obtained in model pruning is then leveraged in the development of a structure-property predictive model to determine the network architecture and initialization conditions. The generality of the approach is demonstrated numerically for a wide range of material microstructures with geometrical characteristics of varying complexity. Unlike previous approaches that only apply to specific material systems or require a significant amount of prior knowledge in model selection and hyper-parameter tuning, the present approach provides an off-the-shelf solution to handle complex microstructures, and has the potential of expediting the discovery of new materials.
• ### Microstructural Materials Design via Deep Adversarial Learning Methodology(1805.02791)

Identifying the key microstructure representations is crucial for Computational Materials Design (CMD). However, existing microstructure characterization and reconstruction (MCR) techniques have limitations to be applied for materials design. Model-based MCR approaches do not have parameters that can serve as design variables, while MCR techniques that rely on dimension reduction tend to lose important microstructural information. In this work, we present a deep adversarial learning methodology that overcomes the limitations of existing MCR techniques. In the proposed methodology, generative adversarial networks (GAN) are trained to learn the mapping between latent variables and microstructures. Thereafter, the low-dimensional latent variables serve as design variables, and a Bayesian optimization framework is applied to obtain microstructures with desired material property. Due to the special design of the network architecture, the proposed methodology is able to identify the latent (design) variables with desired dimensionality, as well as minimize the information loss even for complex material microstructures. The validity of the proposed methodology is tested numerically on a synthetic microstructure dataset and its effectiveness for materials design is evaluated through a case study of optimizing optical performance for energy absorption. In addition, the scalability and transferability of proposed methodology are also demonstrated in this work. Specifically, the proposed methodology is scalable to generate arbitrary sized microstructures, and it can serve as a pre-trained model to improve the performance of a structure-property predictive model via transfer learning.
• ### Differential Equations for Modeling Asynchronous Algorithms(1805.02991)

May 8, 2018 cs.LG, stat.ML
Asynchronous stochastic gradient descent (ASGD) is a popular parallel optimization algorithm in machine learning. Most theoretical analysis on ASGD take a discrete view and prove upper bounds for their convergence rates. However, the discrete view has its intrinsic limitations: there is no characterization of the optimization path and the proof techniques are induction-based and thus usually complicated. Inspired by the recent successful adoptions of stochastic differential equations (SDE) to the theoretical analysis of SGD, in this paper, we study the continuous approximation of ASGD by using stochastic differential delay equations (SDDE). We introduce the approximation method and study the approximation error. Then we conduct theoretical analysis on the convergence rates of ASGD algorithm based on the continuous approximation. There are two methods: moment estimation and energy function minimization can be used to analyze the convergence rates. Moment estimation depends on the specific form of the loss function, while energy function minimization only leverages the convex property of the loss function, and does not depend on its specific form. In addition to the convergence analysis, the continuous view also helps us derive better convergence rates. All of this clearly shows the advantage of taking the continuous view in gradient descent algorithms.
• ### Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications (Extended Version)(1805.01685)

May 4, 2018 cs.LG, stat.ML
We study the Combinatorial Pure Exploration problem with Continuous and Separable reward functions (CPE-CS) in the stochastic multi-armed bandit setting. In a CPE-CS instance, we are given several stochastic arms with unknown distributions, as well as a collection of possible decisions. Each decision has a reward according to the distributions of arms. The goal is to identify the decision with the maximum reward, using as few arm samples as possible. The problem generalizes the combinatorial pure exploration problem with linear rewards, which has attracted significant attention in recent years. In this paper, we propose an adaptive learning algorithm for the CPE-CS problem, and analyze its sample complexity. In particular, we introduce a new hardness measure called the consistent optimality hardness, and give both the upper and lower bounds of sample complexity. Moreover, we give examples to demonstrate that our solution has the capacity to deal with non-linear reward functions.
• ### Spontaneous symmetry breaking and trapping of temporal Kerr cavity solitons by pulsed or amplitude modulated driving fields(1803.10203)

May 2, 2018 physics.optics
We report on a systematic study of temporal Kerr cavity soliton dynamics in the presence of pulsed or amplitude modulated driving fields. In stark contrast to the more extensively studied case of phase modulations, we find that Kerr cavity solitons are not always attracted to maxima or minima of driving field amplitude inhomogeneities. Instead, we find that the solitons are attracted to temporal positions associated with specific driving field values that depend only on the cavity detuning. We describe our findings in light of a spontaneous symmetry breaking instability that physically ensues from a competition between coherent driving and nonlinear propagation effects. In addition to identifying a new type of Kerr cavity soliton behaviour, our results provide valuable insights to practical cavity configurations employing pulsed or amplitude modulated driving fields.
• ### Unsupervised Neural Machine Translation with Weight Sharing(1804.09057)

April 24, 2018 cs.CL
Unsupervised neural machine translation (NMT) is a recently proposed approach for machine translation which aims to train the model without using any labeled data. The models proposed for unsupervised NMT often use only one shared encoder to map the pairs of sentences from different languages to a shared-latent space, which is weak in keeping the unique and internal characteristics of each language, such as the style, terminology, and sentence structure. To address this issue, we introduce an extension by utilizing two independent encoders but sharing some partial weights which are responsible for extracting high-level representations of the input sentences. Besides, two different generative adversarial networks (GANs), namely the local GAN and global GAN, are proposed to enhance the cross-language translation. With this new approach, we achieve significant improvements on English-German, English-French and Chinese-to-English translation tasks.
• ### Optimizing Neural Networks in the Equivalence Class Space(1802.03713)

April 18, 2018 cs.LG, stat.ML
It has been widely observed that many activation functions and pooling methods of neural network models have (positive-) rescaling-invariant property, including ReLU, PReLU, max-pooling, and average pooling, which makes fully-connected neural networks (FNNs) and convolutional neural networks (CNNs) invariant to (positive) rescaling operation across layers. This may cause unneglectable problems with their optimization: (1) different NN models could be equivalent, but their gradients can be very different from each other; (2) it can be proven that the loss functions may have many spurious critical points in the redundant weight space. To tackle these problems, in this paper, we first characterize the rescaling-invariant properties of NN models using equivalence classes and prove that the dimension of the equivalence class space is significantly smaller than the dimension of the original weight space. Then we represent the loss function in the compact equivalence class space and develop novel algorithms that conduct optimization of the NN models directly in the equivalence class space. We call these algorithms Equivalence Class Optimization (abbreviated as EC-Opt) algorithms. Moreover, we design efficient tricks to compute the gradients in the equivalence class, which almost have no extra computational complexity as compared to standard back-propagation (BP). We conducted experimental study to demonstrate the effectiveness of our proposed new optimization algorithms. In particular, we show that by using the idea of EC-Opt, we can significantly improve the accuracy of the learned model (for both FNN and CNN), as compared to using conventional stochastic gradient descent algorithms.
• ### Caching with Time Domain Buffer Sharing(1804.02797)

April 9, 2018 cs.IT, math.IT
In this paper, storage efficient caching based on time domain buffer sharing is considered. The caching policy allows a user to determine whether and how long it should cache a content item according to the prediction of its random request time, also referred to as the request delay information (RDI). In particular, the aim is to maximize the caching gain for communications while limiting its storage cost. To achieve this goal, a queueing theoretic model for caching with infinite buffers is first formulated, in which Little's law is adopted to obtain the tradeoff between the hit ratio and the average buffer consumption. When there exist multiple content classes with different RDIs, the storage efficiency is further optimized by carefully allocating the storage cost. For more practical finite-buffer caching, a $G/GI/L/0$ queue model is formulated, in which a diffusion approximation and Erlang-B formula are adopted to determine the buffer overflow probability and the corresponding hit ratio. The optimal hit ratio is shown to be limited by the demand probability and buffer size for large and small buffers respectively. In practice, a user may exploit probabilistic caching with random maximum caching time and arithmetic caching without any need for content arrival statistics to efficiently harvest content files in air.
• ### Improving Neural Machine Translation with Conditional Sequence Generative Adversarial Nets(1703.04887)

April 8, 2018 cs.CL
This paper proposes an approach for applying GANs to NMT. We build a conditional sequence generative adversarial net which comprises of two adversarial sub models, a generator and a discriminator. The generator aims to generate sentences which are hard to be discriminated from human-translated sentences (i.e., the golden target sentences), And the discriminator makes efforts to discriminate the machine-generated sentences from human-translated ones. The two sub models play a mini-max game and achieve the win-win situation when they reach a Nash Equilibrium. Additionally, the static sentence-level BLEU is utilized as the reinforced objective for the generator, which biases the generation towards high BLEU points. During training, both the dynamic discriminator and the static BLEU objective are employed to evaluate the generated sentences and feedback the evaluations to guide the learning of the generator. Experimental results show that the proposed model consistently outperforms the traditional RNNSearch and the newly emerged state-of-the-art Transformer on English-German and Chinese-English translation tasks.
• ### Machine Learning-Assisted Least Loaded Routing to Improve Performance of Circuit-Switched Networks(1804.08403)

April 3, 2018 cs.NI
The Least Loaded (LL) routing algorithm has been in recent decades the routing method of choice in circuit switched networks and therefore it provides a benchmark against which new methods can be compared. This paper improves the performance of the LL algorithm by additionally incorporating a machine learning approach, using a conceptually simple supervised na\"ive Bayes (NB) classifier. Based on a sequence of historical network snapshots, this predicts the potential future circuit blocking probability between each node pair. These snapshots are taken for each service request arriving to the network and record the number of busy capacity units on each link at that instant. The candidate route for serving a current service request is based on both the link loads and the potential future blocking probability of the entire network in case this route is indeed used. The performance of this proposed approach is studied via simulations and compared with both the conventional LL algorithm and the Shortest Path (SP) based approach. Results indicate that the proposed supervised na\"ive Bayes classifier-assisted LL routing algorithm significantly reduces blocking probability of service connection requests and outperforms both the conventional LL and SP routing algorithms. To enable the learning process based on a large number of network snapshots, we also develop a parallel computing framework to implement parallel learning and performance evaluation. Also, a network control system supporting na\"ive Bayes classifier-assisted LL routing algorithm is addressed.
• ### A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity(1411.4097)

April 3, 2018 physics.soc-ph, cs.SI
Kleinberg proposed a family of small-world networks to explain the navigability of large-scale real-world social networks. However, the underlying mechanism that drives real networks to be navigable is not yet well understood. In this paper, we present a game theoretic model for the formation of navigable small world networks. We model the network formation as a Distance-Reciprocity Balanced (DRB) game in which people seek for both high reciprocity and long-distance relationships. We show that the game has only two Nash equilibria: One is the navigable small-world network, and the other is the random network in which each node connects with each other node with equal probability. We further show that the navigable small world is very stable --- (a) no collusion of any size would benefit from deviating from it; and (b) after an arbitrary deviations of a large random set of nodes, the network would return to the navigable small world as soon as every node takes one best-response step. In contrast, for the random network, a small group collusion or random perturbations is guaranteed to move the network to the navigable network as soon as every node takes one best-response step. Moreover, we show that navigable small world has much better social welfare than the random network, and provide the price-of-anarchy and price-of-stability results of the game. Our empirical evaluation demonstrates that the system always converges to the navigable network even when limited or no information about other players' strategies is available, and the DRB game simulated on the real-world network leads to navigability characteristic that is very close to that of the real network. Our theoretical and empirical analyses provide important new insight on the connection between distance, reciprocity and navigability in social networks.
• ### Learning for Disparity Estimation through Feature Constancy(1712.01039)

March 28, 2018 cs.CV
Stereo matching algorithms usually consist of four steps, including matching cost calculation, matching cost aggregation, disparity calculation, and disparity refinement. Existing CNN-based methods only adopt CNN to solve parts of the four steps, or use different networks to deal with different steps, making them difficult to obtain the overall optimal solution. In this paper, we propose a network architecture to incorporate all steps of stereo matching. The network consists of three parts. The first part calculates the multi-scale shared features. The second part performs matching cost calculation, matching cost aggregation and disparity calculation to estimate the initial disparity using shared features. The initial disparity and the shared features are used to calculate the feature constancy that measures correctness of the correspondence between two input images. The initial disparity and the feature constancy are then fed to a sub-network to refine the initial disparity. The proposed method has been evaluated on the Scene Flow and KITTI datasets. It achieves the state-of-the-art performance on the KITTI 2012 and KITTI 2015 benchmarks while maintaining a very fast running time.
• ### Evidence of nematic order and nodal superconducting gap along [110] direction in RbFe2As2(1803.07304)

Unconventional superconductivity often intertwines with various forms of order, such as the "nematic" order which breaks the rotational symmetry of the lattice. Investigation of these ordered phases sheds crucial light on the superconductivity itself. Here we report a low-temperature scanning tunneling microscopy (STM) study on RbFe2As2, a heavily hole-doped Fe-based superconductor (FeSC). We observe significant symmetry breaking in its electronic structure and magnetic vortex which differentiates the ({\pi}, {\pi}) and ({\pi}, -{\pi}) directions. It is thus a novel nematic state, distinct from the nematicity of undoped/lightly-doped FeSCs which breaks the ({\pi}, 0) / (0, {\pi}) equivalence. Moreover, we observe a clear "V" -shaped superconducting gap which can be well fitted with a nodal gap function. The gap is found to be suppressed on surface Rb vacancies and at step edges, and particularly strong at the [110]-oriented edges, which is possibly due to a dx2-y2 like pairing component with nodes along diagonal directions. Our results highlight the intimate connection between nematicity and superconducting pairing, and promote a universal understanding of them.
• ### Thompson Sampling for Combinatorial Semi-Bandits(1803.04623)

March 13, 2018 cs.LG
We study the application of the Thompson Sampling (TS) methodology to the stochastic combinatorial multi-armed bandit (CMAB) framework. We analyze the standard TS algorithm for the general CMAB, and obtain the first distribution-dependent regret bound of $O(m\log T / \Delta_{\min})$ for TS under general CMAB, where $m$ is the number of arms, $T$ is the time horizon, and $\Delta_{\min}$ is the minimum gap between the expected reward of the optimal solution and any non-optimal solution. We also show that one can not use an approximate oracle in TS algorithm for even MAB problems. Then we expand the analysis to matroid bandit, a special case of CMAB. Finally, we use some experiments to show the comparison of regrets of CUCB and CTS algorithms.
• ### Doubly hidden-charm/bottom $QQ\bar Q\bar Q$ tetraquark states(1803.02522)

March 13, 2018 hep-ph
We study the mass spectra for the $cc\bar c\bar c$ and $bb\bar b\bar b$ tetraquark states by developing a moment sum rule method. Our results show that the $bb\bar b\bar b$ tetraquarks lie below the threshold of $\eta_b(1S)\eta_b(1S)$. They are probably stable and very narrow. The masses for the doubly hidden-charm states $cc\bar c\bar c$ are higher than the spontaneous dissociation thresholds of two charmonium mesons. We suggest to search for such states in the $J/\psi J/\psi$ and $\eta_c(1S)\eta_c(1S)$ channels.
• ### Dynamics of Kitaev spin liquid in a local magnetic field: Emergent Kondo physics and phase transition(1803.01011)

March 13, 2018 cond-mat.str-el
We study the dynamics of fractionalized excitations in a Kitaev spin liquid (KSL) induced by a local magnetic field perpendicular to the Kitaev honeycomb lattice. The local magnetic field induces a dynamic excitation of a pair of fluxes described by a generally particle-hole asymmetric interacting resonant level model and the dynamics resembles that of a Kondo problem. The p-h asymmetry competes with the magnetic field and results in a rich phase diagram. Moreover, the magnetic field breaks the gauge equivalence of the ferromagnetic (FM) and anti-ferromagnetic (AFM) Kitaev couplings of the ground state and leads to dramatically different behaviors for the two cases. The FM couplings favor the magnetization whereas the AFM couplings impede the magnetization. More importantly, the latter case experiences a first order phase transition during magnetization whereas the former does not. This study can be generalized to the KSL in a uniform magnetic field and help resolve issues in recent experiments on KSL candidates.
• ### Improving Aviation Safety using Synthetic Vision System integrated with Eye-tracking Devices(1803.02543)

March 7, 2018 cs.HC
By collecting the data of eyeball movement of pilots, it is possible to monitor pilot's operation in the future flight in order to detect potential accidents. In this paper, we designed a novel SVS system that is integrated with an eye tracking device, and is able to achieve the following functions:1) A novel method that is able to learn from the eyeball movements of pilots and preload or render the terrain data in various resolutions, in order to improve the quality of terrain display by comprehending the interested regions of the pilot. 2) A warning mechanism that may detect the risky operation via analyzing the aviation information from the SVS and the eyeball movement from the eye tracking device, in order to prevent the maloperations or human factor accidents. The user study and experiments show that the proposed SVS-Eyetracking system works efficiently and is capable of avoiding potential risked caused by fatigue in the flight simulation.
• ### Higher order monotonicity and submodularity of influence in social networks: from local to global(1803.00666)

March 2, 2018 cs.DM, cs.SI
Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity imply global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function $\sigma(S)$ is monotone and submodular, where $S$ is a seed set and the spread function $\sigma(S)$ denotes the expected number of active nodes at termination of a diffusion process starting from $S$. The correctness of this conjecture has been proved by Mossel and Roch. In this paper, we first provide the concept AD-k (Alternating Difference-$k$) as a generalization of monotonicity and submodularity. Specifically, a set function $f$ is called \adk if all the $\ell$-th order differences of $f$ on all inputs have sign $(-1)^{\ell+1}$ for every $\ell\leq k$. Note that AD-1 corresponds to monotonicity and AD-2 corresponds to monotonicity and submodularity. We propose a refined version of KKT's conjecture: in the general threshold model, local AD-k implies global AD-k. The original KKT conjecture corresponds to the case for AD-2, and the case for AD-1 is the trivial one of local monotonicity implying global monotonicity. By utilizing continuous extensions of set functions as well as social graph constructions, we prove the correctness of our conjecture when the social graph is a directed acyclic graph (DAG). Furthermore, we affirm our conjecture on general social graphs when $k=\infty$.
• ### Train Feedfoward Neural Network with Layer-wise Adaptive Rate via Approximating Back-matching Propagation(1802.09750)

Feb. 27, 2018 cs.LG, stat.ML
Stochastic gradient descent (SGD) has achieved great success in training deep neural network, where the gradient is computed through back-propagation. However, the back-propagated values of different layers vary dramatically. This inconsistence of gradient magnitude across different layers renders optimization of deep neural network with a single learning rate problematic. We introduce the back-matching propagation which computes the backward values on the layer's parameter and the input by matching backward values on the layer's output. This leads to solving a bunch of least-squares problems, which requires high computational cost. We then reduce the back-matching propagation with approximations and propose an algorithm that turns to be the regular SGD with a layer-wise adaptive learning rate strategy. This allows an easy implementation of our algorithm in current machine learning frameworks equipped with auto-differentiation. We apply our algorithm in training modern deep neural networks and achieve favorable results over SGD.
• ### CubeP Crowds: crowd simulation integrated into "Physiology-Psychology-Physics" factors(1801.00216)

Feb. 24, 2018 cs.MA
In this paper, we present a novel CubeP model for crowd simulation that comprehensively considers physiological, psychological, and physical factors. Inspired by the theory of "the devoted actor", our model determines the movement of each individual by modeling the physical influence from physical strength and emotion. In particular, human physical strength is efficiently computed with a physiology-based method. Inspired by James-Lange theory, the emotion is determined by means of an enhanced susceptible-infectious-recovered model that leverages the inherent relation between the physical strength and the psychological emotion. As far as we know, this is the first time that we integrate physiological, psychological, and physical factors together in a unified manner, and the relationship between each other is explicitly determined. The results and comparisons with real-world video sequences verify that the new model is capable of generating effects similar to real-world scenarios. It can also reliably predict the changes in the physical strength and emotion of individuals in an emergency situation. We evaluate and validate the performance of our model in different scenarios.
• ### Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications(1703.01610)

Feb. 21, 2018 cs.LG, stat.ML
We study combinatorial multi-armed bandit with probabilistically triggered arms (CMAB-T) and semi-bandit feedback. We resolve a serious issue in the prior CMAB-T studies where the regret bounds contain a possibly exponentially large factor of $1/p^*$, where $p^*$ is the minimum positive probability that an arm is triggered by any action. We address this issue by introducing a triggering probability modulated (TPM) bounded smoothness condition into the general CMAB-T framework, and show that many applications such as influence maximization bandit and combinatorial cascading bandit satisfy this TPM condition. As a result, we completely remove the factor of $1/p^*$ from the regret bounds, achieving significantly better regret bounds for influence maximization and cascading bandits than before. Finally, we provide lower bound results showing that the factor $1/p^*$ is unavoidable for general CMAB-T problems, suggesting that the TPM condition is crucial in removing this factor.