Exploration strategy is an essential part of learning agents in model-based Reinforcement Learning. R-MAX and V-MAX are PAC-MDP strategies proved to have polynomial sample complexity; yet, their exploration behavior tend to be overly cautious in practice. We propose the principle of Increasingly Cautious Optimism (ICO) to automatically cut off unnecessarily cautious exploration, and apply ICO to R-MAX and V-MAX, yielding two new strategies, namely Increasingly Cautious R-MAX (ICR) and Increasingly Cautious V-MAX (ICV). We prove that both ICR and ICV are PACMDP, and show that their improvement is guaranteed by a tighter sample complexity upper bound. Then, we demonstrate their significantly improved performance through empirical results.

The classical theory assumes that each concept is represented by a set of features In this thesis, I investigate a hybrid knowledge representation that are shared by all the instances that are abstracted by approach that combines classic knowledge the concept. In this way, concepts can be viewed as rules representations, such as rules and ontologies, for classifying objects based on features. The prototype theory, with other cognitively plausible representations, on the other hand, states that concepts are represented such as prototypes and exemplars. The resulting through a typical instance, which has the typical features of framework can combine the strengths of the instances of the concept. Finally, the exemplar theory assumes each approach of knowledge representation, avoiding that each concept is represented by a set of exemplars their weaknesses. It can be used for developing of it. These exemplars are real entities that were previously knowledge-based systems that combine logicbased experienced by the agent. In theories based on prototypes or reasoning and similarity-based reasoning in exemplars, the categorization of a given entity is performed problem-solving processes.

Large multilayer neural networks trained with backpropagation have recently achieved state-of-the-art results in a wide range of problems. However, using backprop for neural net learning still has some disadvantages, e.g., having to tune a large number of hyperparameters to the data, lack of calibrated probabilistic predictions, and a tendency to overfit the training data. In principle, the Bayesian approach to learning neural networks does not have these problems. However, existing Bayesian techniques lack scalability to large dataset and network sizes. In this work we present a novel scalable method for learning Bayesian neural networks, called probabilistic backpropagation (PBP). Similar to classical backpropagation, PBP works by computing a forward propagation of probabilities through the network and then doing a backward computation of gradients. A series of experiments on ten real-world datasets show that PBP is significantly faster than other techniques, while offering competitive predictive abilities. Our experiments also show that PBP provides accurate estimates of the posterior variance on the network weights.

We consider factoring low-rank tensors in the presence of outlying slabs. This problem is important in practice, because data collected in many real-world applications, such as speech, fluorescence, and some social network data, fit this paradigm. Prior work tackles this problem by iteratively selecting a fixed number of slabs and fitting, a procedure which may not converge. We formulate this problem from a group-sparsity promoting point of view, and propose an alternating optimization framework to handle the corresponding $\ell_p$ ($0

The time complexity of problems and algorithms, i.e., the scaling of the time required for solving a problem instance as a function of instance size, is of key interest in theoretical computer science and practical applications. In this context, propositional satisfiability (SAT) is one of the most intensely studied problems, and it is generally believed that solving SAT requires exponential time in the worst case. For more than two decades, random 3-SAT at the solubility phase transition has played a pivotal role in the theoretical and empirical investigation of SAT solving, and to this day, it is arguably the most prominent model for difficult SAT instances. Here, we study the empirical scaling of the running time of several prominent, high-performance SAT solvers on random 3-SAT instances from the phase transition region. After introducing a refined model for the location of the phase transition point, we show that the median running time of three incomplete, SLS-based solvers – WalkSAT/SKC, BalancedZ and probSAT – scales polynomially with instance size. An analogous analysis of three complete, DPLL-based solvers – kcnfs, march_hi and march_br – clearly indicates exponential scaling of median running time. Moreover, exponential scaling is witnessed for these DPLL-based solvers when solving only satisfiable and only unsatisfiable instances, and the respective scaling models for each solver differ mostly by a constant factor.

Cost-optimal planning (COP) uses action costs and asks for a minimum-cost plan. It is sometimes assumed that there is no harm in using actions with zero cost or rational cost. Classical complexity analysis does not contradict this assumption; planning is PSPACE-complete regardless of whether action costs are positive or non-negative, integer or rational. We thus apply parameterised complexity analysis to shed more light on this issue. Our main results are the following. COP is [W2]-complete for positive integer costs, i.e. it is no harder than finding a minimum-length plan, but it is paraNP-hard if the costs are non-negative integers or positive rationals. This is a very strong indication that the latter cases are substantially harder. Net-benefit planning (NBP) additionally assigns goal utilities and asks for a plan with maximum difference between its utility and its cost. NBP is paraNP-hard even when action costs and utilities are positive integers, suggesting that it is harder than COP. In addition, we also analyse a large number of subclasses, using both the PUBS restrictions and restricting the number of preconditions and effects.

Interactive dynamic influence diagrams(I-DIDs) are a well recognized decision model that explicitly considers how multiagent interaction affects individual decision making. To predict behavior of other agents, I-DIDs require models of the other agents to be known ahead of time and manually encoded. This becomes a barrier to I-DID applications in a human-agent interaction setting, such as development of intelligent non-player characters(NPCs) in real-time strategy(RTS) games, where models of other agents or human players are often inaccessible to domain experts. In this paper, we use automatic techniques for learning behavior of other agents from replay data in RTS games. We propose a learning algorithm with improvement over existing work by building a full profile of agent behavior. This is the first time that data-driven learning techniques are embedded into the I-DID decision making framework. We evaluate the performance of our approach on two test cases.

Distributed word representations have a rising interest in NLP community. Most of existing models assume only one vector for each individual word, which ignores polysemy and thus degrades their effectiveness for downstream tasks. To address this problem, some recent work adopts multi-prototype models to learn multiple embeddings per word type. In this paper, we distinguish the different senses of each word by their latent topics. We present a general architecture to learn the word and topic embeddings efficiently, which is an extension to the Skip-Gram model and can model the interaction between words and topics simultaneously. The experiments on the word similarity and text classification tasks show our model outperforms state-of-the-art methods.

List of sponsors of the 2015 IJCAI conference.

We study equilibrium dynamics in candidacy games, in which candidates may strategically decide to enter the election or withdraw their candidacy, following their own preferences over possible outcomes. Focusing on games under Plurality, we extend the standard model to allow for situations where voters may refuse to return their votes to those candidates who had previously left the election, should they decide to run again. We show that if at the time when a candidate withdraws his candidacy, with some positive probability each voter takes this candidate out of his future consideration, the process converges with probability 1. This is in sharp contrast with the original model where the very existence of a Nash equilibrium is not guaranteed. We then consider the two extreme cases of this setting, where voters may block a withdrawn candidate with probabilities 0 or 1. In these scenarios, we study the complexity of reaching equilibria from a given initial point, converging to an equilibrium with a predermined winner or to an equilibrium with a given set of running candidates. Except for one easy case, we show that these problems are NP-complete, even when the initial point is fixed to a natural---truthful---state where all potential candidates stand for election.