For questions related to the linear programming optimisation technique used in the context of AI (e.g. in the context of RL, in order to solve an MDP).
Questions tagged [linear-programming]
8 questions
5
votes
1 answer
What are the differences between constraint satisfaction problems and linear programming?
I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP…
Prabh Dhali
- 51
- 1
5
votes
1 answer
How can we use linear programming to solve an MDP?
Apparently, we can solve an MDP (that is, we can find the optimal policy for a given MDP) using a linear programming formulation. What's the basic idea behind this approach? I think you should start by explaining the basic idea behind a linear…
nbro
- 39,006
- 12
- 98
- 176
4
votes
1 answer
What AI technique should I use to assign a person to a task?
I'm trying to learn AI and thinking to apply it to our system. We have an application for the translation industry. What we are doing now is the coordinator $C$ assigns a file to a translator $T$. The coordinator usually considers these criteria…
Jaime Sangcap
- 143
- 4
2
votes
1 answer
Are linear approximators better suited to some tasks compared to complex neural net functions?
Model based RL attempts to learn a function $f(s_{t+1}|s_t, a_t)$ representing the environment transitions, otherwise known as a model of the system. I see linear functions are still being used in model-based RL such as in robotic manipulation to…
mugoh
- 531
- 4
- 20
2
votes
1 answer
Which algorithm can I use to solve a problem with multiple objectives and constraints?
Consider a problem with many objectives. In my case, these are school grades for different courses (or subjects). To be more concrete, suppose that my current grade for the math course is $12/20$ and for the philosophy course is $8/20$. My objective…
YLM
- 121
- 3
0
votes
0 answers
How to use UCB or TS in linear programming?
Consider a sequential decision-making problem over $T$ periods where the parameters of the problem should be learned and also optimize an objective function. One possibility is to model the problem as a dynamic program and use RL techniques to solve…
Amin
- 471
- 2
- 11
0
votes
1 answer
Why are policy gradients popular in RL when there exists a dual LP formulation in terms of occupation measures that can be solved easily?
Why are policy gradient methods popular in reinforcement learning when there exists a dual LP formulation in terms of occupation measures that can be solved easily?
0
votes
1 answer
Is it possible to solve a linear programming problem using reinforcement learning? (DDPG algorithm)
I'm trying to solve a linear programming problem using reinforcement learning.
The linear programming problem is:
\begin{array}{ll}
\text{maximize}_x & C* x \\
\text{subject to}& A*x \le b\\
& x_i \in [0,1],\ where \…
Avarash Goel
- 1
- 2